Stack, Queue, Deque, PriorityQueue 완벽 비교 분석

자바 큐와 스택, 어떤 컬렉션을 선택해야 할까? Stack, Queue, Deque, PriorityQueue 완벽 비교 분석

자바 개발에서 데이터를 특정 순서에 따라 처리해야 할 때, 우리는 자연스럽게 큐(Queue)와 스택(Stack) 자료구조를 떠올립니다. 하지만 자바 컬렉션 프레임워크는 단순히 Queue 인터페이스와 Stack 클래스 외에도 다양한 목적과 환경에 최적화된 여러 구현체를 제공합니다. ArrayDeque, LinkedList, PriorityQueue 등 이름은 비슷하지만 내부 동작 방식과 성능 특성은 크게 다릅니다.

어떤 상황에 어떤 컬렉션을 선택해야 애플리케이션의 성능과 안정성을 극대화할 수 있을까요? 이 글에서는 각 컬렉션의 핵심 특징과 시간 복잡도, 그리고 용도에 맞는 최적의 선택지를 명확하게 제시합니다.

자료구조의 기본: LIFO와 FIFO

본격적인 비교에 앞서, 스택과 큐의 근본적인 동작 방식을 이해해야 합니다.

• 스택 (Stack – LIFO): 후입선출(Last-In, First-Out) 구조입니다. 가장 마지막에 추가된 데이터가 가장 먼저 제거됩니다. 접시를 쌓고 위에서부터 하나씩 빼는 것을 생각하면 쉽습니다.
• 큐 (Queue – FIFO): 선입선출(First-In, First-Out) 구조입니다. 가장 먼저 추가된 데이터가 가장 먼저 제거됩니다. 은행 창구에서 줄을 선 순서대로 업무를 보는 것과 같습니다.

Java 큐/스택 계열 컬렉션 상세 비교

이제 각 컬렉션의 특징을 깊이 있게 살펴보겠습니다.

핵심 질문: Stack 클래스 대신 왜 ArrayDeque를 사용해야 하는가?

자바를 처음 배울 때 스택을 Stack 클래스로 구현하는 경우가 많지만, 이는 현재 권장되지 않는 방법입니다. 현대 자바 개발에서는 스택이 필요할 때 ArrayDeque를 사용하는 것이 표준입니다.

Stack 클래스는 오래된 Vector를 기반으로 만들어져 모든 메서드에 동기화 락(lock)이 걸려있습니다. 단일 스레드 환경에서는 이 락이 불필요한 성능 저하를 유발합니다. 반면, ArrayDeque는 비동기 방식으로 동작하며 내부적으로 배열을 사용하여 훨씬 효율적이고 빠릅니다. 따라서 스택이 필요하다면 Stack 클래스가 아닌 ArrayDeque를 사용해야 합니다.

// 추천하는 스택 구현 방식
Deque<String> stack = new ArrayDeque<>();
stack.push("Apple"); // addFirst()와 동일
stack.push("Banana");
System.out.println(stack.pop()); // "Banana" (removeFirst()와 동일)

상황에 맞는 최적의 컬렉션 선택 가이드

애플리케이션의 요구사항에 따라 가장 적합한 컬렉션을 선택하는 것이 중요합니다.

• 일반적인 스택(LIFO)이 필요할 때
  • 추천: ArrayDeque
  • 이유: Stack 클래스보다 빠르고, Deque 인터페이스를 사용하여 스택의 모든 기능을 (push, pop, peek) 명확하게 제공합니다.
• 일반적인 큐(FIFO)가 필요할 때
  • 추천: ArrayDeque, LinkedList
  • 이유: ArrayDeque는 대부분의 시나리오에서 더 나은 성능을 보입니다. LinkedList는 큐의 양 끝뿐만 아니라 리스트 중간에서의 삽입/삭제가 필요한 매우 특수한 경우에 고려할 수 있습니다. 하지만 순수한 큐의 목적이라면 ArrayDeque가 더 효율적입니다.
• 데이터를 우선순위에 따라 처리해야 할 때
  • 추천: PriorityQueue
  • 이유: 데이터를 추가할 때마다 내부적으로 최소 힙(min-heap) 구조에 따라 자동 정렬됩니다. 따라서 poll() 메서드를 호출하면 항상 우선순위가 가장 높은(기본적으로 가장 작은 값) 요소가 반환됩니다. 우선순위 작업 스케줄링이나 최단 경로 탐색 알고리즘 등에 필수적입니다.
• 멀티스레드 환경에서 높은 처리량이 필요할 때
  • 추천: ConcurrentLinkedQueue
  • 이유: 락-프리(lock-free) 알고리즘을 사용하여 여러 스레드가 동시에 큐에 접근하더라도 경합을 최소화합니다. 스레드 간 데이터 공유 시 블로킹 없이 최대한의 성능을 내야 하는 경우에 적합합니다.
• 생산자-소비자 패턴을 구현해야 할 때
  • 추천: BlockingQueue 계열 (ArrayBlockingQueue, LinkedBlockingQueue)
  • 이유: 큐가 비어있을 때 데이터를 가져가려는 스레드(take())는 데이터가 들어올 때까지 자동으로 대기(블로킹)하고, 큐가 가득 찼을 때 데이터를 추가하려는 스레드(put())는 공간이 생길 때까지 대기합니다. 이는 스레드 간의 작업을 안전하고 효율적으로 조율하는 핵심 메커니즘을 제공합니다.

주요 사용 예제 코드

// Queue (FIFO) - ArrayDeque 사용
Queue<String> queue = new ArrayDeque<>();
queue.offer("Task 1");
queue.offer("Task 2");
System.out.println(queue.poll()); // "Task 1"

// PriorityQueue (우선순위 - 최소 힙)
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(10);
pq.offer(1);
pq.offer(5);
System.out.println(pq.poll()); // 1 (가장 작은 값)
System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 10


// Deque (양방향 큐)
Deque<String> deque = new ArrayDeque<>();
deque.addFirst("Header");  // 앞에 추가
deque.addLast("Footer");   // 뒤에 추가
System.out.println(deque.pollFirst()); // "Header"
System.out.println(deque.pollLast());  // "Footer"

자바 컬렉션 프레임워크는 다양한 시나리오에 대응할 수 있도록 세분화된 큐와 스택 구현체를 제공합니다. 단순히 LIFO, FIFO라는 개념에만 머무르지 않고, 애플리케이션의 동시성 요구사항, 데이터의 정렬 필요성, 그리고 성능 목표를 종합적으로 고려하여 가장 적합한 컬렉션을 선택하는 것이 견고하고 효율적인 소프트웨어를 만드는 첫걸음입니다.

---

쿠버네티스 패키지관리

     📕교보문고 종이책 구매
     📱교보문고 이북 구매
🛒부크크 종이책 구매

실수로 배우는 자바

📕교보문고 종이책 구매
📱교보문고 이북 구매
🛒 부크크 종이책 구매

AI와 함께하는 협업 바이블

📱교보문고 이북 구매
     🛒부크크 종이책 구매
책은 yes24, 알라딘에도 판매 되고 있습니다.