Python中的双端队列详解

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

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

注意怪胎!巩固你的基础Python编程基础课程和学习基础知识。

首先, 你的面试准备可通过以下方式增强你的数据结构概念:Python DS课程。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: