225. Implement Stack using Queues
232. Implement Queue using Stacks

---

225. Implement Stack using Queues

접근 방법

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

• queue 를 두 개 이용하여 stack 을 만드는 문제인데, queue 의 경우 데이터가 들어가는 장소와 나오는 장소가 달라 하나의 queue 만 이용하여도 stack 의 구현이 가능하기 때문에 하나의 queue 를 이용하여 stack 을 구현하였다.

class MyStack:

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

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

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

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

    def empty(self) -> bool:      
        return not self.deq

---

• 파이썬에서 제공하는 deque 자료형을 사용하였는데, 문제에서 요구하는 조건이 queue 자료형이 가지는 기본적인 기능인 push to back, peek/pop from front, size, is empty 만 사용하라고 하였으므로 해당하는 기능만 사용하였다.

• 매 번 push 를 할 때 마다, queue 의 길이에서 하나를 뺀 만큼 반복문을 돌며 popleft(), append() 를 반복하여 가장 늦게 들어간 데이터가 가장 앞자리에 오도록 정렬한다. 물론 매 번 시행하는 만큼 push 의 시간복잡도는 $O(n)$이 되어 매우 비효율적인 구성이 된다.

• 나머지 기능의 경우 push 단계에서 모든 데이터를 정렬하여 stack 처럼 만들었으므로, queue 가 가지는 기능을 그대로 이용하여 구현했다.

---

232. Implement Queue using Stacks

접근 방법: push를 복잡하게

• 반대로 stack 만 이용해 queue 를 구현하는 문제인데, 아까와는 다르게 stack 의 경우 데이터가 입력되는 곳과 출력되는 곳이 동일한 위치이므로, 특정 위치의 데이터를 가져오기 위해서는 무조건 해당 데이터가 존재하는 곳까지 pop() 을 반복해야 하기 때문에 하나의 stack 만 사용할 경우 모든 데이터의 순서를 조작할 수 없다.

class MyQueue:

    def __init__(self):
        self.lst = list()
        self.temp = list()

    def push(self, x: int) -> None:
        while self.lst:
            self.temp.append(self.lst.pop())
        self.lst.append(x)
        while self.temp:
            self.lst.append(self.temp.pop())

    def pop(self) -> int:
        return self.lst.pop()

    def peek(self) -> int:
        return self.lst[-1]

    def empty(self) -> bool:
        return not self.lst

---

• 매우 단순하게 생각해서, push 가 실행되면 메인스택에 있는 모든 데이터를 pop() 하여 서브스택의 append() 로 넣은 후, 메인스택의 가장 밑바닥에 들어온 데이터를 넣고, 다시 서브스택에서 모든 데이터를 메인스택으로 옮기는 방식으로 작성했다.

• 마찬가지로 push() 단계에서 모든 데이터가 queue 처럼 정렬되므로 나머지 기능은 제공되는 기능으로 처리할 수 있다.

---

Follow-up: Can you implement the queue such that each operation is amortized* O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

amortized: 분할 상환 분석

접근 방법: 시간복잡도를 고려하기

• 위 방식의 경우 push() 는 모든 상황에서 $O(n)$의 시간복잡도를 가지고, 나머지 기능은 $O(1)$을 가진다.

• Follow-up에서 언급하는 분할 상환 분석이란 모든 상황에 대해 최악의 상황만 고려하여 시간복잡도를 잡는 것은 그 함수의 성능을 과하게 낮게 잡는 것이라고 보고, 매 번 최악을 잡는 것이 아닌 n번의 시행에 걸리는 총 시간 T(n)을 가지고 $T(n)/n$의 값으로 시간복잡도를 잡는 것이다. 참고

• 모든 메소드에 대해 분할 상환 분석으로 $O(1)$의 시간복잡도를 가지기 위해서는 n번의 시행동안 T(n)의 시간이 소요되면 된다. 따라서 매 번 push() 가 실행될 때 마다 스택을 정렬하는 것이 아닌, 탐색을 수행하는 메소드가 실행될 때 지금까지 쌓여있는 모든 스택을 큐의 형태로 정렬해놓으면 정렬된 스택을 다 소요할 동안은 상수의 시간복잡도를 가지게 되므로 분할 상환 분석으로는 $O(1)$ 의 시간 복잡도를 지니게 된다.

class MyQueue:

    def __init__(self):
        self.push_stack = []
        self.peek_stack = []

    def push(self, x: int) -> None:
        self.push_stack.append(x)

    def pop(self) -> int:
        val = self.peek()
        self.peek_stack.pop()
        return val

    def peek(self) -> int:
        if not self.peek_stack:
            while self.push_stack:
                self.peek_stack.append(self.push_stack.pop())
        return self.peek_stack[-1]

    def empty(self) -> bool:
        return self.push_stack == [] and self.peek_stack == []

---

• 위와 같이 코드를 작성하면 된다.