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