[파이썬 알고리즘 인터뷰][스택/큐] 큐를 이용한 스택 구현

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

큐를 이용해 다음 연산을 지원하는 스택 구현

1. push(x)
2. pop()
3. top()
4. empty()

 

책에서 구현된 코드

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

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

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

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

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

 

기억해야할 기법

• 큐 1개로 스택을 쉽게 구현 가능

 

내가 구현한 코드

from collections import deque
class MyStack:
    q = deque()
    tmp = deque()

    def __init__(self):
        self.q.clear()
        self.tmp.clear()

    def push(self, x: int) -> None:
        self.tmp.append(x)
        while self.q:
            self.tmp.append(self.q.popleft())
        self.tmp, self.q = self.q, self.tmp

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

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

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

• 문제에 큐 2개를 사용하라했는데, 하나로도 간단하게 구현할 수 있었다