Stack, Queue, Deque

스택·큐·덱은 데이터를 넣고 빼는 위치를 어떻게 제한하느냐로 갈리는 선형 자료구조다.

스택과 큐의 차이

둘 다 한쪽 끝에서 데이터를 넣지만, 꺼내는 위치가 달라 출력 순서가 정반대다.

구분	스택 (Stack)	큐 (Queue)
입출력 원칙	LIFO (후입선출)	FIFO (선입선출)
삽입/삭제 위치	같은 끝(top)에서 넣고 뺌	뒤(rear)에서 넣고 앞(front)에서 뺌
주요 연산	push / pop / peek	offer / poll / peek

활용 예시

자료구조	실무 예	이유
스택	함수 호출 스택, Undo/Redo, 브라우저 뒤로가기, 괄호·태그 매칭	가장 최근 상태로 되돌아가야 하므로 마지막 것이 먼저 나와야 함
큐	메시지 큐(Kafka), 스레드풀 작업 대기열, 요청 버퍼링, 프린터 스풀러	먼저 들어온 작업을 먼저 처리해 공정성·순서를 보존

스택 - 호출 스택의 내부

스택의 대표 사례는 호출 스택(call stack)가 있다.

• 메서드 호출 시 스택 프레임이 push되며, 이 프레임에 지역 변수·매개변수·복귀 주소(return address)가 담김
• return을 만나면 가장 위 프레임을 pop하고 복귀 주소로 점프 → 호출의 역순으로 정리되는 LIFO 그 자체
• 재귀가 너무 깊어 프레임이 스택 크기 한계를 넘으면 StackOverflowError 발생

큐 - 스레드풀 대기열의 내부

큐의 대표 사례는 스레드풀의 작업 대기열이다.

• ThreadPoolExecutor는 내부에 BlockingQueue를 두고, 제출된 작업을 들어온 순서대로 워커 스레드에 전달
• 생산 속도가 소비 속도보다 빠를 때 큐가 완충(버퍼) 역할을 해 순간 부하를 흡수

구현 시 자료구조 선택 - 배열과 LinkedList

스택·큐 모두 핵심 연산은 O(1)지만, 자료구조의 접근 패턴과 메모리 특성에서 차이가 난다.

큐를 LinkedList로 구현하는 이유

큐는 넣는 입구(rear)와 빼는 출구(front)가 분리된 FIFO 구조로, 배열로 만들면 이 구조가 성능 저하로 이어진다.

• dequeue 때 맨 앞(0번 인덱스)을 비운 뒤, 남은 요소를 전부 한 칸씩 앞으로 당겨야 함 → O(n)
• front에서 빼는 동작이 매번 일어나는 큐에서는 이 시프트가 그대로 누적돼, 큐가 커질수록 느려짐

배열 큐에서 맨 앞(A) 제거:
[A][B][C][D]
[B][C][D][ ]   ← B·C·D를 한 칸씩 앞으로 이동 (O(n))

LinkedList는 이 이동 자체가 없어서 front 삭제를 O(1)로 처리할 수 있다.

• head·tail 포인터만 두면 front 삭제는 head를 다음 노드로 옮기는 것으로 끝나 O(1)
• 양 끝 삽입·삭제가 모두 요소 이동 없이 O(1)이라, front 삭제가 잦은 큐의 정석으로 자리 잡음

스택을 배열로 구현하는 이유

스택은 한쪽 끝(top)에서만 넣고 빼는 LIFO라, 배열 끝에서의 추가·삭제나 LinkedList나 똑같이 O(1)지만, 배열이 메모리·캐시 효율에서 압도적으로 유리하다.

• 메모리 효율
  • 배열: 한 요소에 데이터 참조값 한 칸만 필요
  • LinkedList: 노드마다 데이터 참조 외에 앞뒤 포인터 2개, 객체 헤더, 정렬 패딩이 붙어 항목당 3~4배 많은 메모리를 씀
• 캐시 지역성
  • 배열: 요소가 메모리에 연속 배치돼, CPU가 한 줄을 통째로 캐시에 올리는 특성과 맞아 적중률이 높음
  • LinkedList: 노드가 힙 곳곳에 흩어져, 다음 노드를 따라갈 때마다 캐시 미스가 잦아 실제 속도가 느림
• 리사이징 비용
  • 배열은 꽉 차면 더 큰 배열로 복사하지만, 용량을 일정 비율로 늘리면 그 비용이 전체 연산에 분산돼 분할 상환(amortized)상 O(1)로 수렴
  • 따라서 확장 비용은 배열을 피할 이유가 되지 못함

메모리 회수 한 가지는 LinkedList가 유리하다.

• pop으로 빠진 노드는 곧바로 GC 대상이 되어 그만큼의 메모리가 즉시 회수됨
• 배열은 스택이 줄어도 한번 늘린 용량을 유지해, 비어 있는 칸만큼의 공간을 계속 점유

이는 자료구조 원리상의 선택일 뿐, 실무에서 직접 구현할 일은 거의 없고 Java에서는 스택·큐 모두 ArrayDeque를 쓰는 것이 공식 권장이다.

스택과 큐를 한 구조로 - 덱(Deque)

양쪽 끝에서 삽입·삭제가 모두 가능한 덱(Deque, Double-Ended Queue)을 쓰면 스택과 큐를 하나의 자료구조로 표현할 수 있다.

사용법	호출	동작
스택처럼 쓰기	addFirst + removeFirst	LIFO
큐처럼 쓰기	addLast + removeFirst	FIFO

• Java에서는 Deque 인터페이스가 이 역할을 하며, 구현체로 ArrayDeque(권장)와 LinkedList가 있음
• 한쪽 끝만 쓰면 스택, 양 끝을 쓰면 큐가 되므로 덱 하나로 둘을 모두 대체 가능

Java의 Stack 클래스를 쓰지 않는 이유

Java의 java.util.Stack은 이름과 달리 인터페이스가 아니라 레거시 동적 배열인 Vector를 상속한 클래스다.

public class Stack<E> extends Vector<E> {
    // ...
}

Vector는 자바 1.0 시절의 컬렉션으로 모든 메서드가 synchronized로 묶인 스레드 안전 동적 배열이며, Stack의 문제 대부분이 이 상속에서 나온다.

문제	내용
상속(IS-A) 오용	Vector를 상속해 LIFO와 무관한 연산이 모두 노출됨
불필요한 동기화	모든 메서드가 synchronized → 단일 스레드에서도 락 비용
순회 순서 혼란	인덱스 0이 바닥이라 for/iterator 순회 시 LIFO가 아님

1. 상속으로 인한 캡슐화 붕괴

스택은 push·pop·peek만 노출해야 하는데, Vector를 상속한 탓에 임의 위치 접근 연산까지 그대로 외부에 노출된다.

void main() {
    Stack<Integer> stack = new Stack<>();
    stack.push(1);
    stack.push(2);
    stack.add(0, 99);   // LIFO 위반인데 컴파일됨
    stack.remove(1);    // 스택이 할 수 없어야 할 연산
}

2. 불필요한 동기화 비용

Vector 상속으로 모든 연산이 synchronized라, 멀티스레드가 아닌 상황에서도 락 비용이 항상 발생한다.

• 단일 스레드에서는 모니터 락 획득·해제가 순수 오버헤드
• 메서드 단위 동기화는 복합 연산(검사 후 pop 등)의 원자성을 보장하지 못해, 실제 동시성 안전에도 충분치 않음
• 동시성이 필요하면 ConcurrentLinkedDeque처럼 목적에 맞게 설계된 컬렉션을 쓰는 편이 나음

3. 직관과 어긋나는 순회 순서

Vector 기반이라 인덱스 0이 가장 먼저 들어온 바닥 요소다.

• for문이나 iterator로 순회하면 LIFO 순서가 아니라 삽입 순서(바닥 → top)로 나옴

void main() {
    Stack<Integer> s = new Stack<>();
    s.push(1);
    s.push(2);
    s.push(3);
    for (int x : s)
        System.out.print(x);  // 1 2 3  (top인 3이 먼저일 줄 알았으나 반대)
}

Deque 인터페이스와 ArrayDeque

java.util.Deque(Java 6+)는 양 끝 삽입·삭제를 정의한 인터페이스로, Vector를 상속하지 않아 인덱스 접근 연산이 없고 LIFO 캡슐화가 지켜진다.

스택 연산	Deque 대응 연산
push	addFirst
pop	removeFirst
peek	peekFirst

레거시 Stack과 비교하면 다음과 같다.

구분	Stack (class)	Deque (interface)
타입	Vector 상속 클래스	인터페이스
동기화	전 메서드 synchronized	없음 (필요 시 외부에서 감쌈)
임의 인덱스 접근	get(i) 등 노출 (캡슐화 붕괴)	없음 (LIFO 유지)
순회 순서	바닥 → top (직관 위배)	top → 바닥 (LIFO 일관)
성능	느림 (락 + Vector)	빠름 (ArrayDeque 원형 배열)
권장	비권장 (레거시)	권장

ArrayDeque가 빠른 이유

ArrayDeque는 원형 배열(circular array)에 head/tail 인덱스를 두고 동작한다.

• 양 끝 삽입·삭제를 배열 끝에서 인덱스만 회전시켜 O(1)로 처리하고, 데이터 이동이 없음
• 내부 용량을 2의 거듭제곱으로 유지해, 인덱스가 배열 끝을 넘어 처음으로 되감기는 것(wrap-around)을 비싼 나머지 연산(%) 대신 비트 마스크(& (capacity-1))로 계산
• 연속된 배열이라 캐시 지역성이 좋아, 노드가 흩어지는 LinkedList보다 순회·접근이 빠름

앞서 본 배열 큐는 front를 비울 때마다 뒤 요소를 전부 당겨야 했지만(O(n)), 원형 배열은 head 인덱스만 옮겨 같은 동작을 O(1)로 처리한다.

원형 배열에서 앞(front) 제거: head 인덱스만 이동
[A][B][C][D]   head=0, tail=4
[ ][B][C][D]   head=1          ← A 자리는 그대로 두고 head만 +1 (요소 이동 없음, O(1))