Python中的双端队列
Deque基本上是堆栈和队列结构的一般化，从左到右进行初始化。它使用list对象创建双端队列，为弹出和追加提供O(1)时间复杂度。
Dequeis是一个标准库类，它位于collections模块中。
首先要使用它，我们需要将其导入集合标准库模块。
import collections
在本节中，我们将看到Deque类的一些功能
双端队列的附加功能
有两种不同类型的附加。该append()方法用于在队列的右端添加元素，该appendleft()方法用于在队列的左侧附加元素。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))
#insert x at right and B at left
my_deque.append('x')
my_deque.appendleft('B')
print('Dequeue after appending: ' + str(my_deque))输出结果
Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e']) Dequeue after appending: deque(['B', '1', '2', '4', 'd', 'f', 'r', 'e', 'x'])
双端队列的弹出功能
像追加一样，有两种不同类型的弹出函数。该pop()方法用于从队列中删除并返回最右边的元素，该popleft()方法用于从队列中删除并返回最左边的元素。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('124dfre')
print('Dequeue: ' + str(my_deque))
#delete item from right and left
item = my_deque.pop()
print('Popped Item: ' + str(item))
item = my_deque.popleft()
print('Popped Item: ' + str(item))
print('Dequeue after pop operations: ' + str(my_deque))输出结果
Dequeue: deque(['1', '2', '4', 'd', 'f', 'r', 'e']) Popped Item: e Popped Item: 1 Dequeue after pop operations: deque(['2', '4', 'd', 'f', 'r'])
Deque中与项目相关的功能
Deque中的某些功能用于获取与项目有关的信息。有一些功能，例如index()，count()等等。index方法用于获取元素首次出现的索引。如果没有随元素传递参数，它将选择整个列表，指定了特定限制后，它将检查该限制中的索引。另一方面，该count()方法计算出双端队列中项目的频率。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#find the index of D
print('Index of D:' + str(my_deque.index('D')))
print('Index of D in range 5 to 8 is: ' + str(my_deque.index('D', 5, 8)))
#Count the number of occurrences
print('Occurrences of A: ' + str(my_deque.count('A')))
print('Occurrences of D: ' + str(my_deque.count('D')))输出结果
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Index of D:4 Index of D in range 5 to 8 is: 5 Occurrences of A: 2 Occurrences of D: 3
Deque中的insert()和remove()方法
我们已经在Deque中看到了append和pop函数，分别用于插入和删除元素。还有两种与插入和删除有关的方法。该insert()方法用于插入数字。在这种情况下，我们可以提供插入索引。因此，可以在指定位置插入该项目。并且该remove()方法用于删除元素的首次出现。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Insert letter G and H into the position 5, 7 respectively
my_deque.insert(5, 'G')
my_deque.insert(7, 'H')
print('Dequeue after inserting: ' + str(my_deque))
#Delete first occurrence of letter D
my_deque.remove('D')
print('Dequeue after removing: ' + str(my_deque))输出结果
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Dequeue after inserting: deque(['A', 'A', 'B', 'C', 'D', 'G', 'D', 'H', 'E', 'F', 'D']) Dequeue after removing: deque(['A', 'A', 'B', 'C', 'G', 'D', 'H', 'E', 'F', 'D'])
在Deque中扩展功能
扩展功能用于将多个元素添加到Deque中。我们可以使用列表，元组之类的集合来提供多个值。有两种扩展功能。该extend()方法用于在右侧添加元素，类似于重复append()方法。并且该extendleft()方法用于在左侧添加元素，类似于重复appendleft()方法。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
#Extend by adding 1, 3, 5, 7 to the right and x, y, z to the left
my_deque.extend([1, 3, 5, 7])
my_deque.extendleft(['x', 'y', 'z'])
print('Dequeue after Extending: ' + str(my_deque))输出结果
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Dequeue after Extending: deque(['z', 'y', 'x', 'A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D', 1, 3, 5, 7])
双端队列中的反转和旋转功能
我们可以使用该reverse()方法反转出队列的顺序。还有另一种方法rotate()。使用rotate方法，双端队列可以使用指定为参数的数字进行旋转。如果参数为正，则向右旋转，如果为负数，则向左旋转。
范例程式码
import collections as col
#Insert some elements into the queue at first
my_deque = col.deque('AABCDDEFD')
print('Dequeue: ' + str(my_deque))
my_deque.reverse()
print('Deque after Reversing:' + str(my_deque))
#rotate to the right, 3 elements
my_deque.rotate(3)
print('Deque after rotating:' + str(my_deque))输出结果
Dequeue: deque(['A', 'A', 'B', 'C', 'D', 'D', 'E', 'F', 'D']) Deque after Reversing:deque(['D', 'F', 'E', 'D', 'D', 'C', 'B', 'A', 'A']) Deque after rotating:deque(['B', 'A', 'A', 'D', 'F', 'E', 'D', 'D', 'C'])