Python の Deque (Double Ended Queue) はモジュールを使用して実装されます コレクション 。 deque は、コンテナーの両端からの追加およびポップ操作を迅速に行う必要がある場合、リストよりも優先されます。 ○(1) O(n) 時間の計算量を提供するリストと比較した、追加およびポップ操作の時間計算量。

制限付きデキュー入力のタイプ

入力制限デキュー : 入力は一方の端で制限されますが、両端での削除は許可されます。出力制限デキュー : 出力は一端で制限されますが、両端での挿入は許可されます。

例: デモする Python コード

Python3

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

出力

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

デックに対する操作

例 1: 項目を効率的に追加する

append() :- この関数は、引数の値を両端キューの右端に挿入するために使用されます。 appendleft() :- この関数は、引数の値を両端キューの左端に挿入するために使用されます。

Python3

# importing 'collections' for deque operations> 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> (> ' The 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> (> ' The 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() :- この関数は、両端キューの左端から引数を削除するために使用されます。

Python3

# importing 'collections' for deque operations> 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> (> ' 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)>

出力

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, beg, end) :- この関数は、引数で指定された値の最初のインデックスを返します。beg から end インデックスまで検索を開始します。 insert(i, a) :- この関数は、arguments(a) で指定された値を、arguments で指定されたインデックス (i) に挿入します。 Remove() :- この関数は、引数で指定された値の最初の出現を削除します。 count() :- この関数は、引数で指定された値の出現数をカウントします。

Python3

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

複雑さの分析については終わりを参照してください。

例 4:両端キューのサイズ

len(dequeue) :- デキューの現在のサイズを返します。

Python3

# Python Program to demonstrate> # how to find size of a 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> (> ' The deque after deleting from right is: '> , end> => '')> print> (de)> # printing current size of deque> print> (f> 'Size of Deque: {len(de)}'> )> # This code is contributed by Susobhan Akhuli>

出力

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] :- deque の先頭要素には、de[0] によるインデックス付けを使用してアクセスできます。 Deque[-1] :- deque の後方要素には、de[-1] によるインデックス付けを使用してアクセスできます。

Python3

# Python Program to demonstrate> # accessing the front and back of a 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> ])> # This code is contributed by Susobhan Akhuli>

出力

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() :- この関数は、引数で指定された数だけ両端キューを回転します。指定した数値が負の場合、左方向に回転します。それ以外の場合は右方向に回転します。

Python3

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

複雑さの分析については終わりを参照してください。

複雑さの分析:

メソッド	時間計算量	補助スペース
追加()	○(1)	○(1)
appendleft()	○(1)	○(1)
ポップ（）	○(1)	○(1)
ポップレフト()	○(1)	○(1)
インデックス(ele、beg、end)	の上）	○(1)
挿入(i, a)	の上）	○(1)
取り除く（）	の上）	○(1)
カウント（）	の上）	○(1)
ただ（デキュー）	○(1)	○(1)
デク[0]	○(1)	○(1)
デク[-1]	○(1)	○(1)
拡張(反復可能)	矢印)	○(1)
extendleft(反復可能)	矢印)	○(1)
逆行する（）	の上）	○(1)
回転()	矢印)	○(1)