[データ構造] キュー

キュー

キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し^[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー^[2]、取り出すことをデキュー^[3]という。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

ADTとしてのキューは、先入先出/FIFO/First In First Out でデータを保持する構造を持ち、キューにデータを挿入するenqueue、キューからデータを取り出す dequeue、次に取り出すデータを確認するpeek という基本的な操作を持ちます。

動的配列や連結リストを土台にして実装されます。

幅優先探索というアルゴリズムを実装する際に使われます。

プリンタへの出力処理や、ウィンドウシステムのメッセージハンドラ、プロセスの管理など、データを入力された順番通りに処理する必要がある処理に用いられる。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

enqueue

キューの一番最後に新しいデータを加えます。\( O(1) \) で実行できます。

dequeue

キューの一番最初のデータ（一番古いデータ、つまり一番最初に入ったデータ）を取り出します（先入先出/FIFO/First In First Out ）。 \( O(1) \) で実行できます。

取り出したデータはキューから削除されます。

peek

キューの一番最初のデータ（一番古いデータ、つまり一番最初に入ったデータ）を確認します。 \( O(1) \) で実行できます。

dequeueと異なり、データは削除されません。

キューの実装

Python でリストを持ちいてキューを実装してみます。

class Queue(object):

    def __init__(self):
        self.queue = []

    # O(1)
    def enqueue(self, data):
        self.queue.append(data)

    # O(N)
    def dequeue(self):
        data = self.queue[0]
        del self.queue[0]
        return data

    # O(1)
    def peek(self):
        data = self.queue[0]
        return data


if __name__ == '__main__':
    queue = Queue()
    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    
    # 1
    print(queue.peek())
    print(queue.dequeue())
    
    # 2
    print(queue.peek())
    print(queue.dequeue())
    
    # 3
    print(queue.peek())
    print(queue.dequeue())
    
    # IndexError
    print(queue.peek())
    print(queue.dequeue())

このコードで、それぞれの操作自体は想定通りに行われます。

しかしこのコードでは、enqueue peek は\( O(1) \) で行うことができますが、dequeue 、つまり先頭のデータの削除は Python のリストの性質上\( O(N)\)になってしまいます。

よって、Python でキューを扱うため、deque というモジュールが用意されており、このモジュールを使うことで dequeue の操作が\(O (1)\) で実行できます。