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

发布时间:2024年01月07日

概述

双端队列(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'不'))
文章来源:https://blog.csdn.net/ringnian/article/details/135436767
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。