[알고리즘] 큐를 이용한 스택 구현

큐를 이용한 스택 구현

내 풀이

class MyStack:

    def __init__(self):
        q1 = deque()
        q2 = deque()


    def push(self, x: int) -> None:
        """
        Push element x onto stack.
        """
        while self.q1:
            self.q2.append(self.q1.popleft())
        self.q1.append(x)
        while self.q2:
            self.q1.append(self.q2.popleft())

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

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

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

큐 두 개를 이용한다. 첫 번째 큐에 push를 하면 첫 번째 큐의 기존에 있던 것들을 순서 그대로 두번째 큐에 옮긴 다음, 첫 번째 큐에 push를 한다. 그러고 옮겼던 것들을 다시 그대로 다 옮겨주면 push한 것이 가장 왼쪽에 있다.

책 풀이

class MyStack:

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

    def push(self, x: int) -> None:
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q1.popleft()

    def top(self) -> int:
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1)==0

조금만 더 생각해보면 아예 하나의 큐로도 구현 가능하다.