23. Implement Stack using Queues

리트코드

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

  • push(x): 요소 x를 스택에 삽입한다.

  • pop(): 스택의 첫 번째 요소를 삭제한다.

  • top(): 스택의 첫 번째 요소를 가져온다.

  • empty(): 스택이 비어 있는지 여부를 리턴한다.

1. push() 할 때 큐를 이용해 재정렬

  class MyStack:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        
        self.q = collections.deque()
        

    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        
        self.q.append(x)
        
        #요소 삽입 후 맨 앞에 두는 상태로 재정렬
        
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
        

    def pop(self) -> int:
        """
        Removes the element on top of the stack and returns that element.
        """
        
        return self.q.popleft()
        

    def top(self) -> int:
        """
        Get the top element.
        """
        
        return self.q[0]
        

    def empty(self) -> bool:
        """
        Returns whether the stack is empty.
        """
        
        return len(self.q) == 0
        


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

• 스택이나 큐 ADT를 실제로 구현할 때는 , 대개 스택은 연결리스트로 하고 큐는 배열로 한다.

• 여기서는 큐로 스택을 디자인 하라고 한다. 이 문제는 스택을 그저 활용하기만 하면 되지만, 만약 스택까지 직접 구현하게 된다면 큐를 스택으로 구현하고, 스택은 연결 리스트로 구현하는 구조가 될 것이다.

• 큐를 데크로 선언했지만 문제의 의도에 맞게 여기서는 큐의 연산만을 사용해 구현할 것이다.

• push()할 때만 다소 복잡한 편인데, 다음과 같이 요소를 삽입한 후에 방금 삽입한 요소를 맨 앞에 두는 상태로 전체를 재정렬한다.

• 이렇게 하면 큐에서 맨 앞 요소를 끄집어낼 때 스택처럼 가장 먼저 삽입한 요소가 나오게 될 것이다.

  • 물론, 요소 삽입 시 시간 복잡도가 O(n)이 되어 다소 비효율적이다.