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'])