24. Implement Queue using Stacks

리트코드

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

• push(x): 요소 x를 큐 마지막에 삽입한다.

• pop(): 큐 처음에 있는 요소를 제거한다.

• peek(): 큐 처음에 있는 요소를 조회한다.

• empty(): 큐가 비어 있는지 여부를 리턴한다.

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.
        """
        
        #output이 없으면 모두 재입력
        
        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 == []
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

• 앞서와는 다른 중요한 차이가 있다.
  지난 풀이에서는 큐에 요소를 삽입한 후 맨 앞의 요소부터 끄집어냈다. 그렇게 해서 원래의 큐에 덧붙여 나가는 형태로, 추가 공간 없이 풀이가 가능했다.

  그러나, 이번에는 맨 뒤의 아이템을 끄집어낼 수밖에 없다.

  • 이렇게 하면 다음번에 또 다시 맨 뒤의 아이템을 끄집어 내게 되는데, 결국 무한반복 문제에서 헤어나올 수 없다는 점이 문제다.
  • 따라서, 이 문제를 스택의 연산만을 사용해서 풀기 위해서는 2개의 스택이 필요하다.

• pop()과 peek()은 결국 같은 데이터를 끄집어낸다는 점에 착안해, 이번에는 pop()을 할 때 peek()을 호출하고 여기에 재입력하는 알고리즘을 구현

• 이렇게 구현해도 output의 값이 모두 팝(pop())되기 전까지는 다시 재입력이 일어나지 않기 때문에, 분할 상환 분석에 따른 시간 복잡도는 여전히 O(1)이다.