[LeetCode] #232. Implement Queue using Stacks

nayeoniee·2021년 9월 9일
0

Algorithm

목록 보기
23/29

리트코드 #232. 스택을 이용한 큐 구현

문제

문제 링크

스택을 사용해 큐의 기본 연산을 구현한다.

push() : 큐에 요소 삽입
pop() : 큐의 가장 마지막 요소 제거 및 반환
peek() : 큐의 가장 마지막 요소 반환
empty() : 큐가 비어있으면 True

풀이

큐는 요소를 삽입하고 삭제하는 위치가 다르지만, 스택은 요소를 삽입,삭제하는 위치가 동일하다.
따라서 스택으로 큐를 구현하기 위해서는 스택 2개가 필요하다.

1) 위의 그림처럼 input, output 2개의 스택을 선언한다.
2) 요소를 삽입하면 input에 데이터를 넣는다.
3) 데이터를 살펴보는(?) peek(), pop()함수가 호출되면 input에 있던 모든 요소를 pop()해서 output에 옮긴 후 호출된 peek() 또는 pop()함수를 실행한다.

코드

github link

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 == []

peek(), pop()함수가 호출되면 input에 있던 모든 요소를 output에 옮기는 일은 모두 peek() 함수에 구현했다.

참고한 강의 : 엔지니어대한민국

profile
정말 할 수 있어!

0개의 댓글