[leetcode] 53. 232. Implement Queue using Stacks - Python

🔍 Problem

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

---

📰 문제풀이

• 제한 시간: 20분
• 성공 여부: 실패
• 실패 원인: 2개의 stack을 이용해 어떻게 queue처럼 구현할 수 있을까 고민하다가 결국 제한 시간 내에 deque를 이용해 풀었다...

---

📃 Solving Process

1. 두 개의 stack을 이용해 queue를 구현해야 한다.
2. 먼저 값이 입력되는 append는 stack_in에 값을 넣어준다.
3. pop은 stack_in의 첫 번째 원소를 없애고 반환해야 한다. 따라서 stack_in의 첫 번째 원소만 남을 때까지 stack_in.pop()을 수행하고 해당 값들을 보관하기 위해 stack_out.append()로 값을 저장한다.
4. 마지막 남은 stack_in의 첫 번째 원소를 front_value에 저장하고 이제 다시 stack_out에 있던 원소를 stack_in으로 다시 담아준다.
5. 4번 과정이 이해가 되지 않는다면 두 개의 스택구조를 직접 그려보고 예제를 풀어보면 쉽게 이해할 수 있다.

---

💻 Code

class MyQueue:

    def __init__(self):
        self.stack_in = list()
        self.stack_out = list()

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

    def pop(self) -> int:
        length = len(self.stack_in) - 1
        for _ in range(length):
            self.stack_out.append(self.stack_in.pop())
        front_value = self.stack_in.pop()
        for _ in range(length):
            self.stack_in.append(self.stack_out.pop())   
        return front_value

    def peek(self) -> int:
        return self.stack_in[0]

    def empty(self) -> bool:
        if self.stack_in:
            return False
        return True

---

⏱ Time Complexity

• 구현해야 하는 메서드 기준으로 시간 복잡도를 계산했다.
  • append() => O(1)
  • pop() => O(N) - 스택의 모든 원소를 뺐다가 다시 넣어줘야 한다.
  • peek() => O(1)
  • empty => O(1)

---

💾 Space Complexity

• 두 개의 stack이 필요하므로 O(2N) -> O(N)이다.