Stack과 Queue — 단순한 자료구조가 면접에서 까다로운 이유

Stack과 Queue는 가장 단순한 자료구조지만, "Java에서 Stack 클래스를 왜 쓰면 안 되는지", "Stack 두 개로 Queue를 어떻게 구현하는지"까지 들어가면 이야기가 깊어집니다.

Stack 은 마지막에 넣은 요소가 먼저 나오는(LIFO) 자료구조이고, Queue 는 먼저 넣은 요소가 먼저 나오는(FIFO) 자료구조입니다. 이 두 가지가 DFS/BFS, 함수 호출, 메시지 처리 등 다양한 시스템의 기반이 됩니다.

Stack: 후입선출(LIFO)

동작 원리

마지막에 넣은 요소가 먼저 나옵니다.

push(10) → [10]
push(20) → [10, 20]
push(30) → [10, 20, 30]
pop()    → 30 반환, [10, 20]
peek()   → 20 반환, [10, 20] (제거 안 함)

Java에서의 올바른 구현체 선택

Java에는 Stack 클래스가 있지만, 실무에서는 사용하지 않습니다.

// ❌ Stack 클래스
Stack<Integer> stack = new Stack<>();

// ✅ Deque 인터페이스 + ArrayDeque 구현체
Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.pop();

Stack 클래스가 문제인 이유는 상속 구조에 있습니다. Stack은 Vector를 상속받는데, Vector는 모든 메서드에 synchronized가 걸려 있습니다. 단일 스레드 환경에서도 락 획득/해제 비용을 매번 지불 하게 됩니다. Java 공식 문서에서도 Deque 인터페이스를 권장합니다.

활용 사례

• 함수 호출 스택(Call Stack) -- 함수가 호출되면 프레임이 쌓이고, 리턴하면 빠짐
• ** 괄호 매칭** -- ({[]}) 같은 문자열의 짝 검증
• undo/redo -- 에디터의 되돌리기 기능
• DFS(깊이 우선 탐색) -- 재귀 대신 명시적 스택 사용 가능
• ** 후위 표기법 계산** -- 3 4 + 5 * 같은 수식 평가

Queue: 선입선출(FIFO)

동작 원리

먼저 넣은 요소가 먼저 나옵니다.

offer(10) → [10]
offer(20) → [10, 20]
offer(30) → [10, 20, 30]
poll()    → 10 반환, [20, 30]
peek()    → 20 반환, [20, 30]

Java에서의 구현체 선택

Queue<Integer> queue = new ArrayDeque<>();  // 권장
Queue<Integer> queue = new LinkedList<>();  // 가능하지만 느림

ArrayDeque가 LinkedList보다 빠른 이유는 Array vs LinkedList에서 다뤘던 것과 동일합니다. 연속된 메모리 배치 덕분에 CPU 캐시 적중률이 높습니다.

활용 사례

• BFS(너비 우선 탐색) -- 가까운 노드부터 탐색
• ** 메시지 큐** -- Kafka, RabbitMQ 같은 비동기 처리 시스템의 기반
• ** 스케줄링** -- OS 프로세스 스케줄링, 프린터 작업 대기열
• ** 버퍼** -- 생산자-소비자 패턴의 중간 저장소

Deque: 양쪽 끝이 열린 큐

Deque(Double-Ended Queue)은 앞뒤 양쪽에서 삽입/삭제가 가능합니다. Stack과 Queue를 모두 대체할 수 있는 범용 자료구조입니다.

Deque<Integer> deque = new ArrayDeque<>();

// Stack처럼 사용
deque.push(10);       // 앞에 넣기
deque.pop();          // 앞에서 빼기

// Queue처럼 사용
deque.offerLast(10);  // 뒤에 넣기
deque.pollFirst();    // 앞에서 빼기

Java에서 Stack이 필요하면 Deque<T> stack = new ArrayDeque<>()를, Queue가 필요하면 Queue<T> queue = new ArrayDeque<>()를 사용하는 것이 표준적인 패턴입니다.

Priority Queue: 우선순위 기반 큐

일반 Queue는 삽입 순서대로 꺼내지만, Priority Queue는 ** 우선순위가 높은 요소부터** 꺼냅니다. 내부적으로 ** 힙(Heap)**을 사용합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙
pq.offer(30);
pq.offer(10);
pq.offer(20);
pq.poll(); // 10 (가장 작은 값)
pq.poll(); // 20
pq.poll(); // 30

힙은 완전 이진 트리의 일종으로, 부모 노드가 항상 자식보다 작거나(최소 힙) 큰(최대 힙) 성질을 유지합니다. 삽입과 삭제 시 이 성질을 복원하기 위해 트리를 재조정하므로 O(log n)이 걸립니다.

Stack 두 개로 Queue 구현하기

Stack은 LIFO이고 Queue는 FIFO입니다. Stack을 ** 두 번 거치면** 순서가 두 번 뒤집혀서 원래 순서(FIFO)가 됩니다.

inStack에 요소를 넣고, 꺼낼 때 outStack이 비어있으면 inStack의 모든 요소를 outStack으로 옮깁니다.

class MyQueue<T> {
    private Deque<T> inStack = new ArrayDeque<>();
    private Deque<T> outStack = new ArrayDeque<>();

    public void offer(T item) {
        inStack.push(item);
    }

    public T poll() {
        if (outStack.isEmpty()) {
            while (!inStack.isEmpty()) {
                outStack.push(inStack.pop()); // 순서 뒤집기
            }
        }
        return outStack.pop();
    }
}

poll()이 최악의 경우 O(n)이지만, ** 분할 상환 O(1)**입니다. 각 요소는 inStack에 한 번 push, outStack으로 한 번 pop, outStack에서 한 번 pop -- 총 3번의 연산만 발생하기 때문입니다.

반대로 Queue 두 개로 Stack을 구현하는 것도 가능하지만, push 때마다 전체를 옮겨야 해서 O(n)이 됩니다. 실용적이지 않습니다.

원형 큐 (Circular Queue)

배열 기반 큐는 front와 rear가 앞으로만 이동하면 앞쪽 공간이 낭비됩니다. 원형 큐는 배열 끝에 도달하면 다시 0번 인덱스로 돌아가서 ** 공간을 재활용 **합니다.

배열: [_, _, _, 10, 20, 30]
             front↑         ↑rear

dequeue 후 enqueue(40):

배열: [40, _, _, _, 20, 30]
                    front↑  ↑rear=0

핵심 공식은 rear = (rear + 1) % capacity입니다. 나머지 연산으로 인덱스가 배열 크기를 넘어가면 0으로 순환합니다.

주의할 점

Java Stack 클래스 사용

Stack은 Vector를 상속받아 모든 연산에 synchronized가 걸려 있습니다. 단일 스레드에서 불필요한 동기화 비용을 지불하게 되므로, ** 항상 ArrayDeque를 사용 **해야 합니다.

PriorityQueue의 정렬 오해

PriorityQueue는 내부적으로 힙 구조를 유지하므로, **iterator로 순회하면 정렬된 순서가 아닙니다 **. 정렬된 순서로 꺼내려면 반드시 poll()을 반복 호출해야 합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(30, 10, 20));
// iterator 순회: 정렬 보장 안 됨 (힙 내부 배열 순서)
// poll() 반복: 10, 20, 30 (정렬된 순서)

BlockingQueue와 일반 Queue 혼동

큐가 비어있을 때 poll()은 null을 반환하지만, BlockingQueue.take()는 ** 스레드를 블록 **시킵니다. 생산자-소비자 패턴에서 BlockingQueue를 사용할 때 이 차이를 혼동하면 데드락이나 NPE가 발생할 수 있습니다.

BlockingQueue<String> queue = new LinkedBlockingQueue<>(10);
queue.put("task1");          // 큐가 가득 차면 대기
String task = queue.take();  // 큐가 비면 대기

정리