Kotlin/Java 컬렉션 구조 비교: Stack vs Queue vs ArrayDeque

스택과 큐는 모든 프로그래머가 한 번쯤은 접해보는 대표적인 선형 자료구조입니다. Java 및 Kotlin에서도 다양한 구현체가 제공되지만, 실제로 어떤 자료구조를 써야 할지 헷갈릴 수 있습니다. 특히 Stack, Queue, ArrayDeque는 모두 삽입/삭제 연산을 제공하면서도 구조와 성능, 사용 목적이 다르기 때문에 정확한 이해가 필요합니다.

이 글에서는 각 자료구조의 특징과 차이점을 비교하고, 어떤 상황에 어떤 자료구조를 선택해야 하는지 실용적인 가이드를 제공합니다.

---

기본 개념 요약

Stack (스택)

• LIFO (Last In, First Out) 구조
• 가장 나중에 삽입된 요소가 가장 먼저 제거됨
• Java의 Stack 클래스는 Vector를 상속 → 동기화 처리됨 (synchronized)
• Kotlin에서도 사용 가능하지만, 더 이상 권장되지 않음

Queue (큐)

• FIFO (First In, First Out) 구조
• 먼저 들어온 요소가 먼저 나감
• Queue는 인터페이스로 제공되며, 구현체로는 LinkedList, PriorityQueue, ArrayDeque 등이 있음
• BlockingQueue, ConcurrentLinkedQueue 등 스레드 안전한 구현도 존재

ArrayDeque (배열 덱)

• 양방향 큐(double-ended queue) 구조
• 스택과 큐 양쪽 모두의 기능을 빠르게 제공
• 내부는 배열 기반 비동기 구조로 매우 빠르고 메모리 효율적
• Java 6+에서 도입, Kotlin에서도 매우 추천되는 구현체

---

Stack vs Queue vs ArrayDeque 상세 비교

항목 Stack Queue (인터페이스) ArrayDeque

기본 구조	LIFO (후입선출)	FIFO (선입선출)	LIFO + FIFO (양방향)
사용 방식	push(), pop(), peek()	add(), remove(), peek()	addFirst/Last, removeFirst/Last
성능	느림 (Vector 기반)	보통 (LinkedList는 느림)	매우 빠름 (가변 배열)
스레드 안전성	동기화	기본 비동기	비동기
유연성	한 방향만 지원	한 방향만 지원	양방향 지원
API 추천 여부	사용 지양	큐 구현 필요 시 사용	적극 추천
주요 단점	구식, 느림	구현체 선택에 따라 성능 차이	null 허용 안 함, 초기 용량 지정 불가

---

코드 예제로 이해하기

▶ Stack 예제 (비추천)

val stack = Stack<Int>()
stack.push(1)
stack.push(2)
println(stack.pop())   // 2
println(stack.peek())  // 1

▶ Queue 예제 (FIFO)

val queue: Queue<Int> = LinkedList()
queue.add(1)
queue.add(2)
println(queue.remove())  // 1
println(queue.peek())    // 2

▶ ArrayDeque 예제 (스택 + 큐)

val deque = ArrayDeque<Int>()

// 스택처럼 사용
deque.addLast(10)
deque.addLast(20)
println(deque.removeLast())  // 20

// 큐처럼 사용
deque.addLast(30)
deque.addLast(40)
println(deque.removeFirst()) // 30

---

어떤 자료구조를 써야 할까?

사용 목적 추천 자료구조

후입선출(LIFO)	ArrayDeque (스택 대체)
선입선출(FIFO)	ArrayDeque, LinkedList
우선순위 큐	PriorityQueue
스레드 안전 큐	ConcurrentLinkedQueue, BlockingQueue
멀티기능 큐 & 빠른 성능	ArrayDeque
옛날 코드 유지	Stack, Vector (비추천)

---

결론

• Stack은 더 이상 사용하지 않는 것이 좋습니다. ArrayDeque가 더 빠르고 유연합니다.
• Queue는 개념상 인터페이스이며, 구현체 선택이 성능과 용도에 영향을 줍니다.
• 대부분의 경우 ArrayDeque 하나로 스택과 큐 모두를 구현할 수 있고, 성능도 가장 우수합니다.
• 실무에서는 무조건 ArrayDeque를 기본 선택지로 생각하고, 필요한 경우에만 Queue, BlockingQueue, PriorityQueue 등을 고려하세요.

---

참고 링크

• Java Docs - ArrayDeque: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayDeque.html
• Kotlin Collections Guide: https://kotlinlang.org/docs/collections-overview.html
• Stack vs Queue vs Deque 성능 비교 (StackOverflow): https://stackoverflow.com/questions/12524826/why-should-i-use-deque-over-stack