[Python] スタックでキューを作る

スタックとは、ＬIFO のADTで、データを挿入する push、一番最後に挿入したデータを取り出す pop というメソッドを持ちます。

キューとは、FIFO の ADT で、データを挿入する enqueue 、一番最初に挿入したデータを取り出す dequeue というメソッドを持ちます。

スタックを2つ組み合わせることで、キューを作ることができます。

まずは enqueue のためのスタックを用意し、5, 2, 10 を挿入しました。

スタックなので pop で値を取り出すと 5 が取り出されます。

ここで、dequeue のためにもう一つスタックを用意し、このスタックが空の場合は enqueue のスタックから値を全て pop して挿入することにします。

上の状態にこの操作を適用すると、以下のような状態になります。

この状態であれば、pop で最初に挿入した値を取り出すことができます。

コードにまとめます。

class Stack(object):

    def __init__(self):
        self.stack = []
    
    # O(1)
    def push(self, data):
        self.stack.append(data)
    
    # O(1)
    def pop(self):
        data = self.stack[-1]
        del self.stack[-1]
        return data
    
    # O(1)
    def peek(self):
        data = self.stack[-1]
        return data

    def __len__(self):
        return len(self.stack)

class Queue(object):

    def __init__(self):
        self.enqueue_stack = Stack()
        self.dequeue_stack = Stack()

    def enqueue(self, data):
        self.enqueue_stack.push(data)

    def dequeue(self):
        if len(self.enqueue_stack) == 0 \
            and len(self.dequeue_stack) == 0:
            raise Exception('Empty Queue')

        if len(self.dequeue_stack) == 0:
            while len(self.enqueue_stack) != 0:
                self.dequeue_stack.push(self.enqueue_stack.pop())

        return self.dequeue_stack.pop()


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

    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)

    # 1
    print(queue.dequeue())
    # 2
    print(queue.dequeue())
    # 3
    print(queue.dequeue())
    # 4
    print(queue.dequeue())
    # Exception: Empty Queue
    print(queue.dequeue())

再帰でも書けます。

再帰を使うと、見かけ上のスタックは一つになります。

ただし、関数の再帰的な呼び出しでスタックを使うので、実質的には上のループを使う場合と同様です。

class Stack(object):

    def __init__(self):
        self.stack = []
    
    # O(1)
    def push(self, data):
        self.stack.append(data)
    
    # O(1)
    def pop(self):
        data = self.stack[-1]
        del self.stack[-1]
        return data
    
    # O(1)
    def peek(self):
        data = self.stack[-1]
        return data

    def __len__(self):
        return len(self.stack)

class Queue(object):

    def __init__(self):
        self.stack = Stack()

    def enqueue(self, data):
        self.stack.push(data)

    def dequeue(self):
        if len(self.stack) == 0:
            raise Exception('Empty Queue')

        if len(self.stack) == 1:
            return self.stack.pop()

        popped = self.stack.pop()

        dequeued = self.dequeue()
        self.stack.push(popped)

        return dequeued


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

    queue.enqueue(1)
    queue.enqueue(2)
    queue.enqueue(3)
    queue.enqueue(4)

    # 1
    print(queue.dequeue())
    # 2
    print(queue.dequeue())
    # 3
    print(queue.dequeue())
    # 4
    print(queue.dequeue())
    # Exception: Empty Queue
    print(queue.dequeue())