Python でのキューの実装

  2. プログラミングのヒント
  3. Python のハウツー
  4. Python でのキューの実装
Aditya Raj 2023年6月21日
Python Python Queue
  1. Python でのキューの実装
  2. 要素をキューに追加する: エンキュー操作
  3. キューから要素を削除する: デキュー操作
  4. Python でのキューに対するその他の操作
  5. Python でのリストを使用したキューの実装
  6. Python でのリンク リストを使用したキューの実装
  7. Python で Collections モジュールを使用したキューの実装
  8. Python での最も効率的なキューの実装
Python でのキューの実装

Python でキューを使用して、先入れ先出し (FIFO) 操作を実行します。 この記事では、Python でキューを実装する 3つの異なる方法について説明します。

Python でのキューの実装

キューでは、さまざまな操作を実行できます。 最初にすべての操作の背後にある一般的な概念について説明し、その後、さまざまな構造を使用してキュー操作を実装します。

キューの最初の要素はフロント要素と呼ばれます。 同様に、キューの最後の要素は後方要素と呼ばれます。

たとえば、次の一連の数字をキューとして考えます。 1 はフロント要素、6 はリア要素です。

1,2,3,4,5,6

要素をキューに追加する: エンキュー操作

エンキュー操作では、チケット カウンターで人が列に加わるのと同じように、要素をキューに追加します。 新しく追加された要素は常に後方要素になります。

たとえば、上記のキューに数字 7 を追加すると、キューは次のようになります。

1,2,3,4,5,6,7

キューの最後にのみ要素を追加できることに注意することが不可欠です。

キューから要素を削除する: デキュー操作

デキュー操作では、チケット カウンターからチケットを受け取った後に人がキューから出るのと同じように、キューの先頭要素を削除します。

デキュー操作の後、フロント要素はキューから削除され、フロント要素の後ろの要素が新しいフロント要素になります。 たとえば、デキュー操作の後、前の例で使用されたキューは次のようになります。

2,3,4,5,6,7

デキュー操作では、フロント要素のみを削除できます。 キューは常に先入れ先出しの順序に従います。 したがって、最初にキューに追加された要素も最初に削除されます。

Python でのキューに対するその他の操作

キューに要素がない場合、それは空であると言われます。 さまざまな実装でキューが空かどうかを判断するために、さまざまなアプローチを使用できます。

キューの長さを調べる必要がある場合もあります。 また、この操作の実装についても説明します。

Python でのリストを使用したキューの実装

Python では、リストを使用して最も簡単にキューを実装できます。 リストを使用してキューを作成するには、

  1. 3つの属性を持つクラス Queue を定義します。
  2. リストの要素を格納する空のリスト data を定義します。
  3. front と rear の 2つの変数を初期化します。
  4. 変数を -1 に初期化して、キューが空であることを示します。

コード：

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

Queue オブジェクトを作成すると、空のリストが作成され、属性 data に割り当てられます。 その後、リストはキューの要素を格納します。

空のキューを作成したら、キューにさまざまな操作を実装します。

Python でキューが空かどうかを確認する

キューが空かどうかを確認するには、属性の front と rear が -1 に初期化されているかどうかを確認します。 このために、メソッド isEmpty() を定義します。

isEmpty() メソッドは、キューで呼び出されると、front 属性と rear 属性の値が -1 であるかどうかをチェックします。 はいの場合、キューが空であることを示す True を返します。 それ以外の場合、False を返します。

コード：

def isEmpty(self):
    if self.rear == -1 and self.front == -1:
        return True
    else:
        return False

Python でのリストを使用したエンキュー操作

要素をキューに挿入するには、最初にキューが空かどうかを確認します。 上で定義した isEmpty() メソッドを使用できます。

  1. キューが空の場合、append() メソッドを使用して、data 属性に含まれるリストに要素を追加します。 リストで呼び出されると、append() メソッドは要素を入力引数として取り、それをリストに追加します。
  2. リストに要素が 1つしかないので、属性 front と rear の値を 0 に更新します。 前 要素と 後 要素の両方がリスト データ のインデックス 0 に存在します。
  3. リストが空でない場合、最初に append() メソッドを使用して要素をリストに追加します。
  4. その後、追加要素がキューに追加されたことを示す rear 属性の値を増やします。

エンキュー操作では、キューから要素を削除しないため、front 属性の値は変更されません。

操作全体は、次のように Python で実装できます。

コード：

def enQueue(self, element):
    if self.isEmpty():
        self.data.append(element)
        self.front = 0
        self.rear = 0
    else:
        self.data.append(element)
        self.rear += 1

Python でのリストを使用したデキュー操作

まず、デキュー操作のためにキューが空かどうかを確認します。 はいの場合、操作できません。 それ以外の場合は、以下を実行します。

  1. キューに要素が1つしかないかどうかを確認します。 front と rear 属性が同じ値で、どれも -1 でないかどうかを確認できます。
  2. キューに要素が 1つしかない場合は、pop() メソッドを使用してキューの front インデックスの要素を削除し、それをユーザーに返します。 次に、属性 front と rear を -1 に更新し、キューが空になったことを示します。
  3. 上記の条件のいずれも True でない場合、キューには 2つ以上の要素があります。 このような場合、一時変数の front インデックスに要素を格納します。
  4. その後、属性 front の値をインクリメントします。これは、リスト内の次の要素が front 要素になったことを示します。
  5. 最後に、一時変数に格納されている値を返します。

コード：

def deQueue(self):
    if self.isEmpty():
        print("Queue is Empty. Cannot remove element")
    elif self.front == self.rear and self.front != -1:
        element = self.data[self.front]
        self.front = -1
        self.rear = -1
        return element
    else:
        element = self.data[self.front]
        self.front = self.front + 1
        return element

Python でキューの長さを調べる

Python でキューの長さを確認するには、次の手順を実行します。

  1. キューが空の場合、キューの長さは 0 になります。したがって、最初に isEmpty() メソッドを使用してキューが空かどうかを確認します。
  2. isEmpty() メソッドが True を返す場合、キューの長さとして 0 を返します。
  3. それ以外の場合、リストの長さは rear-front+1 として計算されます。

以下に示すように、これを length() メソッドで実装しました。

コード：

def length(self):
    if self.isEmpty():
        return 0
    return self.rear - self.front + 1

すべてのメソッドを実装しました。 すべての操作を 1 回実行してみましょう。

完全なコード:

class Queue:
    def __init__(self):
        self.data = list()
        self.front = -1
        self.rear = -1

    def isEmpty(self):
        if self.rear == -1 and self.front == -1:
            return True
        else:
            return False

    def enQueue(self, element):
        if self.isEmpty():
            self.data.append(element)
            self.front = 0
            self.rear = 0
        else:
            self.data.append(element)
            self.rear += 1

    def deQueue(self):
        if self.isEmpty():
            print("Queue is Empty. Cannot remove element")
        elif self.front == self.rear and self.front != -1:
            element = self.data[self.front]
            self.front = -1
            self.rear = -1
            return element
        else:
            element = self.data[self.front]
            self.front = self.front + 1
            return element

    def length(self):
        return self.rear - self.front + 1


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

出力：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is Empty. Cannot remove element

この例では、Python でリストを使用してキューを実装した後、いくつかのメソッドを実行しました。 コードをコピーして IDE に貼り付け、コードを試して、コードの動作をよりよく理解することができます。

Python でのリンク リストを使用したキューの実装

Python でリンクされたリスト のさまざまな操作については既に説明しました。 Python でのキューの実装に、リンクされたリスト操作を使用することもできます。

まず、data と next という 2つの属性を持つノードを定義します。

コード：

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

どこ：

  • data 属性は、キューの要素を格納するために使用されます。
  • next 属性は、キュー内の現在の要素の前にある要素を指すために使用されます。

Node を定義した後、front および rear 属性を持つ Queue クラスを定義します。

front 属性は、キューのリンク リスト内の front 要素を含むノードを指します。 同様に、rear 属性は、キューを含むリンク リスト内の rear 要素を含むノードを指します。

キューが空になるため、front および rear 属性は None に初期化されます。

コード：

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

Queue クラスが初期化されると、値 None を持つ front および rear 属性のみが含まれます。

Python でキューが空かどうかを確認する

キューが空かどうかを確認するには、front と rear 属性が None かどうかを確認します。 はいの場合、キューは空であると言えます。

この操作のために isEmpty() メソッドを定義します。 キューで呼び出されると、キューが空の場合、isEmpty() メソッドは True を返します。 それ以外の場合、False を返します。

コード：

def isEmpty(self):
    if self.front is None:
        return True
    return False

Python でのリンク リストを使用したエンキュー操作

エンキュー操作を実行するには、まずキューが空かどうかを確認します。 はいの場合、新しい要素を持つノードを front と rear 属性の両方に割り当てます。

それ以外の場合は、新しい要素を rear ノードの次のノードに追加します。 その後、新しいノードを rear ノードにします。

このようにして、新しい要素がキューに追加されます。

コード：

def enQueue(self, data):
    newNode = Node(data)
    if self.isEmpty():
        self.front = newNode
        self.rear = newNode
    else:
        self.rear.next = newNode

Python でのリンク リストを使用したデキュー操作

まず、デキュー操作のためにキューが空かどうかを確認します。 はいの場合、アンダーフローが発生したと言い、要素を削除することはできません。

それ以外の場合は、最初に front ノードの一時変数にデータを保存します。

その後、front ノードの next ノードを新しい front ノードとして作成します。 次に、del ステートメントを使用して、一時変数に格納されているフロント ノードを削除します。

このようにして、前のフロント ノードがキューから削除されます。 最後に、一時ノードに格納されている値を返します。

コード：

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        element = self.front
        nextFront = self.front.next
        self.front = nextFront
        value = element.data
        del element
        return value

Python でキューの長さを調べる

  1. キューの長さを見つけるために、最初に変数 count を 0 に初期化します。
  2. その後、while ループを使用して front ノードからキューのトラバースを開始します。 次のノードに移動するときに、count を 1 ずつ増やします。
  3. キューの最後、つまり None に到達したら、while ループを終了します。
  4. 最後に、キューの長さを示す count の値を返します。

コード：

def length(self):
    count = 0
    if self.front is None:
        return count
    else:
        temp = self.front
        while temp is not None:
            count += 1
            temp = temp.next
        return count

リンクされたリストを使用してすべてのキュー メソッドを実装しました。 動作をよりよく理解するために、操作を実行してみましょう。

完全なコード:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        if self.front is None:
            return True
        return False

    def enQueue(self, data):
        newNode = Node(data)
        if self.isEmpty():
            self.front = newNode
            self.rear = newNode
        else:
            self.rear.next = newNode

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            element = self.front
            nextFront = self.front.next
            self.front = nextFront
            value = element.data
            del element
            return value

    def length(self):
        count = 0
        if self.front is None:
            return count
        else:
            temp = self.front
            while temp is not None:
                count += 1
                temp = temp.next
            return count


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

出力：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Python で Collections モジュールを使用したキューの実装

Python でのキューの実装に collections モジュールを使用することもできます。

Collections モジュールは、Python でキューとスタックを実装するための deque (両端キュー) クラスを提供します。 次の import ステートメントを使用して、プログラムに deque クラスをインポートできます。

from collections import deque

キューを実装するクラス Queue を作成します。 以下に示すように、クラス内に deque オブジェクトを作成します。

コード：

class Queue:
    def __init__(self):
        self.data = deque()

Queue クラスがインスタンス化されると、キューの要素を格納するために空の deque オブジェクトが作成されます。

Python でキューの長さを確認する

キューの長さを確認するには、length() メソッドを定義します。 length() メソッド内で、len() 関数を使用して deque オブジェクトの長さを計算します。

len() 関数は deque オブジェクトを入力として受け取り、deque の長さを返します。 以下に示すように、キューの長さとして len() 関数の値を返します。

コード：

def length(self):
    return len(self.data)

Python でキューが空かどうかを確認する

キューの長さが 0 の場合、キューは空であると言えます。 以下に示すように、isEmpty() メソッドを定義できます。

コード：

def isEmpty(self):
    if self.length() == 0:
        return True
    return False

Python で要素をキューに入れる

要素をエンキューするために enQueue() メソッドを定義します。 enQueue() メソッドは、新しい要素を入力引数として受け取ります。

enQueue() メソッド内で、append() メソッドを使用して要素を deque オブジェクトに追加します。 deque オブジェクトで呼び出された append() メソッドは、新しい要素を入力引数として取り、それを deque オブジェクトに追加します。

コード：

def enQueue(self, x):
    self.data.append(x)

Python でのデキュー操作

deQueue() メソッドを定義して、要素をキューから削除します。 deQueue() メソッド内で、キューの deque オブジェクトに対して popleft() メソッドを呼び出します。

popleft() メソッドは、deque オブジェクトで呼び出されると、deque の先頭要素を削除します。 また、キューから削除された要素も返します。

また、return ステートメントを使用して deQueue() メソッドから popleft() メソッドによって返された値を返します。

コード：

def deQueue(self):
    if self.isEmpty():
        print("Queue is empty. Cannot remove element.")
    else:
        return self.data.popleft()

これで、コレクション モジュールを使用して Python でキューを実装するためのすべてのメソッドを実装しました。 実行全体を観察してみましょう。

完全なコード:

from collections import deque


class Queue:
    def __init__(self):
        self.data = deque()

    def length(self):
        return len(self.data)

    def isEmpty(self):
        if self.length() == 0:
            return True
        return False

    def enQueue(self, x):
        self.data.append(x)

    def deQueue(self):
        if self.isEmpty():
            print("Queue is empty. Cannot remove element.")
        else:
            return self.data.popleft()


myQueue = Queue()
print("Enqueuing element 10")
myQueue.enQueue(10)
print("Queue Length is:", myQueue.length())
print("Enqueuing element 20")
myQueue.enQueue(20)
x = myQueue.deQueue()
print("dequeued element:", x)
print("Queue Length is:", myQueue.length())
y = myQueue.deQueue()
print("dequeued element:", y)
z = myQueue.deQueue()

出力：

Enqueuing element 10
Queue Length is: 1
Enqueuing element 20
dequeued element: 10
Queue Length is: 1
dequeued element: 20
Queue is empty. Cannot remove element.

Python での最も効率的なキューの実装

この記事では、Python でキューを実装するための 3つのアプローチについて説明しました。

ここで説明したすべてのアプローチの中で、リストを使用してキュー要素を格納するのは最悪です。 このアプローチでは、要素がリストから削除されることはありません。

したがって、プログラムで使用しないことをお勧めします。 Python の初心者で、連結リストについて何も知らない場合にのみ使用してください。

外部モジュールの使用が許可されていない場合は、リンクされたリストを使用する Python キューの実装を使用できます。時間とメモリの効率が良いからです。 ただし、deque を使用するアプローチよりも遅くなります。

Python の最も効率的なキューの実装には、deque モジュール アプローチを使用する必要があります。 モジュールのソース コードは C で記述されており、実装では両端リンク リストを使用して deque オブジェクトを実装しているため、時間とメモリの点で最も効率的です。

この記事が、Python でのキューの実装を理解するのに役立つことを願っています。 より有益な記事をお楽しみに。

著者： Aditya Raj
Aditya Raj avatar Aditya Raj avatar

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub