44. Implement Queue using Stacks

문제

두 개의 스택만 이용해서 FIFO 큐를 구현하시오.

(push, pop, peek, empty 메서드 구현)

 

해결 방식

https://leetcode.com/explore/learn/card/queue-stack/239/conclusion/1386/discuss/64198/Share-my-python-solution-(32ms) 

 

instack에서는 enqueue 작업만,

outstack에서는 dequeue 작업만 실행.

 

enqueue 시

1) instack에 요소 바로 삽입.

 

dequeue 시 

1) instack에 있는 요소를 모두 outstack에 가져옴.

2) outstack의 마지막 요소를 pop해서 반환

ex) instack = [1, 2, 3]이고 outstack = []인 경우 dequeue시 1이 나가야 함.

      instack 요소를 pop해서 outstack에 넣기 => instack = [], outstack = [3, 2, 1]

      outstack의 마지막 요소를 pop하면 1이 알맞게 나감. 

class MyQueue:
    def __init__(self):
        self.instack = []
        self.outstack = []

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

    def pop(self) -> int:
        # instack은 있는데 outstack에 아무것도 없을때만 instack 요소를 outstack으로 이동
        if self.instack and not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack.pop()

    def peek(self) -> int:
    	# instack은 있는데 outstack에 아무것도 없을때만 instack 요소를 outstack으로 이동
        if self.instack and not self.outstack:
            while self.instack:
                self.outstack.append(self.instack.pop())
        return self.outstack[-1]
    
    def empty(self) -> bool:
        return not self.instack and not self.outstack