[자료구조] 스택/큐 마스터하기 - 비교 및 내부 구현 분석

스택/큐 란?

Stack은 LIFO (Last In First Out) 형태로 가장 나중에 들어간 데이터가 가장 먼저 나오게 되는 자료구조 입니다.

단순하게 바구니에 물건을 쌓고 물건을 하나씩 꺼내는 것을 상상해보면 이해하기 쉬울거에요.

 

Queue는 FIFO (First In First Out) 형태로 가장 먼저 들어간 데이터가 가장 먼저 나오게 되는 자료구조 입니다. 

버스를 타기위해서 줄을 서서 기다리고 버스가 도착했을 때 앞 사람부터 탑승하는걸 상상해보시면 됩니다.

---

 

 

java.util 패키지 제공 클래스 비교

java.util이란 Java 프로그래밍에 유용한 클래스를 모아놓은 패키지로 java를 설치하시면 기본적으로 제공됩니다. 

해당 패키지에는 Stack과 Queue 구현 클래스도 기본적으로 제공하고 있는데요. 제공하는 구현 클래스와 차이점을 한번 살펴볼게요.

 

 

Stack 기능 구현 클래스 비교

java.util 내에는 대표적으로 Stack 기능을 구현한 클래스인 Stack, ArrayDeque 구현 클래스가 존재합니다.

하지만 Stack 구현 클래스의 설명에는 Stack 대신 ArrayDeque 사용을 권장하는 것을 볼 수 있습니다.

 

그렇다면 Stack과 ArrayDeque의 주요 차이점은 어떤게 있을까요?

---

멀티 쓰레드 동기화

Stack 구현 클래스의 CRD (Create, Read, Delete) 메서드를 살펴보면 모두 Synchronized 키워드가 붙어있는걸 확인할 수 있어요.

Stack Delete 메서드

 

 

그에반해, ArrayDeque 구현 클래스는 CRD 메서드에서 멀티 쓰레드 동기화를 지원하지 않아요.

ArrayDeque Delete 메서드

 

 

✋ 멀티 쓰레드 동기화를 지원하는건 더 좋은게 아닌가요?

멀티 쓰레드 환경에서의 동기화는 데이터 무결성 확보를 위해서 무척 중요합니다. 

하지만 이러한 멀티 쓰레드 동기화 작업은 데이터 무결성을 확보해주는 동시에 그에 따른 비용도 있어요.

Stack 구현 클래스는 CRD 메서드에서 Synchronized 키워드는 기본적으로 Lock 방식의 동기화를 지원합니다.
Synchronized 키워드가 붙은 메서드는 쓰레드가 접근할 때 다른 쓰레드가 들어오지 못하도록 문을 잠그고 할 일을 하고, 다른 쓰레드가 해당 메서드로 접근하면 손가락 빨면서 문을 열어줄 때까지 기다리고 처리가 끝난 쓰레드가 문을 열어주면 접근하는 방식이에요.

만약, 쓰레드가 하나이거나, 멀티 쓰레드 동기화가 필요없는 상황이라면 Stack 구현 클래스로 굳이 Lock을 걸어 동기화를 처리하는 로직이 들어갈 필요가 없기 때문에 불필요한 오버헤드가 발생할 수 있어요.

따라서, 멀티 쓰레드 환경에서 Stack을 사용하고 싶다면, ArrayDeque에 동기화 데코레이터를 구현하거나 LinkedBlockingDeque 또는 ConcurrentLinkedDeque 사용을 권장해요.

---

불필요한 기능 노출

위의 CRD 이미지에 나와있듯이 Stack은 기본적으로 Vector 클래스를 상속받아요.

 

우리는 분명 Stack 자료구조에 필요한 메서드만 있으면 되지만, Vector에서 제공하는 메서드도 모두 사용이 가능해서 Stack의 무결성을 해칠 수 있다는 단점이 있어요.

따라서, Vector 레거시 클래스를 상속하는 Stack 클래스는 사용이 권장되지 않아요!

 

 

 

Queue 기능 구현 클래스 비교

java.util 내에는 대표적으로 Queue 기능을 구현한 클래스인 LinkedList, ArrayDeque 구현 클래스가 존재합니다.

하지만 Queue도 마찬가지로 LinkedList 대신 ArrayDeque 사용을 권장할 수 있습니다.

Why is ArrayDeque better than LinkedList

위의 stackoverflow 답변을 토대로 차이점을 한번 알아볼까요?

---

메모리 낭비

LinkedList는 데이터를 접근할 때 index 기준으로 접근하지 않고 각각의 데이터를 감싸는 노드의 포인터 위주로 데이터를 접근한다는 특징을 가져요. 따라서, LinkedList는 각각의 데이터를 Node 객체로 감싸져 있다는 특징이 있어요.

LinkedLIst 내의 Node 클래스

 

따라서, LinkedList는 데이터를 추가할 때마다 Node 객체 참조 및 다음/이전 노드 참조만큼 메모리를 더 잡아먹어요!

 

🤔 JVM 64bit 기준 LinkedLIst, ArrayDeque 모두 Integer 객체를 저장한다고 가정해볼게요.

LinkedList : Node 객체 참조(8bytes) + 데이터 참조 (8bytes) + 다음 노드 참조 (8bytes) + 이전 노드 참조 (8bytes) + Integer 객체 (16bytes) = 48 bytes
ArrayDeque : 데이터 참조 (8bytes) + Integer 객체 (16bytes) = 24 bytes

 

물론, 위의 가정은 데이터 하나만 저장했을 때의 가정이고 실제로는 ArrayDeque의 초기 배열 크기를 고려해줘야 합니다.

---

 

 

ArrayDeque 메서드 로직 살펴보기

스택/큐 를 사용할 때는 ArrayDeque 구현체를 사용하는게 이점이 많다는 것을 알았으니 ArrayDeque 로직에 대해서 한번 살펴볼까요?

스택/큐 모두 Deque 내에서 CRD 메서드는 앞 기준이냐 뒤 기준이냐로 로직이 비슷하므로 앞 기준으로 살펴볼게요.

 

객체 생성

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
	// 데이터 저장 배열
	transient Object[] elements;
    
    // 배열의 선두 인덱스로 0 <= head < elements.length 범위를 가짐
	transient int head;
    
    // 다음 데이터가 추가될 인덱스로 elements[tail]은 항상 null
	transient int tail;

	// 배열 헤더 공간을 제외한 배열 최대 크기
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    // 기본 생성자
    public ArrayDeque() {
        elements = new Object[16];
    }
    
    // 배열 크기 지정 생성자
    public ArrayDeque(int numElements) {
        elements =
        	// 0 또는 음수 값으로 선언해도 오류가 발생하지 않고 크기 1로 지정
            new Object[(numElements < 1) ? 1 :
                       (numElements == Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                       numElements + 1];
    }
}

 

가장 처음에 보이는 특징은 ArrayDeque의 기본 생성자는 기본적으로 16 배열 크기를 가지고 초기화가 된다는 점이네요.

그리고, 0 또는 음수 값으로 선언해도 오류를 던지지 않고 1 배열 크기로 초기화를 해주네요.

마지막으로, ArrayDeque는 Stack, Queue 모두 지원하기 때문에 head, tail 두 개의 인덱스 정보로 데이터를 탐색해요.

 

 

데이터 추가

public void push(E e) {
        addFirst(e);
    }

    public void addFirst(E e) {
        // 데이터가 null이라면 NullPointerException 발생!
        if (e == null)
            throw new NullPointerException();

        // final로 선언하여 수정할 수 없는 배열 변수 선언
        final Object[] es = elements;

        // head 인덱스를 -1 후 데이터 추가
        es[head = dec(head, es.length)] = e;

        // 만약 head 인덱스와 tail 인덱스가 같다면 배열 크기 증가
        if (head == tail)
            grow(1);
    }

    static final int dec(int i, int modulus) {
        // 만약 인덱스가 음수가 된다면 배열 마지막 인덱스로 이동
        // 원형 큐 방식
        if (--i < 0) i = modulus - 1;
        return i;
    }

 

여기서 눈여겨 볼 점은 데이터를 추가할 때 인덱스 범위를 넘어선 경우 원형큐 방식으로 반대편 인덱스로 이동한다는 점이에요.

 

 

데이터 삭제

public E pop() {
        return removeFirst();
    }

    public E removeFirst() {
        E e = pollFirst();

        // null 값을 허용하지 않지만 에러 처리해둠
        if (e == null)
            throw new NoSuchElementException();
        return e;
    }

    public E pollFirst() {
        final Object[] es;
        final int h;

        // head에 해당하는 데이터 가져오기
        E e = elementAt(es = elements, h = head);

        if (e != null) {
            // 해당 데이터 삭제
            es[h] = null;

            // head 인덱스 증가시키기
            head = inc(h, es.length);
        }
        return e;
    }

    @SuppressWarnings("unchecked")
    static final <E> E elementAt(Object[] es, int i) {
        return (E) es[i];
    }

    static final int inc(int i, int modulus) {
        // 인덱스 범위를 넘어선 경우 0으로 초기화
        if (++i >= modulus) i = 0;
        return i;

 

여기서 흥미로웠던 점은 데이터 추가 로직을 보면 null 값 추가를 허용하지 않는데도 불구하고 removeFirst 메서드와 pollFirst 메서드에서 null 처리를 해주는 로직이 있었다는 점이에요.

 

 

데이터 조회

public E peek() {
        return peekFirst();
    }
    
public E peekFirst() {
        return elementAt(elements, head);
}

 

데이터 조회는 단순하게 head 인덱스 데이터를 조회하는 로직이네요.

 

 

크기 증가

private void grow(int needed) {
        // 값 변경 불가능한 배열 길이 변수 선언
        final int oldCapacity = elements.length;
        int newCapacity;

        // 새 크기 증가량(jump) 계산:
        // 현재 크기가 64 미만이면 현재 크기 + 2,
        // 64 이상이면 현재 크기의 절반(우측 시프트 연산으로 빠르게 계산)
        int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);

        // 두 가지 조건 중 하나라도 true면 newCapacity() 메서드 호출:
        // 1. jump가 needed보다 작은 경우
        // 2. 현재 크기에 jump를 더한 값이 MAX_ARRAY_SIZE를 초과하는 경우
        if (jump < needed
                || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
            newCapacity = newCapacity(needed, jump);

        // 새로운 크기로 배열을 복사하여 elements 업데이트
        final Object[] es = elements = Arrays.copyOf(elements, newCapacity);

        if (tail < head || (tail == head && es[head] != null)) {
            int newSpace = newCapacity - oldCapacity;

            // 기존의 head 인덱스부터 채워진 데이터를 늘어난 배열 끝으로 이동
            System.arraycopy(es, head,
                    es, head + newSpace,
                    oldCapacity - head);

            // tail과 head 사이 값을 null로 채움
            for (int i = head, to = (head += newSpace); i < to; i++)
                es[i] = null;
        }
    }

    private int newCapacity(int needed, int jump) {
        final int oldCapacity = elements.length, minCapacity;

        // 기존 배열 크기 + 늘리고 싶은 배열 크기 합이 MAx_ARRAY_SIZE보다 크면
        if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
            // needed 값이 기존 배열 크기를 넘어서는 음수일 경우
            if (minCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");

            return Integer.MAX_VALUE;
        }

        if (needed > jump)
            return minCapacity;

        return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
                ? oldCapacity + jump
                : MAX_ARRAY_SIZE;
    }

 

grow 메서드 부분에서 살짝 헷갈렸는데 다음과 같이 배열을 늘려서 데이터를 복사하는 과정을 거쳐요.

기존의 배열 상태
[3, 4, 5, 1, 2]
tail = 3, head = 3

Arrays.copyOf(elements, newCapacity) 이후
[3, 4, 5, 1, 2, null, null, null, null, null]
tail = 3, head = 3

System.arraycopy(es, head, es, head + newSpace, oldCapacity - head) 이후
[3, 4, 5, 1, 2, null, null, null, 1, 2]
tail = 3, head = 3

for (int i = head, to = (head += newSpace); i < to; i++) es[i] = null;  이후
[3, 4, 5, null, null, null, null, null, 1, 2]
tail = 3, head = 8

 

---

 

 

마치며

기존에 스택과 큐 자료구조를 사용할 때 Stack 클래스와 LinkedList 클래스를 주로 사용했었습니다. 이번 포스팅 글을 작성하면서 이러한 클래스들의 구현 방식과 적절한 사용 상황을 이해하지 않고 생각없이 쓰고 있었다는 느낌을 많이 받았어요. 각각의 구현체들은 어떤 방식으로 구현되어 있고 상황에 맞춰 적절한 구현체를 사용하는 것이 효율성 높은 애플리케이션을 만드는 밑바탕이 되지 않을까 싶습니다.

 

---

 

 

참조 문헌

[Java] 왜 Stack 대신 Deque를 사용하는가? | Vanslog

Deque, LinkedList 와 ArrayDeque

Integer vs int: with regard to memory