함께 배우는 수업 · 컴퓨터/정보

스택(Stack)과 큐(Queue)

후입선출(LIFO) 구조의 스택과 선입선출(FIFO) 구조의 큐, 원형 큐와 덱(Deque), 우선순위 큐까지 핵심 추상 자료형(ADT)의 원리와 응용을 학습합니다.

이 수업에서 해 볼 일

스택과 큐의 제거 순서를 실제 연산에서 추적한다

먼저 알면 좋은 것: 배열(Array)과 연결 리스트(Linked List)의 삽입·삭제 원리 · 포인터/인덱스(Top, Front, Rear) 개념 · 함수 호출과 복귀의 기본 흐름

오늘의 목표

가입 없이 시작할 수 있어요. 설명을 읽고, 함께 연습한 뒤, 처음 보는 문제에서 직접 확인합니다.

판단 과정과 비교 사례

스택은 최근에 넣은 항목부터 꺼내고, 큐는 먼저 넣은 항목부터 꺼낸다. 연산이 끝날 때마다 남아 있는 순서를 적어 보면 중간에 제거된 원소를 다시 고르는 실수를 막을 수 있다.실행 취소는 최근 작업부터 되돌리므로 스택과 잘 맞는다. 대기표 순서대로 처리하는 창구는 큐와 잘 맞으며, 중요도가 먼저라면 우선순위 큐를 고려한다.원형 큐에서는 인덱스가 배열 끝을 지나면 나머지 연산으로 처음에 돌아온다. 저장 위치를 재사용하는 것과 처리 순서를 거꾸로 하는 것은 다르다.

1. 스택 (Stack) - LIFO (후입선출) 구조와 응용

- 동작 원리: 프링글스 감자칩 통이나 접시 쌓기처럼 한쪽 끝(Top)에서만 데이터의 삽입(Push)과 삭제(Pop)가 일어나는 LIFO (Last-In, First-Out: 가장 나중에 들어간 데이터가 가장 먼저 나옴) 자료구조입니다. - 주요 연산 (모두 $O(1)$ ): - push(x): Top 위치에 원소

x

를 추가합니다. (가득 찬 스택에 Push하면 Stack Overflow 발생) - pop(): Top 위치의 원소를 꺼내어 제거하고 반환합니다. (빈 스택에서 Pop하면 Stack Underflow 발생) - peek() / top(): Top 원소를 제거하지 않고 값만 확인합니다. - 시스템 및 알고리즘 핵심 활용처: 1. 함수 호출 콜 스택 (Call Stack) 및 재귀 함수 복귀 주소 저장. 2. 수식의 괄호 짝 검사 및 중위 표기식(Infix) ➔ 후위 표기식(Postfix) 변환·계산. 3. 웹 브라우저 뒤로 가기(Back), 문서 편집기 실행 취소(Undo, Ctrl+Z), 깊이 우선 탐색(DFS).스택에 A, B, C, D 순서로 데이터를 넣었다가(Push) 모두 꺼내면(Pop) D, C, B, A처럼 입력 순서가 정확히 역순으로 뒤집힙니다. 순서 뒤집기나 가장 최근 상태로의 되돌리기(Backtracking) 문제가 나오면 무조건 스택을 떠올리세요!

2. 큐 (Queue) - FIFO (선입선출) 구조와 원형 큐

- 동작 원리: 은행 창구나 매표소 대기줄처럼 뒤쪽(Rear / Back)에서는 삽입(Enqueue)만 일어나고, 앞쪽(Front)에서는 삭제(Dequeue)만 일어나는 FIFO (First-In, First-Out: 먼저 들어온 데이터가 먼저 나옴) 자료구조입니다. - 선형 큐의 문제점과 원형 큐 (Circular Queue): - 1차원 배열로 단순 큐를 구현하면 Enqueue와 Dequeue가 반복될수록 front와 rear 인덱스가 뒤로만 이동하여, 앞쪽에 빈 공간이 남는데도 배열 끝에 도달해 더 이상 삽입하지 못하는 현상이 발생합니다. - 이를 해결하기 위해 배열의 처음과 끝을 논리적으로 연결한 원형 큐(Ring Buffer)를 사용하며, 나머지 연산자(%)를 이용해 인덱스를 회전시킵니다:

\text{Rear} = (\text{Rear} + 1) \pmod N, \quad \text{Front} = (\text{Front} + 1) \pmod N

- 핵심 활용처: 운영체제 프로세스 Ready Queue, 프린터 스풀러 대기열, 네트워크 패킷 버퍼, 너비 우선 탐색(BFS), 웹 서버 요청 메시지 큐(Kafka, RabbitMQ).

예제로 살펴보기

빈 스택에 1, 2, 3을 순서대로 Push한 뒤 Pop을 1회 수행하고, 이어서 4, 5를 순서대로 Push한 뒤 남은 원소를 모두 Pop할 때 출력되는 숫자의 순서를 구하시오. 또한 후위 표기식 5 3 + 2 *를 스택으로 계산하시오.

1) 스택 입출력 순서 추적: - Push(1), Push(2), Push(3) ➔ 현재 스택: [1, 2, 3] (Top=3) - Pop() 1회 수행 ➔ '3' 출력! 현재 스택: [1, 2] - Push(4), Push(5) ➔ 현재 스택: [1, 2, 4, 5] (Top=5) - 모두 Pop() 수행 ➔ Top부터 차례대로 '5', '4', '2', '1' 출력! - 최종 출력 순서: 3 ➔ 5 ➔ 4 ➔ 2 ➔ 1 2) 후위 표기식 5 3 + 2 * 계산: - 피연산자 5, 3을 스택에 Push: [5, 3] - 연산자 +를 만나면 두 개를 Pop하여 더한 뒤(5 + 3 = 8) 다시 Push: [8] - 피연산자 2를 Push: [8, 2] - 연산자 *를 만나면 두 개를 Pop하여 곱한 뒤(8 × 2 = 16) Push: [16] ➔ 최종 정답: 16

확인: 스택(Stack)은 LIFO(후입선출) 구조로 함수 콜 스택, 괄호 검사, 후위 표기식 계산, DFS, Undo 기능에 사용된다.

3. 덱(Deque), 우선순위 큐(Priority Queue), 스택 2개로 큐 만들기

- 덱 (Deque, Double-Ended Queue): - 앞(Front)과 뒤(Rear) 양쪽 끝 모두에서 $O(1)$ 시간에 삽입과 삭제가 가능한 만능 자료구조로, 스택과 큐의 역할을 동시에 수행합니다 (슬라이딩 윈도우 알고리즘에 필수). - 우선순위 큐 (Priority Queue): - 들어온 순서와 상관없이 우선순위가 가장 높은(최댓값 또는 최솟값) 데이터가 가장 먼저 나오는 자료구조입니다. 배열이나 연결 리스트가 아닌 완전 이진 트리 기반의 힙(Heap)으로 구현하여 삽입과 삭제 모두 $O(\log N)$ 에 처리합니다. - 기술 면접 단골 문제: 스택 2개로 큐(FIFO) 구현하기: - 입력용 스택(inStack)과 출력용 스택(outStack) 2개를 둡니다. - Enqueue 시에는 inStack에 Push하고, Dequeue 시에는 outStack이 비어 있을 때만 inStack의 모든 원소를 Pop하여 outStack으로 옮긴 뒤 outStack.pop()을 수행하면 두 번 뒤집혀 원래 순서(FIFO)가 되며, 분할 상환 $O(1)$ 속도를 달성합니다.괄호 유효성 검사 알고리즘 핵심: 여는 괄호 (, {, [를 만나면 스택에 Push하고, 닫는 괄호 ), }, ]를 만나면 스택에서 Pop한 괄호와 짝이 맞는지 확인합니다. 문자열 끝까지 읽었을 때 스택이 완전히 비어 있어야 유효한 수식입니다!

참고 근거와 확인 범위

Harvard CS50 · Lecture 5: Data structures ↗
스택과 큐의 LIFO·FIFO 동작

설명·예제·문제 구성 및 오류 수정 책임: 프리런. 위 자료는 표시한 주제를 확인하거나 더 읽기 위한 근거이며, 외부 기관의 공식 수업이나 감수본을 뜻하지 않습니다.

참고 자료 연결 점검: 2026-11-02. 제작 방식·검수 범위와 수정 기록에서 확인 범위를 볼 수 있습니다. 오류는 상단의 의견 보내기 또는 contact@freelearn.io로 알려 주세요.

이 단원의 개념서 읽기 →