LoginSignup
4

More than 3 years have passed since last update.

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

Last updated at Posted at 2019-10-14

概要

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

StackによるQueueの実装

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

Push

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

Screen Shot 2019-10-14 at 17.30.40.png

Pop

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

Screen Shot 2019-10-14 at 17.30.53.png

実装例

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の際は一方のキューにそのまま要素を追加していきます。

Screen Shot 2019-10-14 at 18.01.30.png

Pop

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

Screen Shot 2019-10-14 at 18.01.42.png

実装例

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です。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4