LeetCode #232 - Implement Queue using Stacks(스택을 이용한 큐 구현) 풀이

문제

2개의 스택만을 사용하여 FIFO 큐를 구현하여야 하는 문제이다. 구현된 큐는 일반 큐의 모든 기능(push, pop, empty)를 지원하여야 하며 구현해야 하는 MyQueue 클래스는 다음과 같다.

• push(x: int) -> void : x를 큐의 맨 뒤에 넣는다.
• pop() -> int : 큐의 가장 앞에 있는 요소를 삭제하고 반환한다.
• peek() -> int : 큐의 맨 앞에 있는 요소를 반환한다.
• empty() -> boolean : 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다.

이때, 아래 사항을 참고하여야 한다.

• 스택의 기본 연산(push to top, peek or pop from top, size 및 is empty)만 사용하여야 한다.
• 언어에 따라서는 스택이 navtive로 지원되지 않을 수 있다. 스택의 기본 연산만 사용하는 경우 list 또는 deque(double-end-queue)를 사용하여 스택을 구현할 수 있다.

풀이

스택은 LIFO 정책에 따라 먼저 넣은 데이터를 가장 나중에 꺼낼 수 있다. 슬라이싱을 잘 활용한다면 리스트로 충분히 구현할 수 있지 않을까라는 생각으로 문제에 접근하였다. 파이썬 알고리즘 인터뷰 책에서는 두 개의 리스트를 스택으로 사용하였는데, 출력하기 위해 순서를 바꾸는 과정에서 슬라이싱의 시간 복잡도와 차이가 나지 않는다.

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

    # ... (생략) ....
    # O(N)
    def pop(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
           return self.output.pop()

이를 슬라이싱으로 구현하면 다음과 같다.

class MyQueue:
    def __init__(self):
        self.body = []

    # ... (생략) ...
    # O(N-1)
    def pop(self) -> int:
        val = self.body[0]
        self.body = self.body[1:]
        return val

전체 코드

class MyQueue:
    def __init__(self):
        self.body = []

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

    def pop(self) -> int:
        val = self.body[0]
        self.body = self.body[1:]
        return val

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

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