728x90
반응형
Stack / Queue / Deque
➡️ 순서를 가진 선형 구조
📌 Stack
- 정의: "쌓아 올린" 구조, LIFO (Last In, First Out)
- 동작:
push(x)→ 맨 위에 데이터 넣기pop()→ 맨 위에서 데이터 삭제하기peek()→ 맨 위 데이터 확인 (삭제는 안 함)
- 자바 구현: Stack<E>, 또는 Deque<E>를 이용해서 구현하는 게 더 권장됨
✅ 사용 상황
- 함수 호출(콜 스택)
- Undo/Redo 기능
- 괄호 검사, 수식 계산 (예: 후위 표기법 계산기)
📌 Queue
- 정의: 줄 서기 구조, FIFO (First In, First Out)
- 동작:
offer(x)→ 뒤(rear)에 데이터 넣기poll()→ 앞(front)에서 데이터 꺼내기peek()→ 맨 앞 데이터 확인 (삭제는 안 함)
- 자바 구현: Queue<E> 인터페이스, 보통 LinkedList<E>나 ArrayDeque<E>로 구현
✅ 사용 상황
- 작업 대기열 (프린터 작업, 요청 처리)
- BFS (너비 우선 탐색)
- 캐시 구현 (순차적 처리 필요할 때)
📌 Deque (Double-Ended Queue)
- 정의: 양쪽 끝에서 삽입/삭제 가능한 큐
- 동작:
offerFirst(x)→ 앞에 넣기offerLast(x)→ 뒤에 넣기pollFirst()→ 앞에서 꺼내기pollLast()→ 뒤에서 꺼내기
- 자바 구현: Deque<E> 인터페이스, 대표적으로 ArrayDeque<E> 사용
✅ 사용 상황
- 양방향 탐색
- 슬라이딩 윈도우 문제
- 스택/큐를 동시에 흉내낼 때
- 회전 큐 (예: 원형 버퍼)
📊 비교
자료구조 구조 삽입/삭제 위치 장점
| 자료구조 | 구조 | 삽입/삭제 위치 | 장점 | 단점 | 대표 활용 |
| Stack | LIFO | 한쪽(top)만 | 단순, 직관적 | 중간 접근 불가 | 함수 호출, Undo/Redo, 괄호 검사 |
| Queue | FIFO | 삽입: 뒤 / 삭제: 앞 | 순차적 처리에 적합 | 한쪽만 꺼낼 수 있음 | 작업 대기열, BFS, 캐시 |
| Deque | 양쪽 | 앞뒤 모두 삽입/삭제 | 스택+큐 동작 모두 가능 | 구현 복잡도↑ | 양방향 탐색, 슬라이딩 윈도우, 원형 큐 |
✅ 정리
- Stack → 뒤집어서 다시 꺼내야 할 때
- Queue → 순서대로 처리해야 할 때
- Deque → 양방향이 필요하거나 스택+큐 둘 다 써야 할 때
728x90
반응형