스택 vs 큐
기술노트
스택 vs 큐
스택(Stack)
- 정의: 후입선출(LIFO, Last-In-First-Out) 구조
- 특징: 가장 마지막에 들어온 데이터가 가장 먼저 나가는 구조
- 주요 연산:
- push(삽입): 스택의 맨 위에 데이터 추가
- pop(삭제): 스택의 맨 위에서 데이터 제거 및 반환
- 활용 예:
- 함수 호출 스택: 프로그래밍 언어의 함수 호출 관리
- 브라우저 방문 기록: 뒤로 가기 기능
- 실행 취소(undo) 기능: 최근 작업부터 취소
- 괄호 검사: 표현식의 괄호 짝 맞추기
- 깊이 우선 탐색(DFS) 구현
// Java에서 스택 구현 예시
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
// 데이터 삽입
stack.push(1);
stack.push(2);
stack.push(3);
// 데이터 조회
System.out.println("맨 위 원소: " + stack.peek()); // 3
// 데이터 삭제
System.out.println("삭제된 원소: " + stack.pop()); // 3
System.out.println("삭제된 원소: " + stack.pop()); // 2
// 스택 크기 확인
System.out.println("스택 크기: " + stack.size()); // 1
}
}
큐(Queue)
- 정의: 선입선출(FIFO, First-In-First-Out) 구조
- 특징: 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조
- 주요 연산:
- enqueue(삽입): 큐의 뒤쪽에 데이터 추가
- dequeue(삭제): 큐의 앞쪽에서 데이터 제거 및 반환
- 활용 예:
- 프린터 대기열: 인쇄 작업 순서 관리
- 프로세스 스케줄링: CPU 작업 순서 관리
- 메시지 큐: 비동기 통신에서 메시지 전달
- 너비 우선 탐색(BFS) 구현
- 캐시 구현
// Java에서 큐 구현 예시
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
// 데이터 삽입
queue.offer(1);
queue.offer(2);
queue.offer(3);
// 데이터 조회
System.out.println("맨 앞 원소: " + queue.peek()); // 1
// 데이터 삭제
System.out.println("삭제된 원소: " + queue.poll()); // 1
System.out.println("삭제된 원소: " + queue.poll()); // 2
// 큐 크기 확인
System.out.println("큐 크기: " + queue.size()); // 1
}
}
스택과 큐의 비교
| 특성 | 스택(Stack) | 큐(Queue) |
|---|---|---|
| 삽입/삭제 원칙 | LIFO (후입선출) | FIFO (선입선출) |
| 삽입 위치 | 상단(top) | 후단(rear) |
| 삭제 위치 | 상단(top) | 전단(front) |
| 구현 방식 | 배열 또는 연결 리스트 | 배열, 연결 리스트, 원형 큐 |
| 시간 복잡도 | 삽입/삭제: O(1) | 삽입/삭제: O(1) |
| 공간 관리 | 고정 크기 또는 동적 확장 | 고정 크기, 동적 확장, 원형 구조 |
| 적합한 작업 | 역추적, 재귀 제거 | 순차 처리, 대기열 관리 |
변형된 자료구조
스택 변형
- 양방향 스택: 하나의 배열에서 양 끝에서 스택 연산
- 최소/최대 스택: 최소값 또는 최대값 추적 기능 추가
- 브라우저 스택: 앞으로 가기/뒤로 가기 기능 구현
큐 변형
- 우선순위 큐: 우선순위에 따라 데이터 출력 (힙으로 구현)
- 원형 큐: 배열의 끝과 시작을 연결하여 메모리 효율 향상
- 덱(Deque): 양쪽 끝에서 삽입/삭제 가능한 이중 종단 큐
성능 고려사항
- 스택: 단순한 구현, 메모리 접근 지역성 우수, 동적 확장 시 오버헤드 발생 가능
- 큐: 배열 구현 시 데이터 이동 오버헤드 발생 가능, 연결 리스트 구현 시 추가 메모리 필요
- 선택 기준: 문제의 특성(LIFO/FIFO), 구현 언어의 내장 자료구조, 성능 요구사항에 따라 결정
