スタックによるキューの実装と、キューによるスタックの実装

10954 ワード
データ構造 Python 競技プログラミング アルゴリズム Python テキストリンク

概要

LIFO, FIFOを実現するデータ構造としてそれぞれスタックとキューが挙げられますが、本記事ではこれらの一方を用いてもう一方を実装する手法を紹介したいと思います。

StackによるQueueの実装

2つのスタックを用意し、いずれか一方に要素を格納します。ただしキューの要件であるFIFO(first in first out)を実現するため、もう一方のスタックを利用して古い要素が上に来るようにスタックに積み上げていきます。　

Push

  1. スタックS1に格納されている要素をスタックS2に移動
  2. 空になったスタックS1に新しい要素を格納
  3. スタックS2からスタックS1に要素を戻す

Pop

上記のPush操作によって最も古い要素がスタックS1のTopに位置しているので、そのままPopします。

実装例

2つのスタックを用いてキューを実装する
class MyQueue(object):
    def __init__(self):
        # 2つのスタックを用意する
        self.s1 = []
        self.s2 = []

    def push(self, x):
        # s1からs2に要素を移す
        while self.s1:
            self.s2.append(self.s1.pop())
        # 空になったs1に要素を追加する
        self.s1.append(x)
        # s2からs1に要素を戻す
        while self.s2:
            self.s1.append(self.s2.pop())

    def pop(self):
        return self.s1.pop()

    def peek(self):
        if len(self.s1) > 0:
            return self.s1[-1]
        else:
            return None

    def is_empty(self):
        return len(self.s1) == 0

補足

上記の例とは逆に、push時はそのままスタックに積み上げ、pop時に一方のスタックを利用して逆順にpopするようにしてもOKです。

QueueによるStackの実装

2つのキューを用意し、いずれか一方に要素を格納します。ただしスタックの要件であるLIFO(last in first out)を実現するため、もう一方のキューを利用して直前に格納された値をpopするようにします。

Push

Pushの際は一方のキューにそのまま要素を追加していきます。

Pop

  1. 一方のキューに格納されている要素をもう一方のキューに移動（ただし要素一つだけ残す）
  2. 残された要素を直近の要素として返す

実装例

2つのキューを用いてスタックを実装する

from collections import deque

class MyStack(object):
    def __init__(self):
        # 2つのキューを用意する
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x):
        if self.q1:
            self.q1.append(x)
        else:
            self.q2.append(x)

    def pop(self):
        # 要素を一つだけ残して一方から一方に移動し、最後に残った要素をpopする
        if self.q1:
            while len(self.q1) > 1:
                self.q2.append(self.q1.popleft())
            return self.q1.popleft()
        else:
            while len(self.q2) > 1:
                self.q1.append(self.q2.popleft())
            return self.q2.popleft()

    def top(self):
        if self.q1:
            return self.q1[-1]
        else:
            return self.q2[-1]

    def is_empty(self):
        return len(self.q1) == 0 and len(self.q2) == 0

補足

上記の例とは逆に、push時に一方のキューを利用して逆順にセットされるようにし、pop時はそのままキューから取り出すようにしてもOKです。