python数据结构之双端队列


概念

双端队列是一种有次序的数据集合,跟队列类似,也有首端与尾端之分,但与队列不同的是,双端队列的首端和尾端都可以进行入队和出队操作,即新元素既可以添加到首端,也可以添加到尾端,同理,已有的元素也可以从任意一端移除。因此,双端队列集合了队列和栈的特点,既可以实现先进先出,又可以实现后进先出。

注意:虽然双端队列有队列和栈的特点,但是双端队列本身内部的数据并不具有先进先出或者后进先出的特性,具体的排列次序是要由使用者自己实现,比如要用双端队列模拟栈,那么我们就要自己维持数据的后进先出次序。

实现

列表实现

依然可以用python基础的数据结构列表来实现栈,列表的前端、后端分别作为双端队列的尾端、首端,也可以反过来。

双端队列的首尾都可以进行数据的添加、移除操作,因此双端队列要有从首端入队操作,从首端出队操作,从尾端入队操作,从尾端出队操作。

代码实现:

class Deque:
    """
    利用list实现双端队列
    list下标为0的一端代表双端队列的尾端,
    liat下标为-1的一端代表双端队列的首端
    """
    def __init__(self):
        """将双端队列初始化为空列表"""
        self.items = []

    def isEmpty(self):
        return self.items == []

    def appendFront(self, item):
        """从队首添加数据项"""
        self.items.append(item)

    def appendRear(self, item):
        """从队尾添加数据项"""
        self.items.insert(0, item)

    def popFront(self):
        """从队首移除数据项"""
        return self.items.pop()

    def popRear(self):
        """从队尾移除数据项"""
        return self.items.pop(0)

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


def testDeque():
    """对双端队列进行测试"""
    deque = Deque()

    print(deque.isEmpty())

    deque.appendRear(123)
    deque.appendRear('abc')
    deque.appendFront(True)
    deque.appendFront(5.2)
    print(deque.size())

    print(deque.popFront())
    print(deque.popRear())

    print(deque.isEmpty())

if __name__ == '__main__':
    testDeque()

输出结果为:

True
4
5.2
abc
False

分析代码可以发现,首端的入队出队操作的时间复杂度都是O(1),尾端的入队出队操作的时间复杂度都是O(n)的。

python内置的双端队列

实际上python内置模块collections内已经实现了双端队列,可以通过collections.deque()进行调用。

双端队列的应用

检测回文字串

所谓回文子串就是正读和反读都一样的字串,比如“abcba”是回文字串,“abca”不是回文字串,需要注意的是,单独一个字符,比如“a”,也是回文字串。

代码实现:

def palCheck(aString):
    """
    检测回文字串
    :param aString: 待检测的字符串 
    :return: True: 是回文字串, False: 不是回文字串
    """
    #如果待检测字符串的长度为1,直接返回True
    if len(aString) == 1: return True
    charDeque = Deque()

    # 将待检测字符串入队
    for char in aString:
        charDeque.appendFront(char)

    while charDeque.size() > 1:
        # 将队首字符和队尾字符出队
        first = charDeque.popFront()
        last = charDeque.popRear()
        if first != last:
            return False

    return True

文章作者: likai
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 likai !
评论
 上一篇
数据结构之链表 数据结构之链表
概念python内置的数据结构列表是一种顺序表,列表在内存中占用一段连续的内存空间,列表的第一项数据的地址就是列表的地址,数据项的下标其实可以看做是相对于列表起始地址的偏移量,这也就是为什么列表的查询的时间复杂度是O(1)的,而插入inse
2020-07-28
下一篇 
中断系统 中断系统
计算机组成原理系列之十一
  目录