순환 배열을 이용한 큐 구현

개요

큐(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

주의점

본래는 큐가 가득 차면 배열의 길이를 확장하는 등의 대응을 실시하는 것이 바람직합니다만, 본 기사에서는 간략화를 위해 생략하고 있습니다.

참고