[CS] Stack, Queue (LinkedList) 대신 ArrayDeque 를 추천하는 이유

오규성·2025년 11월 1일

우리가 코딩테스트나 선입선출, 후입선출의 자료구조를 사용할 때는 Stack 과 LinkedList (혹은 다른 Queue) 를 자주 사용한다.

하지만 이러한 방식은 레거시 방식이며, 현재는 ArrayDeque 를 사용하는 것이 권장된다.
이러한 이유를 설명하기에 앞서 Stack 과 LinkedList 에 관한 짧은 설명을 해보자

# Stack 이란 ?

후입선출 [LIFO (Last In First Out)] 의 특징을 가지는 자료구조로서, 나중에 들어가는 것이 가장 먼저 출력된다.

Stack 의 단점

우선 Stack Class 에 대해서 간단히 살펴보자.

public class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }

    public E push(E item) {
        addElement(item);

        return item;
    }
    
    ...

Stack 을 살펴보면 Vector 라는 클래스를 상속받는 것으로 나와있다.
Vector 클래스는 ArrayList 로 대체되어 현재는 사용되지 않는 클래스이며, 내부적으로 문제점이 존재한다.

> synchronized function

벡터의 경우 내부적으로 동기화를 위해 거의 모든 함수에 synchronized 키워드를 설정하여 모든 작업에 Lock 을 걸고, 여러 스레드에서 동시다발적으로 접근하지 못하게 설정하였다.

이러한 동기화 옵션의 경우 멀티 스레드 환경에서는 스레드 안정성이 좋아지지만, 단일스레드 환경에서는 불필요한 옵션으로 인한 오버헤드 발생으로 이어질 뿐이다.

위 이미지는 Vector 를 상속하는 Stack.push() 코드와 Vector.addElement 이다.
이처럼 내부적으로 Stack 이 Vector 클래스의 synchronized function 을 호출하기 때문에 불필요한 오버헤드가 생기므로, 특별한 경우가 아니면 ArrayDeque 를 사용하는 것이 좋다.

만약 동기화가 필요하더라도 Vector 나 상속 클래스들이 아닌, 다른 클래스를 활용하는 것이 추천된다.

# Queue 란?

선입선출 [FIFO (First In First Out)] 의 특징을 가지는 자료구조로서, 먼저 들어간 값이 먼저 출력된다.

Queue [LinkedList] 의 단점

Queue 는 Interface 이기 때문에 일반적으로 이를 구현하는 클래스를 활용하여 Queue 로 작업한다.

val queue: java.util.Queue<Int> = LinkedList()

queue.offer(1)
queue.poll() // 1

이러한 Queue 의 구현체로는 일반적으로 LinkedList 클래스를 사용하는데, 과거에는 Queue 의 구현체로 만들어진 거의 유일한 클래스였기 때문이다.

이러한 이유로 Queue 를 구현하려고 하면 LinkedList 를 사용하였는데, 이 LinkedList 에는 여러 문제가 존재했다.

데이터 하나하나가 각 Node 객체에 담겨 뿔뿔이 흩어지기 때문에, 다음 데이터 탐색 시 메모리 주소를 점프해야하기 때문에 캐시 효율이 나쁘다.
데이터를 저장할 때마다 Node 객체를 생성해야하고, 이전/다음 노드를 가리키는 포인터를 추가로 저장해야하기 때문에 메모리 낭비가 존재한다.

이와는 반대로 ArrayDeque 의 경우 하나의 연속된 배열을 사용하고, 데이터를 담을 배열 공간만 필요하므로 시간 및 공간 복잡도가 줄어들기 때문에 ArrayDeque 의 사용이 권장되는 것이다.

Java.util.ArrayDeque 와 kotlin.collection.ArrayDeque

ArrayDeque 는 Java.util.ArrayDeque 와 Kotlin.collection.ArrayDeque 로 나뉜다.

공통된 사항

ArrayDeque 의 경우 head (원소의 시작위치) 와 tail (원소의 끝위치) 를 판별하여 addFirst, addLast, removeFirst, removeLast, get(idnex) [이 경우는 코틀린만] 시 O(1) 의 시간복잡도를 가진다.

또한 head 와 tail 의 위치가 같아지면 내부가 꽉 찼거나, 비어있다는 것을 의미한다. 이 상태에서 데이터를 추가하려고 하는 경우 동적으로 내부 배열 크기를 증가시킨다.

Java.util.ArrayDeque

자바의 ArrayDeque 는 AbstracCollection 을 상속하며, Deque 를 구현한다. Deque 는 Queue 를 상속한다.
그렇기에 java.util.ArrayDeque 는 자료구조 Queue, Deque 로도 표현할 수 있다.

// Queue 방식.
val queue: Queue<Int> = java.util.ArrayDeque()
queue.offer(1) // 1
queue.offer(2) // 2
println(queue.poll()) // 1

// Deque 방식.
val deque: Deque<Int> = java.util.ArrayDeque()
deque.offer(1) // 1
deque.offer(2) // 2
println(deque.pollLast()) // 2
deque.offer(2)
println(deque.poll()) // 1

// Stack 방식.
val stack: Deque<Int> = java.util.ArrayDeque()
stack.addLast(1)
stack.addLast(2)
println(deque.removeLast()) // 2

kotlin.collection.ArrayDeque

Kotlin 에서의 ArrayDeque 는 Java 의 ArrayDeque 와는 달리 AbstractMutableList 를 상속한다.
그렇기에 ArrayDeque 를 사용할때, Queue 나 Deque 와 같은 데이터타입으로 선언하지는 못한다.

그러나 다음과 같이 addFirst(), addLast(), removeFirst(), `removeLast() 를 사용하여 Stack, Queue, Deque 를 대신할 수 있다.

    val stack = ArrayDeque<Int>()
    stack.addLast(1)
    stack.addLast(2)
    stack.addLast(3)

    stack.removeLast() // 3
    stack.removeLast() // 2
    stack.removeLast() // 1

    val queue = ArrayDeque<Int>()
    stack.addLast(1)
    stack.addLast(2)
    stack.addLast(3)
    stack.removeFirst() // 1
    stack.removeFirst() // 2
    stack.removeFirst() // 3

    val deque = ArrayDeque<Int>()
    stack.addLast(1)
    stack.addLast(2)
    stack.addLast(3)
    stack.removeFirst() // 1
    stack.removeLast() // 3
    stack.removeFirst() // 2