232. Implement Queue using Stacks

stack을 이용해서 queue를 구현하는 것

python의 list는 특정 index에서도 remove가 가능하다. 

 

queue명령어들은 다음과 같다. 

• void push(int x) Pushes element x to the back of the queue.
  -> queue의 맨 뒤에 넣으면 되겠다/
• int pop() Removes the element from the front of the queue and returns it.
  -> queue의 맨 앞을 pop하면 되겠다.
• int peek() Returns the element at the front of the queue.
  -> queue의 맨 앞의 원소 
• boolean empty() Returns true if the queue is empty, false otherwise.
  -> queue의 길이를 가지고 판단

아래 코드가 통과는 되지만 시간 복잡도에서는 최악이다. 

이유는 list에서 pop을 할 경우에는 다시 재정렬이 필요하기 때문이다.

class MyQueue:

    def __init__(self):
        self.stack = []

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

    def pop(self) -> int:
        return self.stack.pop(0)

    def peek(self) -> int:
        return self.stack[0]

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

 대신 stack을 두개를 써서 하면 push은 O(n), pop은 O(1) 보장할 수 있다. 

 

class MyQueue:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        self.front = 0

#추가할때 stack1번을 먼저 다 빼서, stack2에 거꾸로 쌓는다.
#x를 먼저 추가하고, stack2를 다시 옮긴다. 

    def push(self, x: int) -> None:
        while self.stack1:
            self.stack2.append(self.stack1.pop())
        self.front = x
        self.stack1.append(x)

        while self.stack2:
            self.stack1.append(self.stack2.pop())

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

    def peek(self) -> int:
        return self.stack1[-1]

    def empty(self) -> bool:
        #return len(self.stack) == 0
        return not self.stack1