# Python中的双端队列详解

2021年3月9日16:11:58 发表评论 365 次浏览

Python中的双端队列(双端队列)是使用模块collections。 Deque优先于list在我们需要从容器的两端更快地执行添加和弹出操作的情况下, 因为双端队列提供了O(1)与提供O(n)时间复杂度的列表相比, 追加和弹出操作的时间复杂度。

``````# Python code to demonstrate deque

from collections import deque

# Declaring deque
queue = deque([ 'name' , 'age' , 'DOB' ])

print (queue)``````

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

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

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

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

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

``````# Python code to demonstrate working of
# append(), appendleft(), pop(), and popleft()

# importing "collections" for deque operations
import collections

# initializing deque
de = collections.deque([ 1 , 2 , 3 ])

# using append() to insert element at right end
# inserts 4 at the end of deque
de.append( 4 )

# printing modified deque
print ( "The deque after appending at right is : " )
print (de)

# using appendleft() to insert element at right end
# inserts 6 at the beginning of deque
de.appendleft( 6 )

# printing modified deque
print ( "The deque after appending at left is : " )
print (de)

# using pop() to delete element from right end
# deletes 4 from the right end of deque
de.pop()

# printing modified deque
print ( "The 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 ( "The deque after deleting from left is : " )
print (de)``````

``````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])
The deque after deleting from right is :
deque([6, 1, 2, 3])
The deque after deleting from left is :
deque([1, 2, 3])``````

index(ele, beg, end)：-此函数返回参数中提到的值的第一个索引, 从beg开始搜索, 直到结束索引。

insert(i, a)：-此函数将在arguments(a)中提到的值插入到arguments中指定的索引(i)。

：-此功能

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 :
4
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 :
3
The deque after deleting first occurrence of 3 is :
deque([1, 2, 3, 3, 4, 2, 4])``````

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

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

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

rotation()：-此函数将双端队列旋转由参数指定的数字。如果指定的数字为负, 则向左旋转。其他旋转向右。

``````# Python code to demonstrate working of
# extend(), extendleft(), rotate(), reverse()

# importing "collections" for deque operations
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 right 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])
The deque after extending deque at beginning is :
deque([9, 8, 7, 1, 2, 3, 4, 5, 6])
The deque after rotating deque is :
deque([1, 2, 3, 4, 5, 6, 9, 8, 7])
The deque after reversing deque is :
deque([7, 8, 9, 6, 5, 4, 3, 2, 1])`````` 