스택을 이용한 큐 구현 - 큐

Implement Queue Using Stack

스택을 이용해 다음 연산을 지원하는 큐를 구현하라.

• push(x): 요소x를 큐 마지막에 삽입한다.
• pop(): 큐처음에 있는 요소를 제거한다.
• peek(): 큐 처음에 있는 요소를 조회한다.
• empty(): 큐가 비어있는지 여부를 조회한다.

---

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:
        if not self.output and not self.input:
            return True
        else:
            return False

---

#풀이
__init__ : 큐는 입구와 출구가 하나씩이지만 스택은 입구와 출구가 동일하기 떄문에 스택 2개를 이용해 풀기 위해 두개의 배열을 생성해준다.

push(x): input이라는 리스트에 x요소를 삽입해준다.

pop() : 큐는 선입선출 방식이기 때문에 먼저 들어온 요소가 반환되어야 하기때문에, 큐 처음에 들어온 요소를 검색하는 peek()를 호출하여 반환하여준다.

peek() : 큐에 가장 처음 들어온 요소를 검색하기 위해서는 output 리스트에 요소가 존재하는지 부터 확인해줘야한다.
만약 없을경우 input 리스트에서 늦게 들어온 요소부터 output리스트에 삽입해주어 가장 빨리 들어온 요소를 가장 위로 갈수있게 해준다. 그후 output에 가장위에 있는 요소를 반환해준다.

empty() : 큐가 비어있는 경우는 output 과 input 리스트 둘다 비어있는 경우이다.