[자료구조/C언어] 스택(Stack)과 큐(Queue) 개념 및 차이점 완전 정리 (시험 단골 주제)

컴퓨터공학과 자료구조 시험이나 정보처리기사에서 단 한 번도 빠지지 않고 나오는 단골 문제가 있습니다. 바로 대표적인 선형 자료구조인 스택(Stack)과 큐(Queue)입니다.

두 자료구조는 데이터를 저장하고 꺼내는 '순서(Rule)'에서 결정적인 차이가 있습니다. 개념부터 동작 원리, C언어 예제, 그리고 시험 핵심 포인트까지 한눈에 보기 쉽게 정리해 드립니다.

1. 스택(Stack)이란? — LIFO (후입선출)

스택(Stack)은 '차곡차곡 쌓아 올린 더미'라는 뜻입니다.

• 원리: 가장 나중에 들어간 데이터가 가장 먼저 나오는 LIFO (Last-In, First-Out, 후입선출) 방식입니다.
• 비유: 프링글스 과자통, 쌓아놓은 접시 더미, 뒤로 가기(Ctrl+Z) 기능
• 주요 용어:
  • Push: 스택에 데이터를 삽입하는 연산
  • Pop: 스택에서 가장 위에 있는 데이터를 제거 및 추출하는 연산
  • Top: 스택의 가장 맨 위(최근에 들어온 데이터) 위치를 가리키는 지점

💡 스택의 주요 활용 예시 (시험 단골)

1. 함수의 호출 관리 (Call Stack): 재귀 함수 호출 시 메모리 관리
2. 웹 브라우저 뒤로 가기: 가장 최근 방문한 페이지부터 출력
3. 수식의 후위 표기법(Postfix) 계산 및 괄호 검사

2. 큐(Queue)란? — FIFO (선입선출)

큐(Queue)는 '줄을 서서 기다리는 것'을 의미합니다.

• 원리: 가장 먼저 들어간 데이터가 가장 먼저 나오는 FIFO (First-In, First-Out, 선입선출) 방식입니다.
• 비유: 맛집 줄 서기, 일방통행 터널, 프린터 인쇄 대기열
• 주요 용어:
  • Enqueue (또는 Push): 큐의 맨 뒤에 데이터를 삽입하는 연산
  • Dequeue (또는 Pop): 큐의 맨 앞에서 데이터를 제거 및 추출하는 연산
  • Front (Head): 데이터가 나가는 출구(가장 오래된 데이터)
  • Rear (Tail): 데이터가 들어오는 입구(가장 최근 데이터)

💡 큐의 주요 활용 예시 (시험 단골)

1. 프로세스/작업 스케줄링: 운영체제(OS)에서 CPU 작업 대기열
2. 프린터 인쇄 대기열: 먼저 요청된 문서부터 순서대로 출력
3. 너비 우선 탐색 (BFS, Breadth-First Search) 알고리즘

3. C언어 간단 코드로 보는 동작 방식

C언어 배열을 활용하여 데이터가 빠져나가는 순서를 비교해 보겠습니다.

① 스택 (Stack): 나중에 넣은 30이 먼저 출력됨

C

 

#include <stdio.h>

int main() {
    int stack[5];
    int top = -1;

    // Push (10, 20, 30 순서로 삽입)
    stack[++top] = 10;
    stack[++top] = 20;
    stack[++top] = 30;

    // Pop (출력)
    printf("%d ", stack[top--]); // 30
    printf("%d ", stack[top--]); // 20
    printf("%d\n", stack[top--]); // 10
    // 출력 결과: 30 20 10 (역순)
    return 0;
}

② 큐 (Queue): 먼저 넣은 10이 먼저 출력됨

C

 

#include <stdio.h>

int main() {
    int queue[5];
    int front = 0, rear = 0;

    // Enqueue (10, 20, 30 순서로 삽입)
    queue[rear++] = 10;
    queue[rear++] = 20;
    queue[rear++] = 30;

    // Dequeue (출력)
    printf("%d ", queue[front++]); // 10
    printf("%d ", queue[front++]); // 20
    printf("%d\n", queue[front++]); // 30
    // 출력 결과: 10 20 30 (입력 순서 동일)
    return 0;
}

4. 한눈에 비교하는 핵심 요약 (시험 대비 필수)

구분	스택 (Stack)	큐 (Queue)
구조 방식	LIFO (Last-In, First-Out, 후입선출)	FIFO (First-In, First-Out, 선입선출)
입출력 방향	한쪽 끝(Top)에서만 입출력 발생	입구(Rear)와 출구(Front)가 서로 다름
삽입 연산	Push	Enqueue
삭제 연산	Pop	Dequeue
대표 응용	재귀함수, 수식 괄호 검사, Undo(Ctrl+Z)	OS 스케줄링, BFS 탐색, 프린터 대기열

5. 시험 단골 출제 문제 유형

1. Q. 스택에 A, B, C, D 순서로 Push 한 후 Pop을 2번 실행했을 때 남아있는 데이터는?
2. 👉 C, D가 제거되어 A, B만 남습니다. (나중에 들어온 D, C 순으로 먼저 꺼내짐)
3. Q. 웹 브라우저의 '뒤로 가기' 기능과 가장 관련이 깊은 자료구조는?
4. 👉 스택(Stack)입니다.
5. Q. 대기열 처리나 너비 우선 탐색(BFS)에 사용하는 자료구조는?
6. 👉 큐(Queue)입니다.