Stack
LIFO ( Last In First Out )으로 가장 마지막에 추가된 데이터가 가장 먼저 나오게 되는 자료구조
Operation
- push : 스택의 맨 위에 데이터를 추가
- pop : 스택의 맨 위 데이터를 제거
- peek : 스택의 맨 위 요소를 반환 ( 제거하지 않고 )
- isempty : 스택이 비어있는지 검사
- ispull : 스택이 가득 찼는지 검사
시간복잡도
| Operation | Time |
|---|---|
| push | O(1) |
| pop | O(1) |
Application
- 괄호 유효성 검사
- 웹 브라우저 방문기록 (뒤로가기)
- call stack (DFS)
Queue
FIFO ( First In First Out )으로 가장 먼저 들어온 데이터가 가장 먼저 나가는 자료구조
Operation
- enqueue : 큐의 마지막에 데이터를 추가
- dequeue : 큐의 맨 앞 데이터를 제거
- front : 큐의 맨 앞 데이터를 반환 ( 제거하지 않고 )
- isempty : 큐가 비어있는지 검사
- ispull : 큐가 가득 찼는지 검사
시간복잡도
| Operation | Time |
|---|---|
| push | O(1) |
| pop | O(1) |
Application
- CPU 스케줄링
- 너비 우선 탐색 (BFS)
