[자료구조/스택] 큐를 이용한 스택 구현

문제

• 큐를 이용해 다음 연산을 지원하는 스택(Last-In-First-Out)을 구현
  • push(a) : 값 a를 스택에 삽입한다
  • pop() : 스택의 첫번째 요소를 삭제하고 반환한다. (제일 나중에 들어간 값이 첫번째 요소를 의미할 것이다)
  • top() : 스택의 첫번째 요소를 가져온다.
  • empty() : 스택이 비어 있는지 여부를 확인한다. (True / False)
• 원본 url : https://leetcode.com/problems/implement-stack-using-queues/

 

문제 풀이

• 큐는 파이썬 자료구조 중 deque를 활용한다
• 큐의 연산(맨 앞에 있는 값을 제일 먼저 가져오는)만을 사용하기 위해 스택의 LIFO를 구현해줘야 한다
• 즉, 맨 나중에 들어오는 값이 맨 앞(맨 왼쪽에 위치하게끔 바꿔야 한다.
• 실행 속도 : 39ms

class MyStack(object):

    def __init__(self):
        self.q = collections.deque()

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        # Step1. 값을 집어 넣는다
        self.q.append(x)

        # Step2. 데이터를 재정렬한다.
        # 현재 들어 있는 값중 맨 마지막 값은 가만히 있으면 되기 때문에
        # 전체 개수에서 1개 뺀만큼만 이동하면 된다.
        for _ in range(len(self.q)-1):
            # deque 자료구조의 연산중 popleft는 결국 que의 선입선출 연산구조를 의미한다.
            self.q.append(self.q.popleft())

    def pop(self):
        """
        :rtype: int
        """
        return self.q.popleft()

    def top(self):
        """
        :rtype: int
        """
        return self.q[0]


    def empty(self):
        """
        :rtype: bool
        """
        return len(self.q)==0