스택과 큐 (Stack & Queue)

스택(Stack)과 큐(Queue)는 데이터를 넣고 빼는 순서에 제약을 둔 대표적인 선형 자료구조다. 스택은 나중에 넣은 것을 먼저 꺼내는 후입선출(LIFO, Last In First Out) 구조이고, 큐는 먼저 넣은 것을 먼저 꺼내는 선입선출(FIFO, First In First Out) 구조다. 두 구조 모두 핵심 연산이 O(1)로 동작하며, 함수 호출 관리부터 작업 대기열까지 소프트웨어 전반의 기반 개념으로 쓰인다.

스택의 개념과 동작

스택은 한쪽 끝(top)에서만 삽입과 삭제가 일어난다. 요소를 넣는 연산을 푸시(push), 꼭대기 요소를 꺼내는 연산을 팝(pop), 꺼내지 않고 확인만 하는 연산을 피크(peek)라고 부른다. 접시를 쌓아 올렸다가 위에서부터 걷어내는 모습과 같다.

스택의 대표적인 쓰임은 함수 호출 스택(call stack)이다. 함수가 호출되면 지역 변수와 복귀 주소를 담은 스택 프레임(stack frame)이 쌓이고, 함수가 끝나면 걷힌다. 재귀가 너무 깊어지면 발생하는 스택 오버플로(stack overflow)가 바로 이 구조에서 나온 말이다. 그 밖에 실행 취소(undo) 기능, 괄호 짝 검사, 후위 표기식 계산, 그래프의 깊이 우선 탐색(DFS, Depth First Search), 브라우저 방문 기록 관리 등이 모두 스택으로 풀린다.

큐의 개념과 동작

큐는 뒤(rear)로 넣고 앞(front)에서 꺼낸다. 삽입을 인큐(enqueue), 삭제를 디큐(dequeue)라고 한다. 줄을 선 순서대로 처리되는 대기열 그 자체다.

큐는 순서 보장이 필요한 모든 곳에 등장한다. 그래프의 너비 우선 탐색(BFS, Breadth First Search), 운영체제의 작업 스케줄링, 프린터 출력 대기열, 메시지 큐(message queue)를 이용한 서버 간 비동기 통신이 대표 사례다. 변형으로는 양쪽 끝에서 모두 넣고 뺄 수 있는 덱(Deque, Double Ended Queue), 우선순위가 높은 요소부터 나오는 우선순위 큐(priority queue)가 있다. 우선순위 큐는 보통 힙(Heap)으로 구현되어 삽입과 삭제가 O(log n)이라는 점에서 일반 큐와 구별된다.

구현 방식과 시간 복잡도

스택은 배열이나 연결 리스트 어느 쪽으로도 쉽게 구현된다. 배열 기반은 끝에서만 넣고 빼므로 이동 비용이 없다. 큐를 배열로 구현할 때는 주의가 필요하다. 앞에서 요소를 빼며 전체를 당기면 디큐가 O(n)이 되므로, front와 rear 인덱스를 나머지 연산으로 순환시키는 원형 큐(circular queue)로 만들어 O(1)을 유지한다.

구분	스택	큐
순서 규칙	후입선출(LIFO)	선입선출(FIFO)
삽입/삭제 위치	같은 쪽(top)	삽입은 rear, 삭제는 front
삽입/삭제 비용	O(1)	O(1) (원형 큐 기준)
대표 활용	호출 스택, 실행 취소, DFS	BFS, 작업 스케줄링, 메시지 큐
자바 권장 구현	ArrayDeque	ArrayDeque, LinkedList

자바(Java)의 Stack 클래스는 오래된 Vector를 상속해 모든 연산에 동기화 오버헤드가 있으므로, 실무에서는 스택과 큐 모두 ArrayDeque를 쓰는 것이 권장된다.

class CircularQueue {
    int[] data;
    int front = 0, rear = 0, size = 0;

    CircularQueue(int capacity) { data = new int[capacity]; }

    void enqueue(int x) {
        if (size == data.length) throw new IllegalStateException("full");
        data[rear] = x;
        rear = (rear + 1) % data.length;
        size++;
    }

    int dequeue() {
        if (size == 0) throw new IllegalStateException("empty");
        int x = data[front];
        front = (front + 1) % data.length;
        size--;
        return x;
    }
}