[작심큰일] 250806 - leetcode 232번: Implement Queue using Stacks

📜 232번: Implement Queue using Stacks (https://leetcode.com/problems/implement-queue-using-stacks/description/)

두 개의 스택만 사용하여 선입선출(FIFO) 큐를 구현하세요. 구현된 큐는 일반 큐의 모든 기능( push, peek, pop, empty)을 지원해야 합니다.

클래스 를 구현합니다 MyQueue.

void push(int x)요소 x를 큐의 맨 뒤로 밀어 넣습니다.
int pop()큐의 앞쪽에서 요소를 제거하고 반환합니다.
int peek()큐의 앞에 있는 요소를 반환합니다.
boolean empty()true대기열이 비어 있으면 반환하고 , false그렇지 않으면 반환합니다.
참고사항:

스택의 표준 연산 만 사용해야 합니다 . 즉 push to top, peek/pop from top, , size, is empty연산만 유효합니다.
언어에 따라 스택이 기본적으로 지원되지 않을 수 있습니다. 스택의 표준 연산만 사용하는 경우, 리스트나 데크(양방향 큐)를 사용하여 스택을 시뮬레이션할 수 있습니다.

 

import java.util.*;

class MyQueue {

    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

 

스택 2개로 큐를 구현하는 코드

push의 경우 첫번째 스택에 push

pop,peek의 경우 두번째 스택에 아무 요소도 존재하지 않으면 첫번째 스택에 있는 것을 모두 두번째 스택에 옮겨 넣음 이후 두번째 스택에서 pop

empty는 첫번째 두번째 스택이 비어있을 경우 true를 반환한다.

 

 

 

🪛 피드백

📝 코드 설명

- stackIn: 새로운 요소를 push할 때 사용

- stackOut: pop 또는 peek 연산 시 사용하는 스택

- stackOut이 비어있으면 stackIn의 모든 원소를 옮겨 순서를 뒤집어 FIFO를 구현

- pop, peek는 항상 stackOut에서 처리하며, empty는 두 스택 모두 비었는지 확인

- 이렇게 하면 큐의 기본 연산을 스택으로 완벽히 재현 가능

📊 복잡도 분석

시간 복잡도: 평균 O(1) - push는 O(1) - pop, peek는 한 번 옮길 때 O(n)이지만, 전체적으로 균등 분배되어 평균 O(1)

공간 복잡도: O(n) (스택 두 개에 저장하는 만큼)

⚡ 최적화 팁

1. [불필요한 이동을 줄이기] : stackOut이 비었을 때만 stackIn

2. [스택 연산만 사용 엄수] : 문제 조건 준수가 필수

3. [기본 스택 API 활용] : push, pop, peek, isEmpty 등 메서드는 최적화가 되어 있음

🎯 학습 포인트

- 두 개의 스택을 이용해 큐 동작 구현하는 방법

- 스택과 큐의 차이 및 연산 특성 이해

- 평균 시간 복잡도 개념

🔗 관련 문제

- 큐를 스택으로 구현할 때는 “입력용 스택”과 “출력용 스택” 분리 개념을 반드시 숙지

- pop/peek 호출 시마다 모두 옮기는 게 아니라 필요한 순간에만 옮겨 효율적 동작 보장