Python での Deque – 例を含むチュートリアル

Python 開発者であれば、deque、つまり「両端キュー」について聞いたことがあるでしょう。これは、アプリケーションの効率を高め、パフォーマンスを高速化できる強力なツールです。

deque は、コンテナーの両端からの迅速な追加およびポップ操作を提供する特殊なコンテナー データ型です。これは、コンピューティングにおける一般的なリストのようなデータ型であるキューとスタックを実装するための貴重なツールになります。

これは、さまざまなアプリケーションに非常に役立つ、低レベルで高度に最適化されたデータ構造です。Python プログラマーにとって、deque は、必ず備えておきたいツールの 1 つです。

Deque の詳細と、それをPython コードに実装する方法については、読み続けてください。

目次

• デクとは何ですか?
  • Python Deque の機能
  • Deque のアプリケーション
• Deque を作成および初期化する方法
  • deque() 関数の使用
  • 要素を使用した両端キューの初期化
• 一般的なデキュー操作を実行する方法
  • Deque への要素の追加
  • 複数のデータ要素を両端キューに追加する
  • Deque からの要素の削除
  • Deque からのすべての要素の削除
  • Deque の要素へのアクセス
  • Deque の要素の変更
• Deque をキューとして操作する方法
  • append() メソッドと Popleft() メソッドの使用
  • デキューキューが空かどうかの確認
• Deque をスタックとして使用する
  • append() メソッドと Pop() メソッドの使用
  • 空の両端キュー オブジェクトのチェック
• 制限付き DEQUE とは何ですか?
  • • 入力制限されたデキュー
    • 出力制限付きデキュー
• これを終わりにしましょう

デクとは何ですか?

Python やコンピューター プログラミング全般に慣れていない場合は、deque とは何なのか疑問に思うかもしれません。Deque は「double-ended queue」の略で、キューの両端から要素を追加および削除できるデータ構造です。

これは通常のキューに似ていますが、キューの前と後ろの両方で要素を追加したり削除したりできるという柔軟性が追加されています。これが可能なのは、Python の両端キューが二重リンク リストとして実装されているためです。

Python では、両端キューは、両端キュー クラスを提供するコレクション モジュールを使用して実装されます。このクラスは、両端キューに要素を追加したり、両端キューから要素を削除したりするためのメソッドを多数提供します。

また、両端キューの回転や完全なクリアなど、他の便利な操作のための関数も提供します。

Python Deque の機能

通常のリストの追加およびポップ操作の時間計算量は O(n) ですが、デキューの時間計算量は O(1) です。これにより、これらの読み取りおよび書き込み操作が大幅に高速化され、メモリ効率が向上します。

知っておくべき Python の deque 機能をさらにいくつか紹介します。

• これは可変のデータ構造です。

• 複数のデータ型 (整数、タプル、配列など) を保存できます。

• インデックス作成はサポートされますが、スライス操作はサポートされません。

• インプレース並べ替えはサポートされていません

• in、sorted()、len()、reverse()などの一般的な組み込みの反復可能な関数と操作をサポートします。

Deque のアプリケーション

Deque はさまざまな理由で役立ちます。たとえば、これらはキューやスタックの実装に使用できます。これらはどちらもコンピューター サイエンスで一般的なデータ構造です。

また、ストリーミング アプリケーションやデータへの高速アクセスが必要なシステムなどで、データをリアルタイムで効率的に処理するために使用することもできます。

デキューは、キューとスタックに使用されるだけでなく、幅優先検索アルゴリズムの実装にも使用できます。これらは、より大きなシーケンス内の項目のスライディング ウィンドウを維持するのにも役立ちます。

Deque を作成および初期化する方法

コレクション モジュールの組み込み関数を使用して両端キューを作成できます。このデータ構造を作成して埋める方法を詳しく見てみましょう。

deque() 関数の使用

Python で両端キューを作成するには、コレクション モジュールの組み込みのdeque()関数を使用できます。この関数は、両端キューの実装に使用できる新しい空の両端キュー オブジェクトを返します。

次に、空の両端キュー オブジェクトを作成する方法の例を示します。

from collections import deque 

my_deque = deque() 

また、反復可能 (リスト、タプルなど) をdeque()関数に渡すことによって、初期要素を含む両端キューを作成することもできます。両端キューは、反復可能内の要素を使用して左から右に初期化されます。

以下に例を示します。

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

要素を使用した両端キューの初期化

さまざまな方法を使用して、要素を含む空の両端キューを初期化することもできます。これを行う 1 つの方法は、append() メソッドとappendleft()メソッドを使用して、それぞれ右側と左側から両端キューに要素を追加することです。

以下に例を示します。

from collections import deque

#Initialize the empty deque
my_deque = deque()
print(my_deque)

#Add Values to the deque
my_deque.append(1) 
my_deque.append(2) 
my_deque.appendleft(3) 

print(my_deque)

このコードを実行すると、両端キューには要素[3, 1, 2] が含まれます。

要素を使用して両端キューを初期化するもう 1 つの方法は、要素のリストをdeque()関数に渡すことです。

以下に例を示します。

from collections import deque

my_deque = deque([1, 2, 3]) 

このコードを実行すると、要素[1, 2, 3]を含む両端キュー オブジェクトが作成されます。

全体として、Python での両端キューの作成と初期化は簡単で、組み込みのdeque()関数を使用して実行できます。append()メソッドとappendleft()メソッドを使用して空の両端キューに要素を追加することによってもこれを行うことができます。

一般的なデキュー操作を実行する方法

Python では、両端キュー オブジェクトに対して実行できる操作が多数あります。最も人気のあるものをいくつかチェックしてみましょう。

Deque への要素の追加

append()メソッドとappendleft()メソッドを使用して、 Pythonデキューに要素を追加できます。append ()メソッドは両端キューの右端に要素を追加し、appendleft()メソッドは両端キューの左端に要素を追加します。

以下に例を示します。

import collections 

# Create an empty deque 
my_deque = collections.deque() 

# Add elements to the deque 
my_deque.append(1) 
my_deque.appendleft(2) 
my_deque.append(3) 

print(my_deque) 

# Output: 
deque([2, 1, 3])

複数のデータ要素を両端キューに追加する

データ要素を 1 つずつ両端キューに追加したくない場合は、extend()関数またはextendleft()関数を使用してプロセスを高速化できます。これらの関数は反復可能を受け取り、反復可能の内容をそれぞれ両端キューの末尾または左端に追加します。

以下に例を示します。

from collections import deque

my_list = [1, 2, 3, 4, 5] 
my_deque = deque(my_list)

#Creating a tuple and list
cont = (11, 12, 13, 14)
full = [10,20,30]

#Extending the deque from the right
my_deque.extend(cont)
print(my_deque)

#Extending the deque from the left
my_deque.extendleft(full)
print(my_deque)

上記のコードでは、extend()関数は、 contタプル内の複数の値を両端キューの末尾に追加します。次に、extendleft()関数は、完全なリスト内の複数のデータ要素を両端キューの左端に追加します。

Deque からの要素の削除

Pop()メソッドとPopleft()メソッドを使用して、Python デキューから要素を削除できます。Pop ()メソッドは両端キューの右端の要素を削除して返します。一方、popleft()メソッドは両端キューの左端の要素を削除して返します。

以下に例を示します。

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

#Remove elements from the deque 
my_deque.pop() 
my_deque.popleft() 

print(my_deque) 

# Output: deque([2, 3, 4])

また、 remove()関数を使用して、両端キューから特定の値を削除することもできます。この関数は、指定された値の最初の出現を両端キューから削除します。

以下に例を示します。

import collections 

#Create a deque with some elements 
my_deque = collections.deque([1, 2, 1, 4, 5]) 

#Remove elements from the deque 
my_deque.remove(1)

print(my_deque) 

# Output: deque([2, 1, 4, 5])

要素が見つからない場合、Python は ValueError を返します。

Deque からのすべての要素の削除

Deque からすべての要素を削除して空の状態に戻すには、clear()関数を使用できます。仕組みは次のとおりです。

from collections import deque 

#Create a deque with some elements 
my_deque = deque([1, 2, 1, 4, 5]) 

#Remove all elements from the deque 
my_deque.clear()

print(my_deque) 

# Output: 
deque([])

Accessing Elements of a Deque

You can access elements of a Python deque using the indexing operator []. You can also use a negative value in the indexing operator to access the deque elements from the right.

The indexing starts from 0 for the leftmost element and -1 for the rightmost element. Here’s an example:

import collections 

# Create a deque with some elements 
my_deque = collections.deque([1, 2, 3, 4, 5]) 

# Access elements of the deque 
print(my_deque[0]) 
# Output: 1 

print(my_deque[-1]) 
# Output: 5 

Modifying Elements of a Deque

You can modify elements of a Python deque using the indexing operator “[]” and the assignment operator “=“. Here’s an example:

from collections import deque

# Create a deque with some elements 
my_deque = deque([1, 2, 3, 4, 5]) 
print(my_deque)

# Modify elements of the deque 
my_deque[0] = 10 
my_deque[-1] = 50 

print(my_deque) 

In the above code, the indexing operator changes the first and last elements of the deque to 10 and 50 respectively.

These are the basic operations you can perform on a deque object in Python. With these operations, you can efficiently implement various data structures such as queues, stacks, and more.

How to Work with a Deque as a Queue

You can use a deque in Python to implement a queue data structure. A queue is an abstract data type that operates on a first in first out (FIFO) basis.

What this means is that you can append new items from one end of the queue and push out old items from the other end.

A good way to explain this is a line at a store. Typically, the first person to arrive will be at the head of the line and will be attended to first.

New arrivals will have to head to the back of the line and wait their turn. So, the first in will be the first answered, while the last in will be the last attended to.

Here’s how you can use a deque to implement queues.

Using append() and popleft() Methods

両端キューをキューとして使用するには、append()メソッドを使用して要素を両端キューの右端に追加します。さらに、popleft()メソッドを使用して、両端キューの左端から要素を削除できます。

これは、Python でキューを実装する非常に効率的な方法です。以下に例を示します。

from collections import deque 

queue = deque() 
queue.append(1) 
queue.append(2) 
queue.append(3) 

print(queue) 
# Output: deque([1, 2, 3]) 

x = queue.popleft() 
print(x) 
# Output: 1 

print(queue) 
# Output: deque([2, 3]) 

ご覧のとおり、append()メソッドは両端キューの右端に要素を追加し、popleft()メソッドは両端キューの左端から要素を削除します。

これはまさにキューの実装に必要なものです。

デキューキューが空かどうかの確認

デキューが空かどうかを確認するには、not演算子を使用できます。以下に例を示します。

from collections import deque 

queue = deque() 
if not queue: 
   print("Queue is empty") 
else: 
   print("Queue is not empty") 

これにより、両端キューが空であるため、 「 Queue is empty 」が出力されます。両端キューに要素を追加すると、それは空ではなくなります。

結論として、Python で両端キューをキューとして使用することは非常に効率的で、実装が簡単です。

Deque をスタックとして使用する

キューと同様に、スタックもデータの整理に使用できる抽象データ型の例です。キューとは異なり、スタックは後入れ先出し (LIFO) 方式で動作します。

これは、両端キュー内の最後の要素が最初に出力される要素になることを意味します。基礎となるデータ構造を使用してこれを実装する方法を次に示します。

append() メソッドと Pop() メソッドの使用

Deque をスタックとして使用する場合、 append()メソッドを使用してスタックの先頭に要素を追加できます。このメソッドは、要素を両端キューの右端に追加します。

同様に、 pop()メソッドを使用してスタックの最上位から要素を削除できます。このメソッドは、両端キューの右端の要素を削除して返します。

たとえば、「 my_stack 」という両端キューがあり、スタックの先頭に要素を追加するとします。次のコードを使用できます。

 my_stack.append(5) 

これにより、要素 5 がスタックの一番上に追加されます。

スタックから最上位の要素を削除したい場合は、pop() メソッドを使用できます。

bal = my_stack.pop() 

print(bal)
# Output: 5

これにより、両端キューの右端の要素 (この場合は 5) が削除されて返されます。

空の両端キュー オブジェクトのチェック

ブール演算子「not」を使用して、両端キュースタックが空かどうかを確認できます。deque が空の場合、「not my_deque 」はTrueを返します。それ以外の場合は、 Falseを返します。

たとえば、「my_deque」という両端キュー スタックがあり、それが空かどうかを確認したいとします。次のコードを使用できます。

if not my_deque: 
   print("The deque is empty") 

else: 
   print("The deque is not empty") 

これにより、両端キューが空の場合、 「両端キューが空です」と出力されます。空でない場合、出力は「両端キューが空ではありません」となります。

Deque をスタックとして操作する場合、スタックが空かどうかを追跡することが重要です。空のスタックから要素をポップしようとすると、 IndexError が発生します。

制限付き DEQUE とは何ですか?

制限付きデキューは、両端キューの両端でのデータの追加およびポップ操作にいくつかの制限が課された両端キューです。制限された両端キューには主に 2 つのタイプがあります。入力制限付きデックと出力制限付きデック

それらを見てみましょう:

入力制限されたデキュー

入力制限された両端キューを使用すると、両端キューの両端からデータ要素をポップまたは削除できます。ただし、データ要素は両端キューの一方の端からのみ挿入できます。

これは、メモリに制約があるアプリケーションで非常に役立ちます。これを使用すると、両端キューのいずれかの端からデータを破棄する機能を維持しながら、データ要素を時系列に追加できます。

出力制限付きデキュー

出力制限された両端キューを使用すると、両端キューの両端からデータを挿入できます。ただし、項目を削除できるのは、フロントエンドと呼ばれる両端キューの一方の端からのみです。

出力制限されたデキューは、FIFO データ構造を実装する必要があるが、両端からデータを追加する機能が必要な場合に非常に役立ちます。

これを終わりにしましょう

ここまでで、Python の deque モジュールと、それを使用して効率的なキューとスタックを実装する方法について十分に理解できたはずです。

Deque は、従来のリストに比べて多くの利点を提供する多用途のデータ構造です。これらの利点は、メモリ効率の高い追加およびポップ操作に関して明らかです。

スタックまたは両端キューを実装する必要がある場合にも、これらは優れた選択肢です。deque を使用する主な利点には次のようなものがあります。

• デキューの両端からの効率的な O(1) 追加およびポップ操作

• デキューの最初と最後の要素への高速 O(1) アクセス

• スレッドセーフなアトミック操作の組み込みサポート

• 両端キュー内の要素を挿入、削除、回転するための柔軟な方法

全体として、deque モジュールは、より効率的で保守しやすい Python コードを作成するのに役立つ強力なツールです。小規模なスクリプトに取り組んでいる場合でも、大規模なプロジェクトに取り組んでいる場合でも、従来のリストやその他のデータ構造の代替として両端キューを検討する価値は間違いなくあります。

Python についてさらに学ぶ準備ができました。以下の再生リストをチェックしてください。