PythonでのDeque

Dequeは基本的にスタックとキューの構造を一般化したもので、左から右に初期化されます。リストオブジェクトを使用して両端キューを作成します。ポップと追加にO（1）時間計算量を提供します。

Dequeisは、コレクションにある標準ライブラリクラスです。 モジュール。

最初に使用するには、コレクションの標準ライブラリモジュールをインポートする必要があります。

import collections

このセクションでは、Dequeクラスのいくつかの関数を確認します

Dequeの追加機能

追加には2つの異なるタイプがあります。 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'])

DequeのPopping関数

追加と同様に、ポップ関数には2つの異なるタイプがあります。 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（）メソッドは、Deque内のアイテムの頻度をカウントします。

サンプルコード

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関数についてはすでに説明しました。挿入と削除に関連する別の2つの方法があります。 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に複数の要素を追加するために使用されます。リストやタプルなどのコレクションを使用して、複数の値を提供できます。拡張機能には2つのタイプがあります。 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])

Dequeの反転および回転機能

reverse（）メソッドを使用して、デキューアの順序を逆にすることができます。 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'])