📌 목차
1. 스택(Stack)과 큐(Queue)란?
스택(Stack)과 큐(Queue)는 가장 기본적인 선형 자료구조입니다.
데이터를 저장하고 꺼내는 방식에서 차이가 있으며, 다양한 알고리즘과 시스템에서 핵심적으로 사용됩니다.
- 스택: 후입선출 (LIFO) - 나중에 들어간 데이터가 먼저 나옴
- 큐: 선입선출 (FIFO) - 먼저 들어간 데이터가 먼저 나옴
2. 스택 vs 큐 구조 비교
| 항목 | 스택(Stack) | 큐(Queue) |
|---|---|---|
| 동작 원리 | 후입선출 (LIFO) | 선입선출 (FIFO) |
| 삽입 위치 | Top (맨 위) | Rear (뒤) |
| 삭제 위치 | Top (맨 위) | Front (앞) |
| 주요 메서드 | push, pop, peek | enqueue, dequeue, peek |
| 사용 예시 | 웹 브라우저 방문 기록, 되돌리기 | 대기열, BFS 탐색 |
3. 주요 연산 및 시간 복잡도
| 연산 | 스택 | 큐 |
|---|---|---|
| 삽입 | O(1) – push | O(1) – enqueue |
| 삭제 | O(1) – pop | O(1) – dequeue |
| 조회 | O(1) – peek | O(1) – peek |
두 구조 모두 삽입과 삭제가 빠르고 단순하지만, 동작 방향이 완전히 다르기 때문에 사용처는 다릅니다.
4. 사용되는 대표적인 사례
✅ 스택이 쓰이는 상황
- 되돌리기 기능 (Undo/Redo): 마지막 작업부터 차례로 취소
- 괄호 짝 검사: 열고 닫는 괄호 순서 확인
- 재귀 호출 처리: 함수 호출 흐름을 콜 스택으로 관리
- 웹 브라우저 뒤로 가기
✅ 큐가 쓰이는 상황
- 작업 대기열 처리: 프린터, 콜센터 요청 순차 처리
- BFS (너비 우선 탐색): 그래프/트리 탐색 알고리즘
- 실시간 시스템: 메시지 큐, 패킷 처리 등
- OS 프로세스 스케줄링
5. 자바에서 스택과 큐 사용법
📌 Stack 사용 예시
import java.util.Stack;
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2 출력
System.out.println(stack.peek()); // 1 출력
📌 Queue 사용 예시
import java.util.LinkedList;
import java.util.Queue;
Queue<String> queue = new LinkedList<>();
queue.offer("A");
queue.offer("B");
System.out.println(queue.poll()); // A 출력
System.out.println(queue.peek()); // B 출력
자바에서는 Stack, Queue, Deque 등 다양한 컬렉션 구현체로 쉽게 자료구조를 사용할 수 있습니다.
✅ 마무리 요약
- 스택(Stack): 후입선출 구조로, 되돌리기, 함수 호출 처리에 적합
- 큐(Queue): 선입선출 구조로, 대기열 처리, 실시간 데이터 처리에 유리
- 두 구조 모두 자료 순서에 기반한 연산에서 매우 중요하며, 알고리즘과 실무에 모두 필수