LeetCode / Implement Stack using Queues, Implement Queue using Stacks

重要なデータ構造の1つにStack（スタック）とQueue（キュー）がありますが、これを実装しろという問題を取り上げます。

と言っても、こちらの解説記事にあるように、スタックもキューも配列で表現することができ、データ構造としては特別なものではありません。重要なのは以下の使われ方の違いです。

スタック データ構造に入っている要素のうち、最後に push した要素を取り出す
キュー データ構造に入っている要素のうち、最初に push した要素を取り出す

上記メソッドを有するStack class, Queue classを実装します。

Implement Stack using Queues

https://leetcode.com/problems/implement-stack-using-queues/

Implement the following operations of a stack using queues.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.

Example:

MyStack stack = new MyStack();

stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false

Notes:

You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

まずはstackの実装から。問題タイトルにもあるように、queueを使ってstackを実装することが求められています。

queueを使うということは、可能な操作も限定されます。only push to back, peek/pop from front, size, and is empty operations are validとあるように、pushは後ろから、popは前からに限定されます。

誤答

一応やっておくと、問題の意図を無視してstackを使ってしまっても、テストは通ってしまいます。
ただ当然ながら、stackを使ってstackを作っても何の意味もないですね。
pythonではlistがstackにあたる挙動を示します。

class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = []
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        self.stack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        return self.stack.pop()
        

    def top(self) -> int:
        """
        Get the top element.
        """
        return self.stack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        return len(self.stack) == 0

解法

この問題ではqueueを使ってstackを実装することを求められていますが、ポイントはpop。繰り返しになりますが、stackでは最後にpushされた要素を取り出しますが、queueでは最初にpushされた要素を取り出します。

pythonではqueue.popleft()で最初にpushされた要素を取り出せます。popleftを使って、pushを実行した際に、後にpushされた要素が先頭にくるようにqueueを並び替えるのが以下の解法です。

class MyStack:

    def __init__(self):
        self.queue = collections.deque()
        

    def push(self, x: int) -> None:
        q = self.queue
        q.append(x)
        for _ in range(len(q)-1):
            q.append(q.popleft())
        

    def pop(self) -> int:
        return self.queue.popleft()
        

    def top(self) -> int:
        return self.queue[0]
        

    def empty(self) -> bool:
        return len(self.queue) == 0

時間計算量がpushで、popではかかることになります。

ちなみに、本問題の要求のもとでは使えませんが、以下記事にあるようにcollections.deque()にはpopメソッドも存在し、時間計算量で後方から要素を取り出し削除することが可能です。

note.nkmk.me

Implement Queue using Stacks

https://leetcode.com/problems/implement-queue-using-stacks/

Implement the following operations of a queue using stacks.

push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.

Example:

MyQueue queue = new MyQueue();

queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false

Notes:

You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

次に、Queueの実装です。今度はstackを使ってqueueを実装することを求められています。

これも可能な操作が限定されます。only push to top, peek/pop from top, size, and is empty operations are validとなっています。つまりpush, peek, popについてはlist.append(x), list[-1], list.pop()のみが許容されていることになります。

解法

2つstackを用意し、pushの際はinStackに格納、peekやpopの際はinStackの要素を逆順にして格納したoutStackを用意し、処理を行うのが以下の解法です。

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.inStack, self.outStack = [], []
        

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.inStack.append(x)
        

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.peek()
        return self.outStack.pop()
        

    def peek(self) -> int:
        """
        Get the front element.
        """
        if(self.outStack == []):
            while(self.inStack != []):
                self.outStack.append(self.inStack.pop())
        return self.outStack[-1]
        

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return len(self.inStack) == 0 and len(self.outStack) == 0