큐와 스택 요약

Cheatsheet Content

### 워크리스트 (Worklists) - **정의**: 처리 대기 중인 항목들을 담는 컨테이너. - **기본 작업**: 항목 추가, 항목 검색(및 제거). - **핵심 아이디어**: 검색 순서는 고정되어 있지 않음 (LIFO, FIFO, 우선순위 등 데이터 구조에 따라 다름). - **구체적인 워크리스트**: - **스택 (Stacks)**: 가장 최근에 삽입된 요소를 검색 (LIFO - Last In, First Out). - **큐 (Queues)**: 가장 오래 전에 삽입된 요소를 검색 (FIFO - First In, First Out). - **우선순위 큐 (Priority Queues)**: 가장 높은 우선순위의 요소를 검색. - **워크리스트 인터페이스 (ADT)**: - `wl_new()`: 빈 워크리스트 생성. - `wl_add(W, x)`: 워크리스트 `W`에 요소 `x` 추가. - `wl_retrieve(W)`: 워크리스트 `W`에서 요소 검색 및 제거. - `wl_empty(W)`: 워크리스트 `W`가 비어있는지 확인. - **응용**: OS 스케줄링 (준비 큐), 그래프 알고리즘 (BFS/DFS), 데이터 흐름 분석. - 워크리스트 정책 선택이 알고리즘 동작 및 성능에 영향. ### 스택 (Stacks) - **정의**: LIFO (Last-In-First-Out) 정책을 따르는 워크리스트. 책 더미와 유사. - **주요 작업**: - `push(x)`: 스택의 맨 위에 `x`를 삽입. - `pop()`: 스택의 맨 위 요소를 제거하고 반환. - `top()`: 스택의 맨 위 요소를 반환 (제거하지 않음). - `empty()`: 스택이 비어있는지 확인. - `size()`: 스택의 요소 수 반환. - **배열 기반 스택 구현**: - 배열을 사용하여 요소를 저장하고, `t` 변수로 맨 위 요소의 인덱스를 추적. - `push`는 `S[++t] = e`, `pop`은 `return S[t--]`. - **성능**: `n`개 요소에 대해 $O(n)$ 공간, 모든 작업 $O(1)$ 시간. - **제한 사항**: 최대 스택 크기를 미리 정의해야 하며, 동적으로 변경 불가. `StackFull` 예외 발생 가능. - **C++ STL `std::stack`**: - `#include ` 사용. - `push(e)`, `pop()`, `top()`, `empty()`, `size()` 제공. - **응용: 괄호/기호 균형 맞추기**: - 여는 괄호는 `push`, 닫는 괄호는 `pop`하여 짝이 맞는지 확인. - 마지막에 스택이 비어있어야 유효. ### 재귀와 호출 스택 (Recursion and Call Stack) - **재귀**: 함수가 자신을 직접 또는 간접적으로 호출하여 문제를 해결하는 프로그래밍 기법. - **필수 조건**: 기본 케이스 (Base case), 작은 하위 문제 (Smaller subproblem). - **예시**: 팩토리얼 함수 `factorial(n) = n * factorial(n-1)`. - **함수 호출 스택 (Function Call Stacks)**: - 함수가 호출될 때마다 해당 함수의 **스택 프레임**이 호출 스택에 `push`됨. - 스택 프레임에는 지역 변수, 저장된 레지스터 값, 함수 인자, **반환 주소** (다음 명령어) 등이 포함. - 함수가 반환되면 해당 스택 프레임이 `pop`됨. - **재귀가 호출 스택에 미치는 영향**: - 재귀 호출마다 새로운 스택 프레임이 생성. - 스택이 깊어지면 **스택 오버플로우** 발생 가능. - **스택 사용량**: `O(n)` (재귀 깊이에 비례). - **재귀의 장단점**: - **장점**: - **간결성 및 우아함**: 트리, 분할 정복 문제에 자연스럽게 적용. - **코드 크기 감소**: 반복문 대비 코드량이 적음. - **추론 용이성**: 수학적 정의와 유사한 구조. - **데이터 구조에 적합**: 트리, 그래프 등. - **단점**: - **함수 호출 오버헤드**: 스택 프레임 생성 및 제거 비용. - **재계산 가능성**: (예: 순진한 피보나치) 하위 문제를 재계산할 수 있어 느려질 수 있음. - **디버깅 어려움**: 추적하기 복잡. ### 꼬리 호출 재귀 (Tail Call Recursion) - **정의**: 함수의 마지막 작업이 재귀 호출 자체인 재귀 형태. - **비꼬리 호출 예시**: `return n * factorial(n-1)` (재귀 호출 후 곱셈 연산이 남아있음). - **꼬리 호출 변환**: 누적 매개변수 `a`를 사용하여 `factorialHelper(n-1, n * a)`와 같이 재귀 호출만 남김. - **꼬리 호출 최적화 (Tail Call Optimization, TCO)**: - 꼬리 호출 함수에서, 컴파일러는 현재 스택 프레임을 재사용하여 새로운 스택 프레임 할당을 피할 수 있음. - **결과**: 재귀가 반복문처럼 `O(1)` 스택 공간을 사용하게 됨. - **주의**: 모든 컴파일러가 TCO를 보장하지는 않음. ### 상환 분석 (Amortized Analysis) - **목표**: 일련의 작업에 대한 평균 비용을 분석하여 최악의 경우를 완화. - **집합적 방법 (Aggregate Method)**: - `n`개의 작업 시퀀스에 대한 총 비용 $T(n)$을 계산. - 각 작업의 상환 비용은 $T(n)/n$. - **예시 (스택 `MULTIPOP`)**: `n`개의 PUSH, POP, MULTIPOP 작업 시퀀스에 대해 총 비용은 $O(n)$. 따라서 각 작업의 상환 비용은 $O(1)$. - **회계 방법 (Accounting Method)**: - 각 작업에 대해 "크레딧"을 할당/차감하여 미래 작업의 비용을 지불. - 스택 `PUSH`에 $2를 청구하여 $1는 실제 비용으로, $1는 스택에 있는 요소의 "미래 POP" 비용으로 적립. - `POP`과 `MULTIPOP`은 적립된 크레딧을 사용하여 비용을 지불 ($0 청구). - 결과적으로 모든 작업에 대해 은행 계좌(크레딧)가 음수가 되지 않음을 보장하며, 총 상환 비용이 실제 총 비용의 상한선이 됨. ### 큐 (Queues) - **정의**: FIFO (First-In-First-Out) 정책을 따르는 워크리스트. 대기열과 유사. - **주요 작업**: - `enqueue(x)`: 큐의 뒤쪽에 `x`를 삽입. - `dequeue()`: 큐의 앞쪽 요소를 제거하고 반환. - `front()`: 큐의 앞쪽 요소를 반환 (제거하지 않음). - `empty()`: 큐가 비어있는지 확인. - `size()`: 큐의 요소 수 반환. - **배열 기반 큐 구현 (순환 큐)**: - 고정 크기 배열을 순환 방식으로 사용. - `f` (앞쪽 인덱스), `r` (다음 삽입 위치 인덱스), `n` (요소 수) 변수로 상태 추적. - `enqueue` 시 `r = (r + 1) mod N`, `dequeue` 시 `f = (f + 1) mod N`. - **성능**: `n`개 요소에 대해 $O(n)$ 공간, 모든 작업 $O(1)$ 시간. - **제한 사항**: 배열이 가득 차면 `QueueFull` 예외 발생 가능. - **C++ STL `std::queue`**: - `#include ` 사용. - `push(e)` (enqueue), `pop()` (dequeue), `front()`, `back()`, `empty()`, `size()` 제공. - **응용**: - **직접 응용**: 대기 목록, 공유 리소스 접근 (프린터), 멀티프로그래밍. - **간접 응용**: 보조 데이터 구조, 다른 데이터 구조의 구성 요소. - **라운드 로빈 스케줄러**: CPU 스케줄링에서 FIFO 큐를 사용하여 프로세스에 고정된 시간 할당. ### 양방향 큐 (Double-Ended Queues, Deque) - **정의**: 양쪽 끝 (앞과 뒤)에서 삽입 및 삭제를 지원하는 큐. - **주요 작업**: - `push_front(e)`: 앞쪽에 `e` 삽입. - `push_back(e)`: 뒤쪽에 `e` 삽입. - `pop_front()`: 앞쪽 요소 제거 및 반환. - `pop_back()`: 뒤쪽 요소 제거 및 반환. - `front()`, `back()`, `empty()`, `size()` 등. - **구현**: - **이중 연결 리스트 (Doubly Linked List)**: 모든 작업 $O(1)$ 시간. - **C++ STL `std::deque`**: - `#include ` 사용. - `push_front(e)`, `push_back(e)`, `pop_front()`, `pop_back()`, `front()`, `back()`, `empty()`, `size()` 제공. - `std::vector`와 유사하게 랜덤 접근 (`operator[]`) 지원. - 일반적으로 블록 기반 구조로 구현되어 양쪽 끝에서의 빠른 삽입/삭제를 지원. - **순환 버퍼 (Circular Buffers)**: - 배열을 순환 방식으로 사용하여 `front`와 `back` 인덱스를 관리. - 논리적 인덱스는 `(front + i) % MAX`로 매핑. ### ADT, OOP, STL - **추상 데이터 타입 (ADT)**: - **정의**: 데이터에 대한 일련의 연산과 그 동작을 명세하는 개념적 모델. - **명세**: 사용 가능한 연산, 보장된 동작, 유지되어야 할 불변 속성. - **미명세**: 구현 방식 (배열 vs. 연결 리스트), 메모리 배치, 성장 전략. - ADT는 개념적인 명세. - **객체 지향 프로그래밍 (OOP) (클래스)**: - **정의**: ADT를 구체화하는 메커니즘. - **캡슐화**: 데이터 숨김 (private 멤버), 공개 인터페이스 (메서드). - **불변 속성 강제**: 생성자/소멸자를 통해 내부 불변 속성 유지. - OOP는 ADT를 구체적인 구현으로 만듦. - **STL (Standard Template Library)**: - **정의**: ADT의 산업적 설계. 재사용 가능하고 일반적인 구현 제공. - **특징**: 템플릿 기반, 일반적, 캡슐화, 최적화, 표준화. - **각 컨테이너**: ADT를 구현, OOP 및 템플릿 사용, 성능 및 재사용성 고려. - **설계 철학**: 구현과 인터페이스 분리, 템플릿을 통한 타입 추상화, 컴파일 타임 다형성 선호, 불필요한 상속 회피, 예측 가능한 성능. - **예시 (`std::stack`)**: `std::deque`를 기본 컨테이너로 사용하며, `std::vector`나 `std::list` 등으로 변경 가능. 이는 ADT 추상화, OOP 캡슐화, 일반 프로그래밍을 반영. - **결론**: ADT는 이론적 모델, OOP는 이를 구현하는 방식, STL은 이를 일반적이고 효율적으로 재사용 가능하게 만든 라이브러리.