232. Implement Queue using Stacks

---

Problem

Implement the following operations of a queue using stacks.

• push(x) -- Push element x to the back of queue.
• pop() -- Removes the element from in front of queue.
• peek() -- Get the front element.
• empty() -- Return whether the queue is empty.

Example

Solution

class MyQueue:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input = []
        self.output = []

    def push(self, x: int) -> None:
        """
        Push element x to the back of queue.
        """
        self.input.append(x)

    def pop(self) -> int:
        """
        Removes the element from in front of queue and returns that element.
        """
        self.peek()
        return self.output.pop()

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

    def empty(self) -> bool:
        """
        Returns whether the queue is empty.
        """
        return self.input == [] and self.output == []

• Queue를 이용한 Stack 구현과는 다르게 마지막요소부터 끄집어내야되는 문제여서 2개의 스택을 만들었다.
• peek() 함수와 pop 함수는 결국 같은 값을 끄집어내는 함수여서 pop()함수를 호출할때 peek()함수를 호출하고 이곳에 재입력하는 알고리즘이다.
• 즉, 가장먼저 입력된 값을 호출하기 때문에 입력된 값이 없다면 peek()함수에서 푸쉬한 입력한값을 다시 재입력한다 (그래서 시간복잡도는 O(1))