Python数据结构——双端队列

cjie 发布于2019-07-31 10:49 / 3283人阅读

摘要：在队尾添加入一个元素，参数是数据项，无返回值。删除队首的元素，不需要参数，返回值是被删除的元素，队列本身有变化。列表用于随机访问和定长数据的操作，包括切片，而双端队列适用于在两端压入或弹出元素，索引但不包括切片的效率可能低于列表。

双端队列（Deque），是一种类似于队列的元素的有序集合。它拥有两端，队首和队尾，并且元素保持在当前的位置。双端队列的一个不同点就是，添加和删除元素的位置不受限制。新元素可以在队首或者队尾添加。同样地，双端队列中的元素可以从两端弹出。在某种意义上，这种混合的线性结构同时具有栈和队列的性质。

很重要的一点，即使双端队列具有栈和队列的特性，但它不会被强制执行的LIFO和FIFO操作。这取决于你做出统一的添加和删除操作。

双端队列的操作如下：

Deque()          创建一个空的双端队列，无参数，返回值是空队列。
add_front(item)  在队首添加入一个元素，参数是数据项，无返回值。
add_rear(item)   在队尾添加入一个元素，参数是数据项，无返回值。
remove_front()   删除队首的元素，不需要参数，返回值是被删除的元素，队列本身有变化。
remove_rear()    删除队尾的元素，不需要参数，返回值是被删除的元素，队列本身有变化。
is_Empty()       检测队列是否为空。无参数，返回布尔值。
size()           返回队列元素的个数。无参数，返回一个整数。

双端队列操作举例：

Deque Operation	Deque Contents	Return Value
d.isEmpty()	[]	True
d.addRear(4)	[4]
d.addRear("dog")	["dog",4,]
d.addFront("cat")	["dog",4,"cat"]
d.addFront(True)	["dog",4,"cat",True]
d.size()	["dog",4,"cat",True]	4
d.isEmpty()	["dog",4,"cat",True]	False
d.addRear(8.4)	[8.4,"dog",4,"cat",True]
d.removeRear()	["dog",4,"cat",True]	8.4
d.removeFront()	["dog",4,"cat"]	True

列表 VS 双端队列

双端队列支持线程安全，在双端队列的任何一端执行添加和删除操作，它们的内存效率几乎相同（时间复杂度为O(1)）。

虽然list也支持类似的操作，但是它对定长列表的操作表现很不错，而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时，其时间复杂度就变为O(n)了。

在双端队列中最好不使用切片和索引，你可以用popleft和appendleft方法，双端队列对这些操作做了优化。在两端的索引访问时间复杂度为O(1)，但是访问中间元素的时间复杂度为O(n)，速度较慢，对于快速随机的访问，还是用列表代替。

列表用于随机访问和定长数据的操作，包括切片，而双端队列适用于在两端压入或弹出元素，索引（但不包括切片）的效率可能低于列表。

实现双端队列：

class Deque:
    """模拟双端队列""" 
    def __init__(self):
        self.items = []

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

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

    def addRear(self, item):
        self.items.insert(0,item)

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

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

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

以下是测试代码：

d=Deque()
print(d.isEmpty())
d.addRear(4)
d.addRear("dog")
d.addFront("cat")
d.addFront(True)
print(d.size())
print(d.isEmpty())
d.addRear(8.4)
print(d.removeRear())
print(d.removeFront())

云服务器 GPU云服务器 python队列 python的队列 python队列实现 python多队列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44170.html

Python奇遇记：数据结构窥探

摘要：挤掉了堆中实现了堆排序。你可以用堆排序来查找一个序列中最大的或者最小的几个元素。除了使用堆排序，中还有排序和，这两个排序最终生成以列表表示的排序结果，堆排序也是。这次我们来说说python中的数据结构。当然了，不会讲很基础的内容。用过python的都知道，python有着与其他语言很不一样的数据类型，像什么列表、元组、集合、字典之类。这些数据类型造就了python简单易用同时又很强...

mrli2016 2019-07-31 11:01 评论0 收藏0
不可不知的python模块--collections

摘要：原生的也可以从头部添加和取出对象就像这样但是值得注意的是，对象的这两种用法的时间复杂度是，也就是说随着元素数量的增加耗时呈线性上升。基本介绍 Python拥有一些内置的数据类型，比如str, int, list, tuple, dict等， collections模块在这些内置数据类型的基础上，提供了几个额外的数据类型： namedtuple(): 生成可以使用名字来访问元素内容的...

韩冰 2019-07-30 16:18 评论0 收藏0
Java 集合 Queue

摘要：除此之外，还有一个接口，代表一个双端队列，双端队列可以同时从两端删除添加元素，因此的实现类既可当成队列使用，也可当成栈使用。相当于栈方法将一个元素进该双端队列所表示的栈的栈顶。 Queue用于模拟队列这种数据结构，队列通常是指先进先出（FIFO）的容器。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（p...

bang590 2019-08-14 17:04 评论0 收藏0
LeetCode 之 JavaScript 解答第641题 —— 设计双端队列（Design Cir

摘要：小鹿题目设计实现双端队列。你的实现需要支持以下操作构造函数双端队列的大小为。获得双端队列的最后一个元素。检查双端队列是否为空。数组头部删除第一个数据。以上数组提供的使得更方便的对数组进行操作和模拟其他数据结构的操作，栈队列等。 Time：2019/4/15Title: Design Circular DequeDifficulty: MediumAuthor: 小鹿题目：Desi...

Freeman 2019-08-23 16:58 评论0 收藏0
LeetCode 232：用栈实现队列 Implement Queue using Stacks

摘要：题目使用栈实现队列的下列操作将一个元素放入队列的尾部。用栈实现队列，可以用两个栈完成题解。入队列时用存入节点，出队列时内节点顺序出栈压入中。这类编程语言就压根不需要用队列实现栈或用栈实现队列这种问题，因为栈和队列本身就必须借助实现。题目：使用栈实现队列的下列操作： push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队...

cloud 2019-08-19 10:26 评论0 收藏0