225. Implement Stack using Queues (Easy)

---

Problem

Implement the following operations of a stack using queues.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• empty() -- Return whether the stack is empty.

Example

---

Solution

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.
        """
        # 요소를 추가하고 추가한 요소가 리스트의 맨앞에 올 수 있게 하기위해 재정렬
        # 이렇게 하면 큐에서 맨 앞 요소를 추출 할떄 스택처럼 가장 먼저 삽입한 요소가 나온다 (LIFO)
        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

• 요소 삽입시 시간 복잡도가 O(n)이 되어 비효율적이긴 하지만, 이렇게 하면 스택을 큐로 간단하게 구현할 수 있다.

파이썬 알고리즘 인터뷰 - 박상길을 참고하였습니다.