Queueを自作する

今日はキューを自作した。

自作したQueue

pythonのリストを使ってリングバッファで実装してみる。
Stackと違って、どこまでも伸びていってしまうので、端と端をつなぐことでメモリの無駄遣いを抑える。
作成したクラスはこんな感じ。

Sackはいくつ要素が入っているか表す変数がtopの一つだったのに対して、Queueはheadとtailの二つとなった。
tail - headがキューされている要素数になる。

# --- coding: utf-8 ---

import sys

class Queue():
    def __init__(self):
        self.queue = []
        self.head = 0
        self.tail = 0
        self.MAX = 101


    def push(self, x):
        """
        このメソッドが呼ばれた時点でheadとtailがMAX以上離れていたら、
        self.is_full()でexitする。
        """
        if self.is_full():
            print("This queue is full!!")
            sys.exit()
    
        self.queue.append(x)
        self.tail += 1
        if (self.tail) == self.MAX:
            self.tail %= self.MAX

    def pop(self):
        """
        このメソッドが呼ばれた時点でheadとtailが同じなら、
        self.is_null()でexitする。
        """
        if self.is_null():
            print("This queue is null!!")
            sys.exit()

        tmp = self.queue[self.head]
        self.head += 1

        if (self.head + 1) == self.MAX:
            self.head %= self.MAX

        return tmp

    def is_null(self):
        if self.tail == self.head :
            return True
        else:
            return False

    def is_full(self):
        if self.head == (self.tail + 1) % self.MAX :
            return True
        else:
            return False

動作確認

①正常系

if __name__ == '__main__':
    queue = Queue()

    queue.push("1")
    queue.push("1")
    print(queue.pop())
||

②キューをいっぱいなのにpushしてexitさせる異常系
>|python|
if __name__ == '__main__':
    queue = Queue()

    for i in range(60):
        queue.push("1")
    for i in range(15):
        queue.pop()
    for i in range(60):
        queue.push("1")

③キューが空なのにpopしてexitさせる異常系

if __name__ == '__main__':
    queue = Queue()


    queue.push("1")
    print(queue.pop())
    print(queue.pop())

感想

リングバッファがむずい。格納できる要素の最大数がちょっと怪しいですね。
amazonのキューイングシステムなんかは一体どんなサイズのバッファを取ってるのか、恐ろしくなりました...。すごいなぁ。