Python双端队列的3种实现及应用

概述

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

双端队列的数据存储结构可以是顺序表，也可以是链表，即顺序双端队列和链双端队列。

图片.png

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

Deque() 创建双端队列
insert(item) 向队首插入项
append(item) 向队尾插入项
popFront() 返回队首的项，并从双端队列中删除该项
pop() 返回队尾的项，并从双端队列中删除该项
isEmpty() 判断双端队列是否为空
size() 返回双端队列中项的个数
get(index) 返回对列中的对象
show() 对象遍历

操作示意图：

图片.png

顺序双端队列

顺序双端队列是使用顺序表存储数据的双端队列，Python 中的列表元组都属于顺序表，下面使用列表来存储数据，实现顺序双端队列。

class SeQueue(object):
    def __init__(self):
        self.__members = list()

    def isEmpty(self):
        return not len(self.__members)

    def show(self):
        if self.isEmpty():
            return
        for member in self.__members:
            if self.__members.index(member) != len(self.__members) - 1:
                print(member, end=',')
            else:
                print(member)

    def insert(self, data):
        self.__members.insert(0, data)

    def append(self, data):
        self.__members.append(data)

    def popFront(self):
        if self.isEmpty():
            return
        return self.__members.pop(0)

    def pop(self):
        if self.isEmpty():
            return
        return self.__members.pop()

    def size(self):
        return len(self.__members)

    def check(self, index):
        if index < 0 or index > len(self.__members) - 1:
            raise IndexError
        return self.__members[index]

使用
if? name?== ' main':
sdq = SeQueue()
print("isEmpty: ", sdq.isEmpty())
sdq.show()
sdq.insert('x')
sdq.insert('z')
sdq.append(10)
sdq.append(20)
sdq.show()
print(sdq.popFront())
print(sdq.pop())
sdq.show()
print("sequence double queue length: ", sdq.size())
print("index member is: ", sdq.check(2))

链双端队列的实现

链双端队列是使用链表存储数据的双端队列，链表是逻辑有序的，由一个一个的节点构成，所以先声明一个创建节点的类。

# coding=utf-8
class Node(object):
    """
    链双端，节点对象类
    """
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkQueue(object):
    """
    链表
    """
    def __init__(self):
        self.__head = None

    def isEmpty(self):
        return not self.__head

    def show(self):
        if self.isEmpty():
            return
        cur = self.__head
        while cur is not None:
            if cur.next is not None:
                print(cur.data, end=',')
            else:
                print(cur.data)
            cur = cur.next

    def insert(self, data):
        node = Node(data)
        node.next = self.__head
        self.__head = node

    def append(self, data):
        if self.isEmpty():
            self.insert(data)
            return
        node = Node(data)
        cur = self.__head
        while cur.next is not None:
            cur = cur.next
        cur.next = node

    def popFront(self):
        if self.isEmpty():
            return
        cur = self.__head
        self.__head = self.__head.next
        return cur.data

    def pop(self):
        if self.isEmpty():
            return
        cur = self.__head
        prev = None
        while cur.next is not None:
            prev = cur
            cur = cur.next
        if cur == self.__head:
            self.__head = self.__head.next
            return
        prev.next = cur.next
        return cur.data

    def size(self):
        size = 0
        cur = self.__head
        while cur is not None:
            size += 1
            cur = cur.next
        return size

    def get(self, index):
        if index < 0 or index >= self.size():
            raise IndexError
        cur = self.__head
        for _ in range(index):
            cur = cur.next
        return cur.data

用标准库collections.deque实现

from collections import deque


class Deque:
    def __init__(self):
        self.items = deque()

    def insert(self, item):
        self.items.appendleft(item)

    def append(self, item):
        self.items.append(item)

    def show(self):
        if self.isEmpty():
            return
        for index, value in enumerate(self.items):
            if index != len(self.items) - 1:
                print(self.items.__getitem__(index), end=',')
            else:
                print(self.items.__getitem__(index))

    def popFront(self):
        return self.items.popleft()

    def pop(self):
        return self.items.pop()

    def isEmpty(self):
        return self.size() == 0

    def size(self):
        return len(self.items)

    def get(self, index):
        self.items.__getitem__(index)

举例

ldq = Deque()
    # print("isEmpty: ", ldq.isEmpty())
    # ldq.show()

    ldq.insert('X')
    ldq.insert('Y')
    ldq.insert('Z')
    ldq.append(100)
    ldq.append(200)
    ldq.append(300)
    ldq.show()
    # print(ldq.popFront())
    # print(ldq.pop())
    # ldq.show()

    print("link queue length: ", ldq.size())
    print("index member is: ", ldq.get(2))

输出

Z,Y,X,100,200,300
link queue length:  6
index member is:  None

应用 - 回文算法

算法：回文（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.insert(ch)
    while chardeque.size() > 1:
        first = chardeque.popFront()
        last = chardeque.pop()
        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'不'))