스택? 큐?

시리즈

2025.03.11 - [Java/자료구조] - 스택? 큐?

2025.03.11 - [Java/자료구조] - Deque?

 

자바 기반 설명이며 개념에 관한 내용을 다룹니다.

📌 핵심내용

스택(Stack)과 큐(Queue)는 기본적인 자료구조로
동기화(스레드 세이프), 시간 복잡도, 알고리즘 적용 방식에 따라 성능과 활용도가 크게 달라집니다.
본 글에서는 실무에서 발생하는 문제와 해결 방안을 중심으로 심화 내용을 다룹니다.

 

---

1. 스택(Stack)과 큐(Queue)의 차이점

구분스택(Stack)큐(Queue)

구분	스택(Stack)	큐(Queue)
구조	후입선출(LIFO)	선입선출(FIFO)
동기화	Stack (Thread-safe X) ConcurrentLinkedDeque (Thread-safe O)	LinkedList (Thread-safe X) ConcurrentLinkedQueue (Thread-safe O)
시간 복잡도	삽입/삭제: O(1), 검색: O(n)	삽입/삭제: O(1), 검색: O(n)
주요 알고리즘 활용	DFS(깊이 우선 탐색), 백트래킹, 메서드 호출 스택	BFS(너비 우선 탐색), 작업 스케줄링, 네트워크 패킷 처리

---

2. 동기화(스레드 세이프) 고려 사항

멀티스레드 환경에서 스택과 큐를 사용할 때 동기화 이슈가 발생할 수 있습니다. 기본적인 Stack과 LinkedList는 스레드 안전하지 않으며, 동기화를 고려한 자료구조를 사용해야 합니다.

2.1 스택의 동기화

• Stack 클래스: 동기화 지원 X → 멀티스레드 환경에서는 ConcurrentLinkedDeque 또는 Collections.synchronizedList(new LinkedList<>()) 사용 필요
• 사용 사례: JVM의 메서드 호출 스택은 각 스레드별로 분리된 스택을 유지하여 동기화 문제를 해결함

2.2 큐의 동기화

• LinkedList 기반 큐: 동기화 지원 X → 멀티스레드 환경에서는 ConcurrentLinkedQueue 또는 BlockingQueue 계열(ArrayBlockingQueue, LinkedBlockingQueue) 사용
• 사용 사례: Java의 ExecutorService는 BlockingQueue를 사용하여 작업을 스레드풀에 안전하게 할당

---

3. 시간 복잡도 분석

스택과 큐는 삽입/삭제 연산이 O(1)이지만, 검색 연산이 O(n)으로 성능 저하가 발생할 수 있습니다.

3.1 스택의 시간 복잡도

• 삽입(push) / 삭제(pop): O(1) (항상 마지막 요소 접근)
• 검색(contains, search): O(n) (전체 순회 필요)

3.2 큐의 시간 복잡도

• 삽입(enqueue) / 삭제(dequeue): O(1) (헤드 또는 테일에서 연산 수행)
• 검색(contains): O(n) (전체 탐색 필요)

최적화 사례:

• 우선순위 큐(PriorityQueue) 사용 시 O(log n) 연산 가능 (힙(Heap) 기반)
• Deque(양방향 큐) 활용: 특정 시나리오에서 O(1) 연산 가능 (예: Sliding Window 알고리즘)

---

4. 알고리즘 활용 사례

4.1 스택 활용 사례

1. DFS(깊이 우선 탐색): 그래프 탐색에서 스택을 활용하여 재귀 없이 구현 가능
2. 백트래킹(Backtracking): 상태를 저장하고 이전 상태로 돌아갈 때 스택 활용
3. 문자열 괄호 검사: 여는 괄호를 스택에 저장하고 닫는 괄호가 올 때 비교

4.2 큐 활용 사례

1. BFS(너비 우선 탐색): 최단 경로 탐색에서 큐를 활용하여 레벨별 탐색
2. 운영체제의 작업 스케줄링: 프로세스 실행 대기열을 FIFO 방식으로 처리
3. 네트워크 패킷 처리: 데이터 패킷이 도착한 순서대로 처리되는 큐 구조 활용

---

5. 결론

• 스택: 후입선출 구조로 DFS, 백트래킹, 메서드 호출 관리에 유용
• 큐: 선입선출 구조로 BFS, 작업 스케줄링, 네트워크 패킷 처리에 적합
• 멀티스레드 환경에서는 ConcurrentLinkedQueue, BlockingQueue 등 스레드 안전한 자료구조 사용이 필수
• 시간 복잡도를 고려하여 PriorityQueue, Deque 등의 최적화된 자료구조를 활용하면 성능을 개선할 수 있음