Python 알고리즘 인터뷰 - 문제24. 스택을 이용한 큐 구현

leetcode 232. Implement Queue using Stacks - https://leetcode.com/problems/implement-queue-using-stacks/description/

 

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

myQueue = MyQueue();
myQueue.push(1); # queue is: [1]
myQueue.push(2); # queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); # return 1
myQueue.pop(); # return 1, queue is [2]
myQueue.empty(); # return false

 

풀이

스택 2개를 사용하여 push가 발생할 때 stack1에서 stack2로 값을 pop, push로 이동 시킨다. 이후 stack2에 push된 값를 추가한 후 다시 stack2에서 stack1으로 값을 pop, push 하면 queue 처럼 입력 순서대로 pop을 할 수 있도록 인터페이스가 구성된다.

 

코드는 다음과 같다.

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

    def push(self, x):
        tmp_st = []
        while self.st:
            tmp_st.append(self.st.pop())
        tmp_st.append(x)

        while tmp_st:
            self.st.append(tmp_st.pop())

    def pop(self):
        return self.st.pop()

    def peek(self):
        return None if len(self.st) == 0 else self.st[-1]

    def empty(self):
        return len(self.st) == 0