[자료구조 기초] 추상 자료형 (ADT) - 스택 · 큐 · 덱

prev

시퀀스 자료구조 — 배열·연결 리스트·스택·큐

자료구조를 ‘창고 정리법’에 비유해 시퀀스 구조의 본질을 설명합니다. 배열·연결 리스트·스택·큐의 메모리 배치와 연산 특성, 선택 기준을 간단한 STL 코드(std::array/list/stack/queue)로 정리했습니다.

Gibeom KimGibeom Kim

추상 자료형 (Abstract Data Type, ADT)란?

추상 자료형(ADT, Abstract Data Type)은 데이터를 어떻게 저장할지에 대한 세부 구현은 감추고, 어떤 연산이 가능한지만 규약으로 정의한 자료형을 말한다

예를 들어, 배열이나 연결 리스트 같은 시퀀스 자료구조는 데이터의 저장 방식에 초점을 맞추지만, ADT는 그 위에 “데이터를 어떤 규칙에 따라 다룰 수 있는가”에 집중한다.

대표적인 ADT로는 스택(Stack) 과 큐(Queue) 가 있다.

• 스택(Stack) 은 후입선출(LIFO, Last In First Out) 규칙을 따른다. → 나중에 들어간 데이터가 먼저 나온다.
• 큐(Queue) 는 선입선출(FIFO, First In First Out) 규칙을 따른다. → 먼저 들어간 데이터가 먼저 나온다.

즉, 스택과 큐는 그 자체로 특정한 “사용 규약”을 정의한 ADT이며, 실제 구현은 배열이나 연결 리스트 같은 시퀀스 자료구조 위에서 이루어진다.

이처럼 ADT는 “무엇을 할 수 있는가(연산)”에 집중하고, “어떻게 구현되는가(배열, 연결 리스트 등)”는 분리해서 생각하는 것이 핵심이다.

본 게시글에서는 스택과 큐, 그리고 덱 및 다양한 변형 ADT(추후 추가 예정)에 대해서 살펴본다.

스택 (Stack)

후입 선출 (LIFO, 나중에 들어간 원소가 먼저 나오는) 형태의 추상 자료형이다. 알고리즘 구조에서 되돌리기, 괄호 검사, DFS호출 스택 등에서 사용된다. 보통 한쪽 끝에서만 작업이 일어나기 때문에 단순하고 빠르다고 생각하면 된다.

예컨데 프링글스 통을 생각해보면 된다. 먼저 들어간 과자가 나중에 나오는 것과 같은 구조이다. 이러한 특징 때문에 최근 것부터 처리 해야하는 상황, 이력 및 스냅샷 관리, 중첩 상태 관리 등에서 주로 사용된다.

c++ 표준 라이브러리에서는 std::stack 으로 제공되고 있다. 다음과 같이 사용할 수 있다.

#include <stack>

std::stack<int> st;
st.push(7);
st.push(8);
st.pop();       // 8 제거
int t = st.top(); // 7

큐 (Queue)

선입선출 (FIFO, 먼저 들어온 원소 부터 먼저 나오는) 형태의 추상 자료형이다. 주로 대기열(이벤트, 작업 처리), 버퍼링, BFS등에 사용된다. 예컨데 맛집 줄서기를 생각해보면 된다. 이렇듯 입력 순서대로 공정 처리가 필요할 때, 생산자-소비자 모델의 기본이 된다.

c++ 표준 라이브러리에서는 std::queue 로 제공되고 있다. 다음과 같이 사용할 수 있다.

#include <queue>

std::queue<int> q;
q.push(1);
q.push(2);
q.pop();         // 1 제거
int f = q.front(); // 2

#include <deque>

void demoDeque()
{
    std::deque<int> dq;
    dq.push_front(1);
    dq.push_back(2);
    dq.pop_front(); // 1 제거
    dq.pop_back();  // 2 제거
}

덱(Deque)

덱(Deque, Double-Ended Queue)은스택과 큐를 확장한 형태의 추상 자료형(ADT) 으로, 이름 그대로 Double-Ended Queue를 뜻한다. 가장 큰 특징은 앞과 뒤 양쪽에서 삽입과 삭제가 모두 가능하다는 점이다.

특징

• 양쪽 끝에서 삽입(push_front, push_back)과 삭제(pop_front, pop_back) 모두 가능.
• 배열 기반, 연결 리스트 기반으로 구현 가능.
• 스택/큐 기능을 모두 포함하는 범용성 높은 구조.

활용 사례

• 슬라이딩 윈도우 최댓값/최솟값 문제: 덱을 이용하면 전체를 O(n)에 해결 가능.
• 양방향 탐색: BFS/DFS 혼합 탐색, 또는 앞뒤 모두에서 데이터가 유입되는 시뮬레이션.
• 캐시/버퍼: 제한된 크기에서 앞뒤 양쪽 처리가 필요한 상황.

c++ 표준 라이브러리에서는 std::deque 로 제공된다. 다음과 같이 사용할 수 있다.

#include <iostream>
#include <deque>

void demoDeque()
{
    std::deque<int> dq;

    // 뒤쪽에 원소 삽입
    dq.push_back(10); // [10]
    dq.push_back(20); // [10, 20]

    // 앞쪽에 원소 삽입
    dq.push_front(5); // [5, 10, 20]

    // 맨 앞/뒤 원소 확인
    std::cout << "Front: " << dq.front() << "\n"; // 5
    std::cout << "Back: " << dq.back() << "\n";   // 20

    // 맨 앞/뒤에서 원소 제거
    dq.pop_front(); // [10, 20]
    dq.pop_back();  // [10]

    // 중간 삽입
    dq.insert(dq.begin() + 1, 15); // [10, 15]

    // 순회
    std::cout << "Deque elements: ";
    for (auto val : dq)
    {
        std::cout << val << " ";
    }
    std::cout << "\n";

    // 크기와 비어있는지 확인
    std::cout << "Size: " << dq.size() << "\n";
    std::cout << "Empty: " << std::boolalpha << dq.empty() << "\n";
}

우선순위 큐 (Priority Queue)

우선순위 큐는 일반적인 큐(Queue)의 변형 ADT로, 단순히 “먼저 들어온 순서(FIFO)”에 따라 처리하는 것이 아니라, 우선순위가 높은 원소부터 꺼내는 규칙을 가진 자료구조이다.

즉, 삽입은 자유롭게 할 수 있지만, 삭제 연산(pop)은 항상 현재 저장된 원소 중 가장 높은 우선순위 원소가 선택된다.

c++ 표준 라이브러리에서는 std::priority_queue로 제공이 된다. 다음과 같이 사용할 수 있다.

#include <queue>
#include <vector>
#include <functional>
#include <iostream>

void demoPriorityQueue()
{
    std::priority_queue<int> max_heap; // 최대 힙
    max_heap.push(3);
    max_heap.push(1);
    max_heap.push(5);

    std::cout << "Max heap top: " << max_heap.top() << "\n"; // 5

    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 최소 힙
    min_heap.push(3);
    min_heap.push(1);
    min_heap.push(5);

    std::cout << "Min heap top: " << min_heap.top() << "\n"; // 1
}

요약

예제 풀이

같은 숫자는 싫어 (자료구조) - 프로그래머스

프로그래머스 lv1 자료구조 관련 문제인 ‘같은 숫자는 싫어’의 풀이입니다. std::vector을 stack 처럼 사용해서 풀이를 진행하였습니다.

Gibeom KimGibeom Kim

올바른 괄호: 프로그래머스

프로그래머스 lv2 올바른 괄호의 두 가지 버전의 풀이 방법에 대해서 다룹니다.

Gibeom KimGibeom Kim