Stacks, Queues & Deques

1. Overview

스택, 큐와 데크(Stacks, Queues & Deques)는 데이터가 들어오고 나가는 방향성(Ordering)이라는 단순한 계약 하나가, 함수 호출 스택(Call Stack), 운영체제의 I/O 요청 큐, 이진 탐색트리(BFS), 코드 파서(Parser), 작업 스케줄러 등 무한한 현실 시스템을 지탱하는 핵심 추상자료형(ADT)임을 깨닫는 역학 공학입니다.

학습자는 LIFO(Last In, First Out) 계약으로 함수가 서로를 재귀 호출할 때의 반환 주소와 지역 변수를 층층이 쌓고 되돌아오는 콜 스택(Call Stack)의 물리적 실체를 뜯어봅니다. 나아가 FIFO(First In, First Out) 계약으로 네트워크 패킷이 도착 순서대로 CPU를 기다리는 I/O 큐를 거쳐, 두 방향 모두 O(1)로 삽입/삭제가 가능한 **데크(Deque, Double-ended Queue)**의 슬라이딩 윈도우 극한 활용까지 장악하여 알고리즘 설계의 핵심 무기를 확보합니다.

2. Scope & Boundaries

In-Scope

• 스택 구현과 활용 (Stack): 배열/연결 리스트 기반, 함수 콜 스택(Call Stack), 괄호 매칭(Balanced Parentheses), 역순 폴란드 표기법(RPN), DFS(깊이 우선 탐색) 명시적 스택.
• 큐 구현과 활용 (Queue): 원형 배열 큐(Circular Buffer), BFS(너비 우선 탐색), 생산자-소비자(Producer-Consumer) 패턴, 우선순위 큐(Min/Max Heap, 별도 심화).
• 데크와 슬라이딩 윈도우 (Deque): 양방향 O(1) 삽입/삭제, Python collections.deque, 슬라이딩 윈도우 최댓값(Monotonic Deque).
• 모노토닉 스택 (Monotonic Stack): 오큰수(Next Greater Element), 히스토그램 최대 넓이, 단조 감소/증가 스택 패턴.

Out-of-Scope

• 힙 기반 우선순위 큐(Priority Queue) 내부: 배열 기반 완전 이진 트리(Binary Heap)의 Heapify 연산 $\rightarrow$ 04-02-02. Heaps & Priority Queues 영역.
• 락-프리(Lock-Free) 큐: 멀티스레드 환경의 CAS(Compare-And-Swap) 원자적 큐 구현 $\rightarrow$ 05-01-04. Lock-Free Data Structures 영역.

Boundaries

• Stack vs. Recursion vs. Heap Memory: 함수의 재귀 호출이 쌓이는 곳이 '콜 스택'(스택 메모리 영역)이고, malloc()으로 동적 할당하는 곳이 '힙 메모리' 영역으로 서로 독립된 메모리 공간입니다. 알고리즘으로서의 스택 자료구조(ADT)는 이 중 어느 메모리 영역에든 구현될 수 있으며, 혼동하지 않아야 합니다.

3. Counterexample

• 배열 큐의 False Full 현상 (Linear Queue Drift): 배열 크기 5짜리 큐에 5번 Enqueue 후 3번 Dequeue를 하면, Front 포인터가 3번째 칸으로 이동합니다. 다시 2번 Enqueue를 하면 배열의 논리적 뒤쪽(Index 4)은 꽉 찼지만, 비워진 앞 3칸(Index 0, 1, 2)을 쓸 수 없어 Queue Full! 에러가 납니다. 배열의 뒤쪽이 막혀도 앞쪽에 빈 공간이 있으면 재사용하는 **원형 배열 큐(Circular Buffer)**를 쓰지 않으면 배열 큐는 선형적으로 공간을 낭비하며 뒤에서 막혀 멈춥니다.
• 재귀 스택 오버플로우 (Recursive Call Stack Overflow): "피보나치 수열을 재귀(Recursive)로 풀면 쉽잖아"라며 fib(n) = fib(n-1) + fib(n-2) 코드를 n=100,000으로 돌리는 순진한 실수. 각 재귀 호출마다 함수 프레임(Local Variables, Return Address)이 스택 메모리에 쌓입니다. 스택 메모리는 기본 8MB(Linux)로 엄격히 제한되어 있어, fib(100000)이 순식간에 10만 개의 스택 프레임을 쌓으며 메모리 한계를 돌파하여 OS가 SIGSEGV 신호로 프로세스를 사살하는 스택 오버플로우(Stack Overflow) 재앙이 터집니다.

4. Prerequisites

• 배열과 연결 리스트 (Basic): 스택과 큐의 내부 구현체로 배열(고정 크기)이나 연결 리스트(동적 크기)를 선택하는 트레이드오프를 이해해야 합니다. (04-01-01, 04-01-02)
• 함수 호출 규약 (Recommended): 함수가 호출될 때 반환 주소와 로컬 변수가 스택 프레임으로 어떻게 쌓이는지 알아야 콜 스택의 실체를 이해할 수 있습니다. (03-01-02 System Call Interface)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: LIFO의 법칙과 함수의 기억, 스택 (Stack & Call Stack)

• Why to Learn: 스택은 함수 호출의 숨은 뼈대(Call Stack)이자, 브라우저 뒤로 가기(Back), 텍스트 편집기 Undo, 프로그래밍 언어 파서(Parser)의 공통 심장을 장악하기 위함입니다.
• What to Learn:
  • Concepts: LIFO(Last In First Out), Push(삽입), Pop(삭제/반환), Peek(조회), 스택 프레임(Stack Frame), 오버플로우(Overflow).
  • Skills: 배열 기반 스택 구현, 괄호 유효성 검사(Valid Parentheses), 역순 폴란드 표기법(RPN) 계산.
  • Tools: GDB backtrace 콜 스택 추적.
  • Trade-offs: 배열 기반 스택은 캐시 히트율이 완벽하고 메모리 오버헤드가 없지만 크기를 사전에 선언해야 하며(고정 크기), 연결 리스트 기반 스택은 무한정 동적으로 팽창 가능하지만 노드마다 포인터 오버헤드가 붙고 캐시 지역성이 파괴되는 트레이드오프.
• How to Learn:
  • 1단계: main() → foo() → bar() 순으로 함수가 호출될 때, 각 함수의 반환 주소(Return Address)와 지역 변수들이 스택 프레임으로 쌓입니다. bar()가 리턴하면 스택 프레임이 POP되어 foo() 실행 지점으로 돌아가는 LIFO 물리 기하학을 해부합니다.
  • 2단계: ({[]}) 같은 괄호 문자열 유효성 검사 알고리즘. (, {, [를 스택에 Push, ), }, ]가 나오면 Pop한 원소와 짝이 맞는지 확인하여 최종 스택이 비어있으면 유효(Valid)한 괄호 매칭 로직을 뜯어봅니다.
• Implement: 파이썬 Stack 클래스 + valid_parentheses(s) 함수. push(), pop(), peek(), is_empty() 구현 후, "({[]})" → True, "({[}])" → False 검증. 추가로 역순 폴란드(RPN) 계산기: ["3","4","*","2","+"] → 14 계산 증명.

Recommended

Core Topic 02: FIFO의 공정성과 원형 버퍼, 큐 (Queue & Circular Buffer)

• Why to Learn: BFS(너비 우선 탐색)의 층위별 탐색, OS 프로세스 레디 큐(Ready Queue), 메시지 시스템의 생산자-소비자 패턴. FIFO 공정성이 이 모든 시스템의 핵심 설계임을 꿰기 위해서입니다.
• What to Learn:
  • Concepts: FIFO(First In First Out), Enqueue(Head 삽입)/Dequeue(Tail 제거), Front/Rear 포인터, 원형 배열 큐(Circular Array Queue).
  • Skills: BFS 너비 우선 탐색 구현, 생산자-소비자 큐 동기화.
  • Tools: 파이썬 collections.deque(큐로 활용), queue.Queue.
  • Trade-offs: 원형 배열 큐는 캐시 히트율이 좋고 오버헤드가 없지만 최대 크기가 고정되어 있어 넘치면 Enqueue를 거부합니다(Bounded Queue). 동적 연결 리스트 큐는 무한 팽창 가능하지만 노드 생성/소멸의 힙 메모리 할당 비용과 캐시 파괴가 단점입니다.
• How to Learn:
  • 1단계: 배열 크기 5인 큐에서 Front/Rear 포인터 인덱스를 (idx+1) % 5 나머지 연산으로 관리하면, Rear가 배열 끝(4)에 도달해도 다음 Enqueue 시 자동으로 처음(0)으로 돌아가 꽉 차지 않은 빈 공간을 재활용하는 원형 큐 물리를 해부합니다.
  • 2단계: BFS에서 Queue를 쓰는 이유. 시작 노드를 Enqueue, 루프에서 Dequeue 후 인접 미방문 노드를 모두 Enqueue하면, 레벨(층)별로 자연스럽게 탐색이 이뤄지는 BFS 큐 연동 역학을 뜯어봅니다.
• Implement: 파이썬 CircularQueue(capacity) 클래스. enqueue(v), dequeue(), is_full(), is_empty() 를 나머지(%) 연산으로 구현. BFS 미로 탐색: 0(빈 칸), 1(벽) 5×5 그리드에서 시작점에서 목적지까지 최단 거리(층수)를 Queue로 레벨 탐색하는 증명 코드.

Practical

Core Topic 03: 양방향 O(1)과 슬라이딩 윈도우, 데크 (Deque & Sliding Window Max)

• Why to Learn: 양쪽 끝에서 모두 O(1) 삽입/삭제가 가능한 데크는 LRU 캐시, 슬라이딩 윈도우 알고리즘, 실시간 시계열 스트림 분석 등 현대 고성능 서비스의 핵심 파이프라인 도구임을 꿰기 위함입니다.
• What to Learn:
  • Concepts: 데크(Deque, Double-ended Queue), appendleft/append, popleft/pop O(1).
  • Skills: 슬라이딩 윈도우 최댓값(Sliding Window Maximum, Monotonic Deque), 고정 크기 윈도우 연산.
  • Tools: 파이썬 collections.deque, Java ArrayDeque.
  • Trade-offs: 파이썬 list에서 list.insert(0, x)(Head 삽입)는 O(n)(뒤로 다 밀기)인 반면, collections.deque의 appendleft(x)는 내부적으로 이중 연결 리스트를 써서 O(1)입니다. 대신 deque는 dq[k] 인덱싱이 O(k)(포인터 따라가기)라 임의 접근이 필요한 알고리즘엔 부적합한 타협.
• How to Learn:
  • 1단계: 배열 [1,3,-1,-3,5,3,6,7], 윈도우 크기 k=3에서 슬라이딩 윈도우 최댓값 [3,3,5,5,6,7]을 구하는 문제. Naive한 O(nk) 방법 대신 Monotonic Deque로 O(n)에 푸는 역학을 해부합니다.
  • 2단계: 데크 안을 '내림차순'(Monotonic Decreasing)으로 유지. 새 원소가 들어올 때 데크 뒤에서 자기보다 작거나 같은 원소를 모두 빼버리고(Pop Right) 삽입. 윈도우를 벗어난 원소는 데크 앞(Left)에서 Pop. 항상 데크의 맨 앞이 현재 윈도우의 최댓값임을 증명합니다.
• Implement: 파이썬 collections.deque로 sliding_window_max(arr, k) 구현. 각 단계에서 데크 상태를 프린트하며 불필요 원소 추방과 윈도우 이탈 원소 제거 과정을 시각적으로 출력. 결과 최댓값 리스트와 O(n) 루프임을 시간 측정으로 증명.

Advanced

Core Topic 04: 단조로운 규칙과 폭발적 응용, 단조 스택 (Monotonic Stack)

• Why to Learn: "각 원소에서 오른쪽으로 봤을 때 처음으로 나오는 더 큰 수(Next Greater Element)"를 O(n²) Naive 대신 O(n)으로 찾는 단조 스택은, 히스토그램 최대 넓이, 건물 스카이라인, 주식 스팬 계산 등 실무 알고리즘에서 빠지지 않는 핵심 패턴임을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 단조 증가 스택(Monotonic Increasing Stack), 단조 감소 스택(Monotonic Decreasing Stack), Next Greater/Smaller Element 패턴.
  • Skills: 히스토그램 최대 직사각형 넓이(Largest Rectangle in Histogram, LeetCode #84), 일일 온도(Daily Temperatures) 문제.
  • Tools: LeetCode #496, #739, #84 문제.
  • Trade-offs: 단조 스택은 "스택에 들어온 원소가 절대 역순이 되지 않도록" 위배 원소를 즉각 Pop하는 단순 규칙을 통해 O(n) 시간을 보장하지만, 스택 상태가 직관적이지 않아 처음 접하는 사람에게는 "왜 Pop하는 순간이 답인가?"를 이해하기 어려운 습득 난이도 장벽이 있습니다.
• How to Learn:
  • 1단계: Next Greater Element: 배열 [2, 1, 2, 4, 3] 각 원소의 오른쪽 첫 번째 큰 수를 구하는 O(n) 알고리즘. 단조 감소 스택을 유지하며, 새 원소가 스택 Top보다 크면 Top을 Pop하고 그 Pop된 원소의 Next Greater는 현재 원소라고 기록하는 역학을 해부합니다.
  • 2단계: 히스토그램: 단조 증가 스택으로, Pop 시 현재 원소가 오른쪽 경계, 스택 새 Top이 왼쪽 경계가 되어 최대 직사각형 넓이를 O(n)에 계산하는 아름다운 응용을 뜯어봅니다.
• Implement: next_greater_element(arr) 파이썬 구현. [2,1,2,4,3] → [4,2,4,-1,-1] 검증 (없으면 -1). 추가로 일일 온도 daily_temperatures([73,74,75,71,69,72,76,73]) → [1,1,4,2,1,1,0,0] (며칠 뒤 더 따뜻해지는 날)을 단조 스택으로 구현하여 O(n) 시간 증명.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Data Structure Fundamentals — Stacks and Queues context.
• [P1] CS2023 - SDF/Fundamental Data Structures (Linear Structures) — Core requirements.

Secondary

• [Data Structures and Algorithm Analysis in C++] Mark Allen Weiss — Formal SQD focus.
• [Hacker's Delight] Henry S. Warren — Low-level stack/bitwise tricks.

Industry

• [CPP Reference: std::stack, std::queue, std::deque] — Standard library specs.
• [Linux Kernel: kfifo implementation] — Real-world high-performance queue.

9. Final Checklist

Primary

• 'LIFO'와 'FIFO'의 물리적 출입 통제 방식이 시스템의 '데이터 처리 순서'를 어떻게 결정짓는지 설명 가능한가? (P1)
• 스택을 사용하여 '문자열 뒤집기'나 '연산자 우선순위'를 수리적으로 처리하는 과정을 입증할 수 있는 가? (P1)

Secondary

• 원형 큐에서 Full 상태와 Empty 상태를 구분하기 위해 '한 칸을 비워두는' 물리적 이유를 수리적으로 소통 가능한가?
• 덱(Deque)이 왜 스택과 큐를 모두 포함하는 '일반화된 선형 자료구조'인지 그 논리적 포함 관계를 도출할 수 있는 가?

Industry

• 네트워크 라우터 설계 시, 큐의 크기가 너무 작을 때 발생하는 'Tail Drop' 현상의 물리적 파급력을 기술할 수 있는 가? (SFIA)
• 함수의 깊은 재귀가 시스템의 물리적 'Call Stack' 용량을 초과할 때, 이를 '사용자 정의 스택(Heap 기반)'으로 전환하여 해결하는 방안을 제안할 수 있는 가?