Python中的双端队列deque

python收藏家

Python中的deque（双端队列）是使用模块“collections”实现的。当我们需要从容器的两端进行更快的追加和弹出操作时，deque比列表更受欢迎，因为与提供O（n）时间复杂度的列表相比，deque为追加和弹出操作提供了O（1）时间复杂度。

deque输入的类型

输入deque：在一端限制输入，而在两端允许删除。
输出deque：在一端限制输出，但在两端允许插入。

示例：演示双端队列的Python代码

from collections import deque
# Declaring deque
queue = deque(['name','age','DOB']) 
print(queue)

输出

deque(['name', 'age', 'DOB'])

对deque的操作

1. 高效地追加项

- append()：此函数用于将其参数中的值插入到双端队列的右端。

- appendleft()：此函数用于将其参数中的值插入到双端队列的左端。

import collections
# initializing deque
de = collections.deque([1, 2, 3])
print("deque: ", de)
# using append() to insert element at right end
# inserts 4 at the end of deque
de.append(4)
# printing modified deque
print("\nThe deque after appending at right is : ")
print(de)
# using appendleft() to insert element at left end
# inserts 6 at the beginning of deque
de.appendleft(6)
# printing modified deque
print("\nThe deque after appending at left is : ")
print(de)

输出

deque:  deque([1, 2, 3])
The deque after appending at right is : 
deque([1, 2, 3, 4])
The deque after appending at left is : 
deque([6, 1, 2, 3, 4])

2. 有效地弹出项

- pop()：-此函数用于从双端队列的右端删除参数。

- popleft()：-此函数用于从双端队列的左端删除参数。

import collections
# initializing deque
de = collections.deque([6, 1, 2, 3, 4])
print("deque: ", de)
# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()
# printing modified deque
print("\nThe deque after deleting from right is : ")
print(de)
# using popleft() to delete element from left end
# deletes 6 from the left end of deque
de.popleft()
# printing modified deque
print("\nThe deque after deleting from left is : ")
print(de)

输出

deque:  deque([6, 1, 2, 3, 4])
The deque after deleting from right is : 
deque([6, 1, 2, 3])
The deque after deleting from left is : 
deque([1, 2, 3])

3. 访问双端队列中的项

- index(ele，start，end)：该函数返回参数中提到的值的第一个索引，从start开始搜索到end索引。

- insert(i，a)：此函数将参数（a）中提到的值插入参数中指定的索引（i）处。

- remove()：此函数删除参数中第一次出现的值。

- count()：该函数计算参数中提到的值出现的次数。

# Python code to demonstrate working of
# insert(), index(), remove(), count()
# importing "collections" for deque operations
import collections
# initializing deque
de = collections.deque([1, 2, 3, 3, 4, 2, 4])
# using index() to print the first occurrence of 4
print ("The number 4 first occurs at a position : ")
print (de.index(4,2,5))
# using insert() to insert the value 3 at 5th position
de.insert(4,3)
# printing modified deque
print ("The deque after inserting 3 at 5th position is : ")
print (de)
# using count() to count the occurrences of 3
print ("The count of 3 in deque is : ")
print (de.count(3))
# using remove() to remove the first occurrence of 3
de.remove(3)
# printing modified deque
print ("The deque after deleting first occurrence of 3 is : ")
print (de)

输出

The number 4 first occurs at a position : 
The deque after inserting 3 at 5th position is : 
deque([1, 2, 3, 3, 3, 4, 2, 4])
The count of 3 in deque is : 
The deque after deleting first occurrence of 3 is : 
deque([1, 2, 3, 3, 4, 2, 4])

4. 双端队列的大小

- len（dequeue）：返回当前队列的大小。

from collections import deque
# initializing deque
de = deque([1, 2, 3, 4, 5, 6])
print("Current Deque: ", de)
# printing current size of deque
print(f"Size of Deque: {len(de)}")
# using pop() to delete element from right end
# deletes 6 from the right end of deque
de.pop()
# printing modified deque
print("\nThe deque after deleting from right is: ", end = '')
print(de)
# printing current size of deque
print(f"Size of Deque: {len(de)}")

输出

Current Deque:  deque([1, 2, 3, 4, 5, 6])
Size of Deque: 6
The deque after deleting from right is: deque([1, 2, 3, 4, 5])
Size of Deque: 5

5. 双端队列的前端和后端

- deque[0]：我们可以使用de[0]索引访问deque的前端元素。

- deque[-1]：我们可以使用de[-1]索引访问deque的后端元素。

from collections import deque
# initializing deque
de = deque([1, 2, 3, 4, 5, 6])
print("Current Deque: ", de)
# Accessing the front element of the deque
print("Front element of the deque:", de[0])
# Accessing the back element of the deque
print("Back element of the deque:", de[-1])

输出

Current Deque:  deque([1, 2, 3, 4, 5, 6])
Front element of the deque: 1
Back element of the deque: 6

6. 对双端队列的其他操作

- extend（iterable）：此函数用于在双端队列的右端添加多个值。传递的参数是可迭代的。

- extendleft（iterable）：此函数用于在双端队列的左端添加多个值。传递的参数是可迭代的。由于使用了左追加，顺序颠倒了。

- reverse（）：此函数用于反转双端队列元素的顺序。

- rotate（）：此函数按参数中指定的数字旋转双端队列。如果指定的数字为负数，则向左旋转。否则旋转向右。

# Python code to demonstrate working of
# extend(), extendleft(), rotate(), reverse()
import collections
# initializing deque
de = collections.deque([1, 2, 3,])
# using extend() to add numbers to right end
# adds 4,5,6 to right end
de.extend([4,5,6])
# printing modified deque
print ("The deque after extending deque at end is : ")
print (de)
# using extendleft() to add numbers to left end
# adds 7,8,9 to left end
de.extendleft([7,8,9])
# printing modified deque
print ("The deque after extending deque at beginning is : ")
print (de)
# using rotate() to rotate the deque
# rotates by 3 to left
de.rotate(-3)
# printing modified deque
print ("The deque after rotating deque is : ")
print (de)
# using reverse() to reverse the deque
de.reverse()
# printing modified deque
print ("The deque after reversing deque is : ")
print (de)

输出

The deque after extending deque at end is : 
deque([1, 2, 3, 4, 5, 6])