1. 스택(Stack)
후입선출 (LIFO: Last-In-First-Out) 자료구조이다. 마치 바구니에 책을 겹겹이 쌓아올리는 것처럼 한 방향에서만 데이터의 삽입/삭제가 일어난다.
특징
- 가장 최근에 추가한 데이터가 가장 먼저 나오는 후입선출 자료구조이다. 예를 들어 상단 그림에서는
A-B-C순으로 데이터가 삽입되었으며, 삭제 시에는C-B-A순이 될 것이다. - 스택에서의 데이터 삽입/삭제는 push(), pop() 이라 부르는데, 이 연산은 모두
O(1)의 시간 복잡도를 갖는다.
활용 예시
- 깊이 우선탐색
- 웹 브라우저 방문기록 (뒤로 가기): 뒤로 가기 시 가장 최근에 실행한 앱으로 되돌아 가는 것
- 괄호 유효성 검사
- call stack
- 후위 표기법 연산
2. 큐(Queue)
선입선출 (FIFO: First-In-First-Out) 자료구조이다. 한쪽 방향에서는 데이터 삽입이, 다른 쪽에서는 데이터 삭제가 일어나 먼저 들어간 데이터가 먼저 나오게 되는 자료구조이다.
특징
- 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 선입선출 자료구조이다. 상단 사진에서는
A-B-C순으로 데이터가 삽입되었으며, 삭제 시에도A-B-C순으로 삭제될 것이다. - 큐에서의 데이터 삽입을 enqueue, 데이터 삭제를 dequeue 라고 하는데, 두 연산 모두 O(1) 만큼의 시간이 소요된다.
구현 방식
- Array-Based-Queue: 크기가 고정되어있어 데이터 삽입/삭제 과정에서 메모리 낭비가 발생할 수 있다. 이 경우 아래에서 다시 언급할 원형 큐로 이 문제를 예방할 수 있다.
- List-Based-Queue: 크기가 가변적이기 때문에 재할당이나 메모리 낭비 걱정을 할 필요가 없어진다.
원형 큐
큐의 삭제 연산이 일어나는 곳을 front, 삽입 연산이 일어나는 곳을 rear라고 부르는데, 데이터를 계속하여 삭제하다보면 front값이 하나씩 밀려 저장공간은 있는데도 데이터를 삽입할 수 없는 상황이 발생할 수 있다. 이러한 단점을 보완하기 위해 나온 곳이 원형 큐이다.
양쪽이 뚫려있는 파이프와 같은 형태인 선형 큐와는 달리 원형 큐는 파이프의 출입구를 연결시켜놓은 듯한 모양이다. rear와 front 값은 rear = (rear+1) % max, front = (front+1) % max와 같은 식으로 조정을 해주기 때문에 삽입/삭제가 반복되어도 여유공간을 최대로 활용할 수 있다.
1. 큐가 가득 찬 상태
2. 삭제 연산 후
3. 삽입 연산 후
활용 예시
- 하나의 자원을 공유하는 프린터
- CPU Taking Schedule
- Cache
- BFS
Start fast to fail fast