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

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

---

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

 

문제 정의

스택으로 큐 구현

 

책에서 구현된 코드

class MyQueue:

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

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

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

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

    def empty(self) -> bool:
        return self.input == [] and self.output == []

 

기억해야할 기법

• Amortized O(1)
  • pop, peek을 호출할 때만 stack을 뒤집어서 사용

 

내가 구현한 코드

class MyQueue:

    def __init__(self):
        self.stk = []
        self.tmp = []

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

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

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

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

• Amortized O(1)를 만들지 못했음
  • push가 일어날 때마다 n개씩 데이터 이동 발생
• 그런데 leetcode에 제출할 때는 두 알고리즘의 runtime이 비슷함
  
  • 오히려 내가 구현한 게 더 빨랐으나(28ms vs 32ms), 다시 돌려보니 32ms 나옴