스택(Stack)과 큐(Queue)는 선형 자료구조(Linear Data Structure)의 대표적인 형태로, 알고리즘 문제 해결, 시스템 아키텍처 설계, 소프트웨어 개발 등 다양한 영역에서 활용된다.
스택(Stack)
스택은 후입선출(Last-In, First-Out, LIFO)의 특성을 가진 자료구조이다. 즉, 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다. 스택은 마치 책을 위로 쌓아올리고 위에서부터 꺼내는 것과 유사하다.
주요 연산
| 연산 | 설명 |
|---|---|
push(item) | 스택의 **맨 위(top)**에 요소를 삽입한다. |
pop() | 스택의 맨 위 요소를 제거하고 반환한다. |
peek() | 제거하지 않고 맨 위 요소를 반환한다. (읽기 전용) |
isEmpty() | 스택이 비어 있는지 여부를 반환한다. |
size() | 스택 내 요소의 개수를 반환한다. |
내부 구현
스택은 배열(Array) 또는 연결 리스트(Linked List)로 구현할 수 있다.
배열 기반 스택
-
고정 크기 할당
-
O(1) 시간의 push, pop 가능
-
크기 초과 시 오버플로우 발생 가능
연결 리스트 기반 스택
-
크기 제한 없음
-
노드 기반 동적 메모리 할당
-
push, pop 시 O(1) 성능 유지
시간 복잡도
| 연산 | 시간 복잡도 |
|---|---|
push | O(1) |
pop | O(1) |
peek | O(1) |
활용 사례
-
재귀 함수 호출 시 콜 스택 관리
-
웹 브라우저 뒤로가기 기능
-
수식 계산기 (후위 표기법, 전위 표기법 등)
-
괄호 검사 (유효한 괄호 쌍 판별)
큐(Queue)
큐는 선입선출(First In, First Out; FIFO) 방식으로 동작하는 선형 자료구조이다. 먼저 삽입된 요소가 먼저 제거되는 구조로, 현실의 대기열(줄 서기)을 모방한 구조이다.
주요 연산
| 연산 | 설명 |
|---|---|
enqueue(item) | 큐의 **뒤쪽(rear)**에 요소를 삽입한다. |
dequeue() | 큐의 앞쪽(front) 요소를 제거하고 반환한다. |
peek() | 제거하지 않고 맨 앞 요소를 반환한다. |
isEmpty() | 큐가 비어 있는지 여부를 반환한다. |
size() | 큐 내 요소의 개수를 반환한다. |
종류
| 큐 종류 | 설명 |
|---|---|
| 일반 큐 | 선입선출 구조의 가장 기본형 |
| 원형 큐 (Circular Queue) | 배열을 원형 구조로 활용하여 공간 낭비를 최소화 |
| 이중 큐 (Deque) | 양쪽에서 삽입과 삭제가 가능한 큐 |
| 우선순위 큐 | 요소마다 우선순위를 부여하여 높은 우선순위의 요소를 먼저 처리 |
내부 구현
큐 또한 배열 또는 연결 리스트로 구현할 수 있다. Circular Queue는 배열로 구현 시 인덱스를 순환시켜 공간을 절약하는 구조이다.
배열 기반 큐
-
큐의 맨 앞 요소를 제거할 때 모든 요소를 앞으로 한 칸 이동 → 비효율적
-
Circular Queue로 이를 개선 가능
연결 리스트 기반 큐
- front와 rear 포인터를 통해 O(1) 시간에 삽입/삭제 가능
시간 복잡도
| 연산 | 시간 복잡도 |
|---|---|
enqueue | O(1) |
dequeue | O(1) |
peek | O(1) |
활용 사례
-
운영체제의 프로세스 스케줄링
-
프린터 작업 큐 관리
-
너비 우선 탐색 (BFS) 알고리즘
-
이벤트 핸들링 시스템, 메시지 큐
Stack vs Queue 비교
| 항목 | Stack | Queue |
|---|---|---|
| 기본 원리 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입 위치 | top | rear |
| 삭제 위치 | top | front |
| 주요 연산 | push, pop, peek | enqueue, dequeue, peek |
| 시간 복잡도 | O(1) | O(1) |
| 대표 활용 예 | 콜 스택, 괄호 검사, 수식 계산 등 | BFS, 작업 처리, 스케줄링 등 |
마무리
실제 프로그램에서는 단순한 배열이나 리스트보다 이 구조들을 활용한 문제 해결이 훨씬 유연하고 효율적이다. 특히 알고리즘 문제 해결 시 이 구조의 원리적 이해와 구현 경험이 매우 중요하다. 직접 구현하고 다양한 시나리오에서 이들을 적용해 보는 연습이 필요하다.
