[리트코드] 232. 스택을 사용하여 큐 구현하기 (Python)

Implement Queue using Stacks - LeetCode

문제

두 개의 스택만 사용하여 큐를 구현하라.

• push(): 요소를 대기열 뒤쪽으로 푸시합니다.
• pop(): 대기열의 앞부분에서 요소를 제거하고 반환합니다.
• peek(): 대기열의 맨 앞에 있는 요소를 반환합니다.
• empty(): 대기열이 비어 있으면 true를 반환하고 , 그렇지 않으면 false를 반환합니다.

과정

1. 큐는 요소를 삽입하고 삭제하는 위치가 다르지만, 스택은 요소를 삽입,삭제하는 위치가 동일하다.
   따라서 스택으로 큐를 구현하기 위해서는 스택 2개가 필요하다.
2. input과 output 두개의 스택으로 나누어서 구현한다.
3. 요소를 삽입하면 input에 넣어준다
4. 데이터를 살펴보는 peek(), pop()함수가 호출되면 input에 있던 모든 요소를 pop()해서 output에 옮긴 후 호출된 peek() 또는 pop()함수를 실행한다.

 

입력

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

출력

[null, null, null, 1, 1, false]

 

풀이

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

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

    def pop(self) -> int:
        self.peek()
        return self.output.pop()

    def peek(self) -> int:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self) -> bool:
        return self.input == [] and self.output == []

 

한 줄씩 코드 해석해보기

class MyQueue:
    def __init__(self):
        self.input = []
        self.output = []

• input과 output 두개의 스택을 만들어준다

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

• push 명령을 할 경우 스택은 선입선출이기 때문에 그냥 append해준다

def pop(self) -> int:
    self.peek()
    return self.output.pop()

def peek(self) -> int:
    if not self.output:
        while self.input:
            self.output.append(self.input.pop())
    return self.output[-1]

• peek(), pop()함수가 호출되면 input에 있던 모든 요소를 output에 옮기는 일은 모두 peek() 함수에 구현
• pop() 실행시 input에 있던 모든 요소를 pop()해서 output에 옮긴 후 output에서 pop() 해준다.
• peek() 실행시 input에 있던 모든 요소를 pop()해서 output에 옮긴 후 output에서 가장 마지막값을 반환한다.

def empty(self) -> bool:
	return self.input == [] and self.output == []

• input과 output이 비었는지 확인 후 return