本記事は、ソフトバンクパブリッシングから発行されている「定本 Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)」を参考にPythonでアルゴリズムとデータ構造について学習していきます。
今回は、データ構造として有名なキュー(待ち行列)について学んでいきます。
キューとは
キュー(Queue)とは待ち行列を意味し、一方の端でのみ挿入が行われ、また反対の端で削除が行われるものを差し、一般的にFIFO(First In First Out:先入れ先出し)のデータ構造のものを言います。。
なお、待ち行列に入れることをEnqueue、待ち行列から取り出すことをDequeueといいます。
身近なところでキューの概念が使われているのが、TCPやUDPなどのネットワーク通信で使われるソケットライブラリです。
ソケットはポート番号を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()呼び出しで、キューが空になっていることが確認できます。