225. Implement Stack using Queues

Queue를 이용해서 Stack을 구현하는 문제 

 

python에서는 list에서 stack도 가능하고 queue도 가능하지만, list를 queue처럼 사용할 경우 속도가 느리다. O(1)을 보장하기 위해 Queue를 사용한다.

 

문제에서는 일단 list를 사용해서 myStack을 만들었고, 통과를 했음

class MyStack:
    def __init__(self):
        self.q = []

    def push(self, x: int) -> None:
        self.q.append(x)
        

    def pop(self) -> int:
        return self.q.pop()
        

    def top(self) -> int:
        return self.q[-1]
        

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

 

하지만 queue를 이용하라고 했으므로, 다시 풀어보면 다음과 같다. 

q의 자료형을 collections.deque()로만 바꿨다. 

class MyStack:

    def __init__(self):
        self.q = collections.deque()
    def push(self, x: int) -> None:
        self.q.append(x)
    def pop(self) -> int:
        return self.q.pop()
    def top(self) -> int:
        return self.q[-1]
    def empty(self) -> bool:
        return len(self.q) == 0

queue를 list처럼 사용해서 마음에 들지 않는다. 

queue는 FIFO구조이므로 pop을 했을때는 앞에서 가져와야하고, top을 했을때는 끝자리가 아니라 [0]에서 값을 가져와야한다. 

 

그러므로 push 할때 뒤집어 주어야 한다.

class MyStack:

    def __init__(self):
        self.q = collections.deque()
    
    def push(self, x: int) -> None:
        self.queue.append(x)
        #queue구조는 FIFO이므로 반대로 뒤집어 준다.
        for _ in range(len(self.queue)-1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.q.pop()
    
    def top(self) -> int:
        return self.q[-1]
    
    def empty(self) -> bool:
        return len(self.q) == 0