Stacks, Queues & Deques

1. Overview

스택, 큐 및 덱(Stacks, Queues & Deques, SQD)은 컴퓨터 시스템이 명령과 데이터를 처리하는 '순서'의 물리학을 정의하는 핵심적인 규율(Discipline) 기반 자료구조입니다.

컴퓨터는 모든 일을 한꺼번에 할 수 없습니다. 학습자는 나중에 들어온 놈이 먼저 나가는 **스택(Stack)**의 원리를 통해 함수 호출과 복귀라는 시스템의 '기억법'을 배웁니다. 또한, 먼저 온 줄이 먼저 빠지는 **큐(Queue)**의 수리적 모델을 통해 시스템의 대기열과 버퍼링(Buffering) 개념을 익힙니다. 특히 양쪽 끝에서 출입이 자유로운 **덱(Deque)**의 유연한 물리 배치를 분석합니다. 이를 통해 '무엇을 먼저 할 것인가'라는 전략적 선택을 하드웨어 자원 위에 설계하는 기본기를 확보합니다.

2. Scope & Boundaries

In-Scope

• Stack Mechanics: LIFO 물리, Push/Pop 연산, 시스템 실행 스택(Call stack)의 하드웨어 연동
• Queue Structures: FIFO 물리, Enqueue/Dequeue, 원형 큐(Circular Queue)의 물리적 오버플로우 방지
• Deque Variants: Double-ended Queue의 물리 배치 및 스택/큐의 일반화된 수리 모델
• Abstract Data Types (ADT): 구현(배열 vs 연결리스트)과 무관한 논리적 인터페이스 정의

Out-of-Scope

• 우선순위 큐(Priority Queue)의 힙 트리 상세 (04-02-02 노드에서 분담)
• 운영체제 스케줄러의 실제 작업 큐 복합 알고리즘 (03-02-03 노드에서 위임)

Boundaries

• SQD vs. Dynamic Lists: 일반 리스트가 '아무 곳이나 찌르는' 자유를 가졌다면, SQD는 '정해진 문(Gate)'으로만 출입해야 하는 물리적 제약성에 집중하여 구분합니다.

3. Counterexample

• 단순히 "창고에 쌓는 것"이라는 비유는 SQD 학습이 아닙니다. 왜 스택이 함수 호출 구조에서 **재귀(Recursion)**의 물리적 한계를 결정짓는지 '스택 프레임' 점유 관점에서 증명할 수 있어야 하며, 일차원 배열로 구현된 큐에서 데이터를 뺄 때마다 나머지 데이터를 '물리적으로 한 칸씩 미는' 행위가 왜 최악의 설계($O(n)$)인지 수리적으로 분석하지 못한다면 SQD의 정수를 놓친 것입니다.

4. Prerequisites

• Arrays, Strings & Memory Layout (Basic): 연속 메모리 접근 기초가 필수입니다. (04-01-01 ASL)
• Linked Lists & Pointer Logic (Recommended): 주소 연결 기반의 동적 확장 이해가 권장됩니다. (04-01-02 LPL)

5. Learning Map

1. The Last-In Rule: 들어온 길을 되돌아 나가는 스택의 '역전(Reverse)' 물리를 배웁니다.
2. The First-Come Fairness: 질서 있게 줄을 서는 큐의 '유량(Flow)' 통제법을 익힙니다.
3. The Endless Loop: 배열의 끝이 다시 시작으로 이어지는 원형 큐의 기하학적 배치를 분석합니다.
4. The Flexible Gate: 양방향 출입을 허용하는 덱을 통해 범용적인 대기열 구조를 완성합니다.

6. Learning Topics

Basic

Core: 스택의 물리적 실행과 LIFO (The Stack)

• Why to Learn: 당신이 짠 모든 함수가 CPU 안에서 길을 잃지 않고 복귀하게 만드는 유일한 증거이기 때문입니다.
• What to Learn:
  • TOP Pointer: 데이터가 쌓이는 물리적 최상단 주소의 이동
  • Underflow & Overflow: 빈 통을 비우거나 가득 찬 통에 억지로 넣을 때의 하드웨어적 경고
  • Expression Evaluation: 후위 표기법(RPN)을 통한 산술 연산의 물리적 순서 결정
• How to Learn:
  • 함수가 호출될 때마다 스택 포인터(ESP) 값이 물리적으로 내려가는지/올라가는지 디버거로 확인 실습
  • 괄호 짝 맞추기 알고리즘을 통해 스택이 '쌍'을 이루는 논리를 어떻게 물리적으로 포착하는지 분석
• Implement: 배열을 기반으로 Push와 Pop 시 고정 시간($O(1)$)을 보장하는 기초 스택

Recommended

Core: 큐와 대기열의 물리 전개 (The Queue)

• Why to Learn: 네트워크 패킷이나 디스크 요청처럼 순서가 중요한 하드웨어 이벤트의 임시 보관소이기 때문입니다.
• What to Learn:
  • Front & Rear: 줄의 시작과 끝을 가리키는 물리적 인덱스 관리
  • Linear vs Circular: 배열 공간을 버리지 않고 재사용하기 위한 나머지($\%$) 연산 논리
  • Buffer Management: 데이터 생산과 소비의 속도 차이를 물리적으로 완충하는 법
• How to Learn:
  • 선형 큐에서 발생한 '가짜 오버플로우' 현상을 직접 재현하고, 원형 큐가 이를 어떻게 하드웨어적으로 해결하는지 연구 실습
  • 큐의 크기를 바꿔가며 데이터 손실(Drop)률과 지연 시간의 수리적 상관관계 도출
• Implement: 나머지 연산을 활용하여 공간을 낭비하지 않는 고성능 원형 큐

Practical

Core: 덱과 일반화된 순서 관리 (The Deque)

• Why to Learn: 스택과 큐의 장점을 합쳐 상황에 따라 카멜레온처럼 변하는 하이브리드 제어기가 필요하기 때문입니다.
• What to Learn:
  • Head/Tail Insertion: 시스템의 앞과 뒤 모두에서 작업을 우선 처리할 수 있는 권장 물리
  • Generalization: 덱 하나로 스택과 큐를 수리적으로 흉내 내는 방식(Constraint mapping)
  • Work-Stealing: 멀티코어 환경에서 남의 일을 뒤에서 몰래 훔쳐가 효율을 높이는 덱 기반 물리 기법
• How to Learn:
  • 양방향 연결 리스트를 이용해 덱을 구현했을 때의 포인터 연결 물리 전개도 작성 실습
  • 브라우저의 '앞으로 가기/뒤로 가기' 기능을 덱이나 두 개의 스택으로 물리 모델링 분석
• Implement: 덱의 인터페이스를 활용하여 스택과 큐의 동작을 선택적으로 수행하는 클래스

Advanced

Core: 시스템 스택과 보안 물리 (Call Stack & Security)

• Why to Learn: 프로그램의 생사 결정권이 담긴 스택의 취약점이 해커의 물리적 침투 통로가 되기 때문입니다.
• What to Learn:
  • Stack Frame Structure: 매개변수, 복귀 주소, 지역 변수의 물리적 레이아웃
  • Smash the Stack: 복귀 주소를 변조하여 CPU의 눈을 속이는 물리적 탈취 시나리오
  • Stack Canary: 스택 오염을 감지하기 위해 심어놓은 하드웨어적 '탄광의 카나리아' 비트
• How to Learn:
  • 고의로 배열 범위를 넘겨 함수가 원래 가야 할 주소가 아닌 엉뚱한 곳으로 점프하게 만드는 물리 재현 실습
  • 재귀 함수의 깊이를 100만 번으로 설정하여 하드웨어가 내뱉는 'Stack Overflow'의 물리적 임계점 측정
• Implement: 함수의 매개변수 정보를 스택 상에서 직접 찾아내 출력하는 저수준 분석 루틴

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 기반)'으로 전환하여 해결하는 방안을 제안할 수 있는 가?