Engineering Note

プログラミングなどの技術的なメモ

キュー(待ち行列) (Pythonによるアルゴリズムとデータ構造)

queue

本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonアルゴリズムとデータ構造について学習していきます。

今回は、データ構造として有名なキュー(待ち行列)について学んでいきます。

 

 

キューとは

キュー(Queue)とは待ち行列を意味し、一方の端でのみ挿入が行われ、また反対の端で削除が行われるものを差し、一般的にFIFO(First In First Out:先入れ先出し)のデータ構造のものを言います。。

なお、待ち行列に入れることをEnqueue待ち行列から取り出すことをDequeueといいます。

身近なところでキューの概念が使われているのが、TCPUDPなどのネットワーク通信で使われるソケットライブラリです。

ソケットはポート番号をbind()したら、listen()で接続要求を待ちます。

listen()で指定したbacklog(接続要求キューのサイズ)までキューに溜め込み、accept()でキューから取り出されます。

 

キューの実現方法

今回はリストのサイズを決めて、その中でキューを実現します。

限られたメモリの中で効率よく待ち行列を実現するには、リストをリング状にした、リングバッファというものにします。

またリングバッファを用いるためには、リストの1つを必ず空の状態にしておく必要があり、これによりキューが空なのか、または一杯なのかを判断します。

 

Pythonでキューを作ってみる

それでは、Pythonでキューを実装してみます。

 

# my_queue.py
class Queue:
    def __init__(self, size=10):
        self.entries = [None for _ in range(size)]
        self.size = size
        self.front = self.rear = 0

    def next(self, n):
        return (n + 1) % self.size

    def enqueue(self, n):
        if self.front == self.next(self.rear):
            print("queue is full")
            return False
        self.entries[self.rear] = n
        self.rear = self.next(self.rear)

    def dequeue(self):
        if self.front == self.rear:
            print("queue is empty")
            return False
        n = self.entries[self.front]
        self.front = self.next(self.front)
        return n

q = Queue(4)
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
q.enqueue(4)

print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
q.dequeue()

 

frontとrearはともに0で初期化をしておき、front == rearの状態だとキューは空の状態であり、rearに1を加算しサイズで除算した値(リング状にするため)がfrontと同値であれば、キューは一杯であることになります。

 

動作確認

それでは上記で作成したスクリプトを実行してみます。

 

 > python my_queue.py
 queue is full
 1
 2
 3
 queue is empty

 

サイズ4のリストを作成し、4つ目のデータを追加した際に一杯になります。

その後、データを追加した順に取り出して、4回目のdequeue()呼び出しで、キューが空になっていることが確認できます。

 

参考書籍

定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)