232. Implement Queue using Stacks ☆

232. Implement Queue using Stacks

 

이 문제는 두 개의 스택을 이용해서 큐(FIFO)를 구현하는 문제로, 인터뷰에서도 자주 나오는 고전 문제입니다.
Follow-up 조건인 "모든 연산의 시간복잡도가 평균 O(1)" 도 만족해야 합니다.

---

✅ 핵심 아이디어

두 개의 스택 사용:

• in_stack: push() 할 때 사용하는 스택 (뒤쪽에 쌓임)
• out_stack: pop()/peek() 할 때 사용하는 스택 (앞쪽에서 꺼냄)

📌 필요할 때만 in_stack을 out_stack으로 옮기기 때문에 amortized O(1) 시간 보장됨

---

✅ 구현 코드 (Python, 리스트를 스택처럼 사용)

class MyQueue:
    def __init__(self):
        # 데이터를 입력받는 스택 (큐의 뒤쪽 역할)
        self.in_stack = []

        # 데이터를 꺼내는 스택 (큐의 앞쪽 역할)
        self.out_stack = []

    def push(self, x: int) -> None:
        # 새로운 값을 in_stack 에 추가
        # 큐에서 뒤쪽에 들어가는 것과 같음
        self.in_stack.append(x)

    def pop(self) -> int:
        # 큐의 앞쪽 값을 꺼냄
        # out_stack이 비어 있다면 in_stack의 모든 값을 옮겨야 함
        self._move_in_to_out()
        # out_stack의 top은 큐의 front와 같으므로 꺼냄
        return self.out_stack.pop()

    def peek(self) -> int:
        # 큐의 앞쪽 값을 확인 (제거하지 않음)
        self._move_in_to_out()
        return self.out_stack[-1]  # top 요소 보기

    def empty(self) -> bool:
        # 두 스택 모두 비어 있어야 큐가 비어 있는 상태
        return not self.in_stack and not self.out_stack

    def _move_in_to_out(self):
        # out_stack 이 비어 있을 때만 옮김 (필요할 때만)
        # 이렇게 하면 매번 옮기지 않

 

🔍 요약 흐름

연산 동작	방식
push(x)	in_stack에 추가 (큐의 뒤)
pop() / peek()	out_stack이 비어 있으면 in_stack을 뒤집어 옮기고, 그 위에서 꺼냄
empty()	두 스택 모두 비어 있으면 True

 

🔍 작동 흐름 예시

myQueue = MyQueue()
myQueue.push(1)     # in_stack = [1]
myQueue.push(2)     # in_stack = [1, 2]
myQueue.peek()      # out_stack = [2, 1] → peek = 1
myQueue.pop()       # out_stack.pop() = 1
myQueue.empty()     # False (out_stack = [2])

 

⏱️ 시간복잡도 (Amortized)

연산	시간 복잡도
push	O(1)
pop	O(1) (amortized)
peek	O(1) (amortized)
empty	O(1)

 

최종 내 코드

class MyQueue:
    # 스텍을 가지고, 큐를 만들어야
    # 스텍: 후에 넣은게 먼저 나감
    # 큐: 먼저 넣은게.. 먼저 나감
    # 2개 스텍만들어서

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

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

    def pop(self) -> int:
    	"""
        pop()이나 peek()할 때마다 input 스택을 매번 다 비워서 output에 옮길 필요없이,
		이미 output 스택에 데이터가 있으면 굳이 다시 옮길 필요 없습니다.
        왜냐. output 스텍에 있는 데이터는 미리 들어온거다보니, 비워지면 채워넣으면 됨!!
        """
        if not self.output: 
            while self.input:
                self.output.append(self.input.pop())
        return self.output.pop()        

    def peek(self) -> int:
    	"""
        pop()이나 peek()할 때마다 input 스택을 매번 다 비워서 output에 옮길 필요없이,
		이미 output 스택에 데이터가 있으면 굳이 다시 옮길 필요 없습니다.
        왜냐. output 스텍에 있는 데이터는 미리 들어온거다보니, 비워지면 채워넣으면 됨!!
        """
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]
        

    def empty(self) -> bool:
        # 둘다 비었으면 True
        return not self.input and not self.output
        


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()