Help us understand the problem. What is going on with this article?

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

概要

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

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away