스택과 큐의 추상 자료형(ADT)

스택과 큐는 어떤 순서로 꺼내느냐를 정해 주는 자료구조입니다. 스택은 접시를 위에 쌓고 위에서 꺼내는 방식이고, 큐는 줄을 서서 앞에서 빠지는 방식입니다. 이 순서 규칙이 바뀌면 DFS/BFS 같은 상위 알고리즘 결과도 바로 달라집니다.

여기서는 라이브러리 이름 암기보다 스택/큐 계약(LIFO/FIFO)을 코드에서 안정적으로 지키는 방법을 익힙니다. 빈 구조 처리 같은 실수 포인트도 함께 점검합니다.

핵심 개념 해설

스택과 큐는 라이브러리 이름보다 꺼내는 순서 규칙을 우선 이해해야 헷갈리지 않습니다. 각 연산을 볼 때 입력 하나를 넣고 어떤 값이 먼저 나오는지 직접 써 보세요.

스택(Stack)은 나중에 넣은 값을 먼저 꺼내는 구조입니다. 정의로는 LIFO(Last In First Out) 순서를 보장하는 선형 ADT입니다. push 1, push 2, pop을 순서대로 실행하면 2가 나옵니다.

큐(Queue)는 먼저 넣은 값을 먼저 꺼내는 구조입니다. 정확한 계약은 FIFO(First In First Out) 순서 보장입니다. enqueue 1, enqueue 2, dequeue를 실행하면 1이 먼저 나옵니다.

ADT 계약은 연산 이름과 기대 결과를 코드 바깥에서 우선 고정한 약속입니다. 입력/출력 형식, 빈 구조 처리 방식, 실패 시 동작까지 인터페이스 수준에서 정합니다. 예를 들어 빈 스택 pop에서 예외를 던질지 특수값을 반환할지 미리 합의해 두면 디버깅이 빨라집니다.

ADT 계약이 실무에서 중요한 이유

같은 DFS/BFS라도 스택/큐 계약이 흔들리면 탐색 순서가 완전히 달라집니다.
또한 예외 정책(빈 구조 pop/dequeue) 미정의는 런타임 오류의 주요 원인입니다.

ADT 계약을 우선 문서화하면 다음 이점이 생깁니다.

알고리즘 코드와 자료구조 구현 분리
테스트 케이스 재사용 가능
교체 구현(배열/연결 리스트) 실험이 쉬움
지금 작성 중인 코드에서 빈 구조 예외 정책을 우선 고정할 수 있음

계약 위반 오답 재현으로 검증하기

오답 -> 디버깅 -> 교정 -> 검증 순서를 먼저 고정하고 예제를 따라가면 경계 버그를 빠르게 줄일 수 있습니다.

스택과 큐의 차이는 같은 입력을 처리해 보면 바로 드러납니다.

입력 순서: push/enqueue 1, 2, 3
추가 연산: pop/dequeue 2회

스택(LIFO)은 3, 2가 나옵니다.
큐(FIFO)는 1, 2가 나옵니다.
같은 연산 집합이라도 계약이 다르면 상위 알고리즘 결과가 바뀝니다.

스택 ADT 기본 계약

문제 의도: 스택의 핵심 동작(push, peek, pop)과 빈 스택 처리 규칙을 가장 짧은 코드로 고정합니다.
입력 예시: push(10), push(20), peek(), pop(), pop()
출력 예시: 20, 20, 10

main.cpp

#include <iostream>
#include <vector>
using namespace std;

int peekStack(const vector<int>& stack) {
    if (stack.empty()) return -1;
    return stack.back();
}

int popStack(vector<int>& stack) {
    if (stack.empty()) return -1;
    int value = stack.back();
    stack.pop_back();
    return value;
}

int main() {
    vector<int> stack;
    stack.push_back(10);
    stack.push_back(20);

    cout << peekStack(stack) << "\n";
    cout << popStack(stack) << "\n";
    cout << popStack(stack) << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static int peekStack(List<Integer> stack) {
        if (stack.isEmpty()) return -1;
        return stack.get(stack.size() - 1);
    }

    static int popStack(List<Integer> stack) {
        if (stack.isEmpty()) return -1;
        return stack.remove(stack.size() - 1);
    }

    public static void main(String[] args) {
        List<Integer> stack = new ArrayList<>();
        stack.add(10);
        stack.add(20);

        System.out.println(peekStack(stack));
        System.out.println(popStack(stack));
        System.out.println(popStack(stack));
    }
}

main.py

def peek_stack(stack):
    if not stack:
        return -1
    return stack[-1]

def pop_stack(stack):
    if not stack:
        return -1
    return stack.pop()

stack = [10, 20]
print(peek_stack(stack))  # 20
print(pop_stack(stack))   # 20
print(pop_stack(stack))   # 10

main.rs

fn peek_stack(stack: &[i32]) -> i32 {
    *stack.last().unwrap_or(&-1)
}

fn pop_stack(stack: &mut Vec<i32>) -> i32 {
    stack.pop().unwrap_or(-1)
}

fn main() {
    let mut stack = vec![10, 20];
    println!("{}", peek_stack(&stack));
    println!("{}", pop_stack(&mut stack));
    println!("{}", pop_stack(&mut stack));
}

스택/큐 ADT 확인 불변식 초기 확인

스택 계약의 핵심은 가장 최근 값이 우선 나온다는 순서입니다.
코드를 단순하게 유지하려고 빈 스택에서는 -1을 반환하는 규칙으로 통일했습니다.
실전에서는 문제 조건에 맞게 -1, None, 예외 중 하나를 처음에 정하고 끝까지 일관되게 쓰면 됩니다.

평균 시간복잡도: push/pop/peek 모두 O(1)
최악 시간복잡도: O(1) (리스트 재할당 제외)
공간복잡도: O(N)

큐 ADT 구현

문제 의도: 큐 ADT의 FIFO 계약과 빈 큐 예외 처리를 코드로 고정합니다.
입력 예시: enqueue(10), enqueue(20), front(), dequeue(), dequeue()
출력 예시: 10, 10, 20 enqueue는 뒤에 넣고, dequeue는 앞에서 꺼내는 연산입니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

void enqueue(vector<int>& q, int value) { q.push_back(value); }

int dequeue(vector<int>& q, int& head) {
    if (head == static_cast<int>(q.size())) return -1;
    int value = q[head];
    head += 1;
    return value;
}

int front(const vector<int>& q, int head) {
    if (head == static_cast<int>(q.size())) return -1;
    return q[head];
}

int main() {
    vector<int> q;
    int head = 0;
    for (int x : {10, 20, 30}) enqueue(q, x);
    cout << front(q, head) << "\n";
    cout << dequeue(q, head) << "\n";
    cout << dequeue(q, head) << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void enqueue(List<Integer> q, int value) {
        q.add(value);
    }

    static int dequeue(List<Integer> q, int[] head) {
        if (head[0] == q.size()) return -1;
        int value = q.get(head[0]);
        head[0] += 1;
        return value;
    }

    static int front(List<Integer> q, int[] head) {
        if (head[0] == q.size()) return -1;
        return q.get(head[0]);
    }

    public static void main(String[] args) {
        List<Integer> q = new ArrayList<>();
        int[] head = {0};
        for (int x : new int[]{10, 20, 30}) enqueue(q, x);
        System.out.println(front(q, head));
        System.out.println(dequeue(q, head));
        System.out.println(dequeue(q, head));
    }
}

main.py

def enqueue(q, value):
    q.append(value)

def dequeue(q, head):
    if head[0] == len(q):
        return -1
    value = q[head[0]]
    head[0] += 1
    return value

def front(q, head):
    if head[0] == len(q):
        return -1
    return q[head[0]]

q = []
head = [0]
for x in [10, 20, 30]:
    enqueue(q, x)
print(front(q, head))    # 10
print(dequeue(q, head))  # 10
print(dequeue(q, head))  # 20

main.rs

fn enqueue(q: &mut Vec<i32>, value: i32) {
    q.push(value);
}

fn dequeue(q: &Vec<i32>, head: &mut usize) -> i32 {
    if *head == q.len() {
        return -1;
    }
    let value = q[*head];
    *head += 1;
    value
}

fn front(q: &Vec<i32>, head: usize) -> i32 {
    if head == q.len() {
        return -1;
    }
    q[head]
}

fn main() {
    let mut q: Vec<i32> = Vec::new();
    let mut head: usize = 0;
    for x in [10, 20, 30] {
        enqueue(&mut q, x);
    }
    println!("{}", front(&q, head));
    println!("{}", dequeue(&q, &mut head));
    println!("{}", dequeue(&q, &mut head));
}

스택/큐 ADT 확인 연산 순서 추적

큐는 먼저 들어온 값이 먼저 나와야 하므로 양끝 연산이 효율적인 구현이 필요합니다.
파이썬에서는 deque가 리스트 pop(0)보다 안정적인 선택입니다.
ADT 계약이 고정되어 있으면 내부 구현 교체가 상위 코드에 영향을 덜 줍니다.

평균 시간복잡도: enqueue/dequeue/front 모두 O(1)
최악 시간복잡도: O(1)
공간복잡도: O(N)

스택/큐 표현 방식 판정 축

스택/큐 선택은 문제 요구 순서에서 결정됩니다.

되돌리기/괄호 검사/호출 추적: 스택
작업 스케줄/레벨 순회/버퍼링: 큐
우선순위가 있으면: 우선순위 큐(별도 ADT)

문제의 처리 순서를 우선 읽으면 구조 선택이 쉬워집니다.

배열 큐와 원형 큐 구현 복잡도 비교

스택/큐 자체는 단순하지만 구현 선택에서 차이가 납니다.

배열 기반: 캐시 친화적이고 단순함
연결 기반/덱 기반: 앞쪽 삭제 연산에 강함
고정 크기 버퍼: 메모리 예측 가능, 오버플로우 정책 필요

ADT 계약은 같아도 운영 요구에 맞춰 내부 구현은 달라질 수 있습니다.

고정 용량 큐 정책

문제 의도: 용량이 제한된 큐에서 overflow 정책을 명시적으로 처리합니다.
입력 예시: capacity=3, 순서대로 enqueue 1,2,3,4
출력 예시: 정책에 따른 최종 큐 상태(예: drop-oldest면 2,3,4) drop-oldest는 꽉 찼을 때 맨 앞 값을 버리고 새 값을 넣는 정책입니다.

운영 시스템에서는 큐가 무한히 커질 수 없으므로 overflow 정책이 필요합니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

void enqueueDropOldest(vector<int>& q, int capacity, int value) {
    if (static_cast<int>(q.size()) == capacity) {
        q.erase(q.begin());
    }
    q.push_back(value);
}

int main() {
    vector<int> q;
    int capacity = 3;
    for (int x : {1, 2, 3, 4, 5}) enqueueDropOldest(q, capacity, x);
    for (int x : q) cout << x << " ";
    cout << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static void enqueueDropOldest(List<Integer> q, int capacity, int value) {
        if (q.size() == capacity) q.remove(0);
        q.add(value);
    }

    public static void main(String[] args) {
        List<Integer> q = new ArrayList<>();
        int capacity = 3;
        for (int x : new int[]{1, 2, 3, 4, 5}) enqueueDropOldest(q, capacity, x);
        System.out.println(q); // [3, 4, 5]
    }
}

main.py

def enqueue_drop_oldest(q, capacity, value):
    if len(q) == capacity:
        q.pop(0)
    q.append(value)

q = []
capacity = 3
for x in [1, 2, 3, 4, 5]:
    enqueue_drop_oldest(q, capacity, x)
print(q)  # [3, 4, 5]

main.rs

fn enqueue_drop_oldest(q: &mut Vec<i32>, capacity: usize, value: i32) {
    if q.len() == capacity {
        q.remove(0);
    }
    q.push(value);
}

fn main() {
    let mut q: Vec<i32> = Vec::new();
    let capacity = 3usize;
    for x in [1, 2, 3, 4, 5] {
        enqueue_drop_oldest(&mut q, capacity, x);
    }
    println!("{:?}", q);
}

스택/큐 ADT 확인 실패사례 재실행 확인

큐 ADT에 용량 제약을 추가하면 정책 선택이 필수입니다.
드롭 정책은 drop-oldest, drop-newest, block 등으로 나뉘며 서비스 성격에 따라 선택해야 합니다.
ADT 계약을 확장할 때도 기본 연산 의미(FIFO)는 유지되어야 상위 로직과 호환됩니다.

평균 시간복잡도: enqueue_drop_oldest O(1), snapshot O(N)
최악 시간복잡도: enqueue_drop_oldest O(1), snapshot O(N)
공간복잡도: O(capacity) (snapshot 반환 시 추가 O(N))

스택/큐 실패 로그 실수 포인트

자주 발생하는 실패 패턴입니다.

빈 구조 예외 처리 누락
큐를 리스트 pop(0)으로 구현해 성능 저하
스택/큐 의미를 혼동해 탐색 결과 왜곡
멀티스레드 환경에서 동기화 없이 공유

ADT 테스트는 정상 케이스뿐 아니라 언더플로우 케이스를 반드시 포함해야 합니다.

연산 계약 비용 모델 정리

입력 분포가 치우치면 같은 알고리즘이라도 성능 체감이 달라지므로, 판단 축을 데이터 특성과 함께 기록해 두는 편이 안전합니다.

ADT	핵심 연산	평균 시간	최악 시간	공간
스택	push/pop/peek	`O(1)`	`O(1)`	`O(N)`
큐	enqueue/dequeue/front	`O(1)`	`O(1)`	`O(N)`

복잡도 계약을 지키는 구현을 선택하는 것이 ADT 활용의 핵심입니다.

제출 직전 예외 입력 체크

ADT 이름이 같아도 언어 라이브러리마다 예외 정책이 다를 수 있습니다.
성능 측정 시 입력 패턴(연속 push/pop vs 교차 연산)을 분리해 봐야 합니다.
디버깅 로그는 구조 전체 출력보다 상단/전단 값 중심으로 보는 것이 효율적입니다.
API 문서에 연산 의미와 예외 조건을 함께 명시해야 협업 오류가 줄어듭니다.

ADT 구현 전후 점검 목록

빈 구조에서의 동작(예외/특수값)을 명확히 정의했는가
스택/큐 계약(LIFO/FIFO)을 테스트로 검증했는가
구현 교체 시에도 ADT 인터페이스가 유지되는가
용량 제한과 overflow 정책을 문제 요구에 맞게 정했는가

스택·큐 모델 정리

스택과 큐는 구현보다 계약이 우선인 구조입니다.
ADT 관점으로 설계하면 알고리즘 코드는 단순해지고, 구현 교체와 성능 개선도 훨씬 쉬워집니다.

스택과 큐의 추상 자료형(ADT)

목차