개념 정리
스택(Stack)과 큐(Queue)
단원 개요
후입선출(LIFO) 구조의 스택과 선입선출(FIFO) 구조의 큐, 원형 큐와 덱(Deque), 우선순위 큐까지 핵심 추상 자료형(ADT)의 원리와 응용을 학습합니다.선수 개념
필수 키워드:동작 원리TopPushPop주요 연산 (모두 )Stack OverflowStack Underflow시스템 및 알고리즘 핵심 활용처함수 호출 콜 스택 (Call Stack)수식의 괄호 짝 검사
1
스택 (Stack) - LIFO (후입선출) 구조와 응용
•
동작 원리: 프링글스 감자칩 통이나 접시 쌓기처럼 한쪽 끝(Top)에서만 데이터의 삽입(Push)과 삭제(Pop)가 일어나는 LIFO (Last-In, First-Out: 가장 나중에 들어간 데이터가 가장 먼저 나옴) 자료구조입니다.
•
주요 연산 (모두 ):
•
push(x): Top 위치에 원소 를 추가합니다. (가득 찬 스택에 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)를 사용하며, 나머지 연산자(
%)를 이용해 인덱스를 회전시킵니다:•
핵심 활용처: 운영체제 프로세스 Ready Queue, 프린터 스풀러 대기열, 네트워크 패킷 버퍼, 너비 우선 탐색(BFS), 웹 서버 요청 메시지 큐(Kafka, RabbitMQ).
풀이
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] ➔ 최종 정답: 163
덱(Deque), 우선순위 큐(Priority Queue), 스택 2개로 큐 만들기
•
덱 (Deque, Double-Ended Queue):
•
앞(Front)과 뒤(Rear) 양쪽 끝 모두에서 시간에 삽입과 삭제가 가능한 만능 자료구조로, 스택과 큐의 역할을 동시에 수행합니다 (슬라이딩 윈도우 알고리즘에 필수).
•
우선순위 큐 (Priority Queue):
•
들어온 순서와 상관없이 우선순위가 가장 높은(최댓값 또는 최솟값) 데이터가 가장 먼저 나오는 자료구조입니다. 배열이나 연결 리스트가 아닌 완전 이진 트리 기반의 힙(Heap)으로 구현하여 삽입과 삭제 모두 에 처리합니다.
•
기술 면접 단골 문제: 스택 2개로 큐(FIFO) 구현하기:
•
입력용 스택(
inStack)과 출력용 스택(outStack) 2개를 둡니다.•
Enqueue 시에는
inStack에 Push하고, Dequeue 시에는 outStack이 비어 있을 때만 inStack의 모든 원소를 Pop하여 outStack으로 옮긴 뒤 outStack.pop()을 수행하면 두 번 뒤집혀 원래 순서(FIFO)가 되며, 분할 상환 속도를 달성합니다.학습 도움말
괄호 유효성 검사 알고리즘 핵심: 여는 괄호 (, {, [를 만나면 스택에 Push하고, 닫는 괄호 ), }, ]를 만나면 스택에서 Pop한 괄호와 짝이 맞는지 확인합니다. 문자열 끝까지 읽었을 때 스택이 완전히 비어 있어야 유효한 수식입니다!핵심 요약
- ✓스택(Stack)은 LIFO(후입선출) 구조로 함수 콜 스택, 괄호 검사, 후위 표기식 계산, DFS, Undo 기능에 사용된다.
- ✓큐(Queue)는 FIFO(선입선출) 구조로 작업 스케줄링 대기열, 스트리밍 버퍼, BFS 최단 경로 탐색에 사용된다.
- ✓원형 큐(Circular Queue)는 모듈로(% N) 연산으로 배열의 처음과 끝을 이어 붙여 메모리 공간 낭비를 해결한다.
- ✓양방향 입출력이 가능한 덱(Deque)은 O(1)에 동작하며, 힙 기반의 우선순위 큐는 O(log N)에 최댓값/최솟값을 꺼낸다.