循環配列を用いたキューの実装

概要

キュー（Queue）は先入れ先出し（First In First Out）を実現するためのデータ構造です。無限の長さを持つ配列があれば末尾に要素を追加していくだけでキューを実装できますが、実際には有限長の配列でキューを実装する必要があります。有限長の配列に要素を追加する際、配列の末尾がすでに埋まっていたら配列の先頭から格納していく必要があるため、剰余算術を用いて格納位置を決定します。下記に実装例を示します。

実装例

class MyCircularQueue(object):
    def __init__(self, k):
        # サイズkの配列を用いてキューを実装する
        self.k = k
        self.q = [None] * k
        self.first = 0 # 要素の先頭を表すindex
        self.last = 0  # 要素の末尾を表すindex

    # キューの末尾にデータを追加する
    def enQueue(self, value):
        if self.isFull():
            return False
        else:
            # 剰余をindexとして返す
            idx = self.last % self.k
            self.q[idx] = value
            self.last += 1
            return True

    # キューの先頭からデータを取り出す
    def deQueue(self):
        if self.isEmpty():
            return None
        else:
            # 剰余をindexとして返す
            idx = self.first % self.k
            val = self.q[idx]
            self.q[idx] = None
            self.first += 1
            return val

    # キューの先頭のデータを参照する
    def front(self):
        idx = self.first % self.k
        return self.q[idx]

    # キューの末尾のデータを参照する
    def rear(self):
        idx = (self.last - 1) % self.k
        return self.q[idx]

    # キューが空かどうか判定する
    def isEmpty(self):
        return self.first == self.last

    # キューが一杯かどうか判定する
    def isFull(self):
        return self.last - self.first == self.k

注意点

本来はキューが一杯になったら配列の長さを拡張する等の対応を行うことが望ましいですが、本記事では簡略化のため省略しています。

参考