Python实现的数据结构与算法之双端队列详解

本文实例讲述了python实现的数据结构与算法之双端队列。分享给大家供大家参考。具体分析如下：

一、概述

双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端：队首（front）、队尾（rear），但与队列不同的是，插入操作在两端（队首和队尾）都可以进行，删除操作也一样。

二、adt

双端队列adt（抽象数据类型）一般提供以下接口：

① deque() 创建双端队列
② addfront(item) 向队首插入项
③ addrear(item) 向队尾插入项
④ removefront() 返回队首的项，并从双端队列中删除该项
⑤ removerear() 返回队尾的项，并从双端队列中删除该项
⑥ empty() 判断双端队列是否为空
⑦ size() 返回双端队列中项的个数

双端队列操作的示意图如下：

三、python实现

在python中，有两种方式可以实现上述的双端队列adt：使用内建类型list、使用标准库collections.deque（其实collections.deque就是python中双端队列的标准实现）。

两种方式的不同主要体现在性能上（具体参考 | timecomplexity）：

操作|实现方式  list  collections.deque
-----------------------------------------
addfront    o(n)  o(1)
-----------------------------------------
addrear     o(1)  o(1)
-----------------------------------------
removefront   o(n)  o(1)
-----------------------------------------
removerear   o(1)  o(1)

1、使用内建类型list

#!/usr/bin/env python
# -*- coding: utf-8 -*-
class deque:
  def __init__(self):
    self.items = []
  def addfront(self, item):
    self.items.insert(0, item)
  def addrear(self, item):
    self.items.append(item)
  def removefront(self):
    return self.items.pop(0)
  def removerear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

2、使用标准库collections.deque

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from collections import deque
class deque:
  def __init__(self):
    self.items = deque()
  def addfront(self, item):
    self.items.appendleft(item)
  def addrear(self, item):
    self.items.append(item)
  def removefront(self):
    return self.items.popleft()
  def removerear(self):
    return self.items.pop()
  def empty(self):
    return self.size() == 0
  def size(self):
    return len(self.items)

四、应用

回文（palindrome）是正读反读都一样的单词或句子，是一种修辞方式和文字游戏。

英文例子：

madam
able was i ere i saw elba

中文例子：

花非花
人人为我、我为人人
如果要实现一个 回文验证算法（验证一个给定的字符串是否为回文），使用deque类将非常容易：将字符串存储到双端队列，同时取出首尾字符并比较是否相等，只要有一对字符不等，则该字符串不是回文；若全部相等，则该字符串为回文。具体代码如下：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def palchecker(astring):
  chardeque = deque()
  for ch in astring:
    chardeque.addrear(ch)
  while chardeque.size() > 1:
    first = chardeque.removefront()
    last = chardeque.removerear()
    if first != last:
      return false
  return true
if __name__ == '__main__':
  str1 = 'able was i ere i saw elba'
  print('"%s" is%s palindrome' % (str1, '' if palchecker(str1) else ' not'))
  str2 = u'人人为我、我为人人'
  print(u'"%s"%s是回文' % (str2, u'' if palchecker(str2) else u'不'))
  str3 = u"what's wrong 怎么啦"
  print(u'"%s"%s是回文' % (str3, u'' if palchecker(str3) else u'不'))

运行结果：

$ python palchecker.py
"able was i ere i saw elba" is palindrome
"人人为我、我为人人"是回文
"what's wrong 怎么啦"不是回文

希望本文所述对大家的python程序设计有所帮助。