배열에서 조금 더 발전한 형태의 자료구조
Stack (스택)
개념
- LIFO(Last In First Out): 후입선출
- 나중에 들어온 데이터가 먼저 나가는 구조
주요 연산
- push: 데이터를 스택의 맨 위에 삽입
- pop: 스택의 맨 위 데이터를 제거하고 반환
- top: 스택의 맨 위 데이터를 확인 (제거하지 않음)
동작 과정
- 빈 스택 → push(새 값) → 스택에 값 추가
- 데이터 있는 스택 → pop() → 맨 위 값 제거
- top 포인터가 항상 스택의 최상단을 가리킴
활용
- 깊이 우선 탐색(DFS: Depth First Search)
- 백트래킹 종류의 코딩 테스트에 효과적
- LIFO(후입선출) 개념 자체가 재귀 함수 알고리즘의 원리와 일맥상통
Queue (큐)
개념
- FIFO(First In First Out): 선입선출 자료구조
- 스택과 달리 양쪽 끝에서 삽입과 삭제가 이루어짐
큐의 구조
[새 값] → [값] [값] [값] [값] [지울 값] → [pop]
↑ ↑
back front
(rear) (head)주요 연산
- push: back 부분에 새로운 데이터를 삽입하는 연산
- pop: front에서 데이터를 제거하는 연산
- back: 큐에서 가장 끝 데이터를 가리키는 영역
- front: 큐에서 가장 앞의 데이터를 가리키는 영역
동작 원리
- 새 데이터 추가: back(rear) 위치에 push
- 데이터 제거: front(head) 위치에서 pop
- 먼저 들어온 데이터가 먼저 나감
큐 관련 용어
- back = rear: 큐의 뒤쪽 (삽입 위치)
- front = head: 큐의 앞쪽 (삭제 위치)
활용 예시
- 프린터 대기열
- BFS(너비 우선 탐색)
- 작업 스케줄링
- 버퍼링 시스템
핵심 차이점
| 구조 | 삽입/삭제 위치 | 데이터 순서 | 예시 |
|---|---|---|---|
| 스택 | 한쪽 끝(top) | 후입선출 | 접시 쌓기 |
| 큐 | 양쪽 끝 | 선입선출 | 대기줄 |
우선순위 큐 (Priority Queue)
- 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조
- 일반적으로 힙(heap)을 이용해 구현
알고리즘과의 연관성
- 스택 → DFS (깊이 우선 탐색)
- 큐 → BFS (너비 우선 탐색)