225. Implement Stack using Queues

문제

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise. Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid. Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Follow-up: Can you implement the stack using only one queue?

예제 입출력

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

참고

You can read the full description here.

풀이 1

접근법

1. 파이썬 라이브러리 큐를 이용합니다.
2. 두 개의 큐 a, b를 사용합니다. a는 값을 보관하는 용으로 사용하고, b는 a에서 뺀 값을 담아두는 용으로 사용합니다.
3. pop 연산 시 큐 a의 마지막 값을 뽑을 때까지 큐 a의 값을 b로 옮기고, a의 마지막 값을 리턴합니다.

구현 코드

from queue import Queue

class MyStack:

    def __init__(self):
        self.a, self.b = Queue(), Queue()
        return

    def push(self, x: int) -> None:
        self.a.put(x)
        return

    def pop(self) -> int:
        while (self.a.qsize() > 1):
            self.b.put(self.a.get())
        res = self.a.get()
        self.a, self.b = self.b, self.a
        return res

    def top(self) -> int:
        res = self.pop()
        self.a.put(res)
        return res

    def empty(self) -> bool:
        return self.a.empty()

풀이 2

접근법

1. pop 연산 시 큐 b로 받는 대신, 큐 a로 바로 받아줍니다.

구현 코드

from queue import Queue

class MyStack:

    def __init__(self):
        self.a = Queue()
        return

    def push(self, x: int) -> None:
        self.a.put(x)
        return

    def pop(self) -> int:
        qsize = self.a.qsize()
        while (qsize > 1):
            qsize -= 1
            self.a.put(self.a.get())
        res = self.a.get()
        return res

    def top(self) -> int:
        res = self.pop()
        self.a.put(res)
        return res

    def empty(self) -> bool:
        return self.a.empty()

---

책에 있는 풀이

참고

원본 코드는 여기에서 확인하실 수 있습니다.

풀이 3

접근법

1. deque 을 이용합니다.
2. 이 풀이에서 pop은 $O(1)$ 로, push는 $O(n)$ 으로 동작합니다.
3. top 구현부에서 인덱싱을 사용하는데, 파이썬 deque에서 양끝값에 대한 접근은 $O(1)$ 로 동작합니다. 그래서 큐로 스택을 구현하라는 출제자의 의도에서 벗어날 수 있습니다. 참고링크

In addition to the above, deques support iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[0] to access the first element. Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

구현 코드

import collections

class MyStack:
    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        self.q.append(x)
        # 요소 삽입 후 맨 앞에 두는 상태로 재정렬
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self):
        return self.q.popleft()

    def top(self):
        return self.q[0]

    def empty(self):
        return len(self.q) == 0