[2024] Day29. 232. Implement Queue using Stacks

gunny·2024년 1월 29일

232. Implement Queue using Stacks 232. Implement Queue using Stacks python leetcode 232. Implement Queue using Stacks leetcode 232. Implement Queue using Stacks python

코딩테스트

목록 보기

342/530

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 29일 (월)
Leetcode daily problem

232. Implement Queue using Stacks

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/description/?envType=daily-question&envId=2024-01-28

Problem

두 개의 스택만 사용하여 FIFO(선입선출)를 구현한다.
구현된 큐는 일반 큐의 모든 기능(푸시, 픽, 팝, 비어 있음)이 가능해야한다.

MyQueue 클래스를 구현하고,
void push(int x) 요소 x를 대기열 뒤로 밀어 넣는다.
int pop() 대기열의 앞부분에서 요소를 제거하고 반환한다.
int peek() 대기열의 맨 앞에 있는 요소를 반환한다.
booleanempty() 대기열이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환한다.

주의사항
스택의 표준 작업만을 사용해서 push, pop, empty를 구현해야 합니다.

Solution

data structure

스택 2개 (리스트) 를 생성한뒤에 push 작업을 할 때는 lst1 에 있는 것을 pop하면서 임시 스택인 lst2에 뒤에서부터 순차적으로 넣는다.
기존 스택 lst1에 있는 모든 원소를 뒤에서부터 lst2로 옮긴후에 현 시점에 push되는 원소 값을 lst1에 넣는다.
그 뒤에 옮겼던 lst2를 뒤에서부터 순차적으로 pop 하면서 다시 lst1에 넣어준다.

그러면 선입선출을 스택으로 구현할 수 있고, peek 같은 제일 처음에 들어가는 원소들이나 pop 같은 경우에는 스택의 가장 마지막에 있기 때문에 출력하거나 pop 할 수 있다.

Code

class MyQueue:

    def __init__(self):
        self.lst1 = []
        self.lst2 = []

    def push(self, x: int) -> None:
        while self.lst1:
            self.lst2.append(self.lst1.pop())
        self.lst1.append(x)
        while self.lst2:
            self.lst1.append(self.lst2.pop())

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

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

    def empty(self) -> bool:
        return not self.lst1