Java Stack과 Deque

ordilov / 2022. 3. 27

LIFO(Last In First Out) 의 대표적인 구조로 Stack이 있습니다. Java에서 Stack 자료 구조를 지원하기 위해 Stack 클래스와 Deque 인터페이스를 제공합니다. 이 중에서 Stack 대신 Deque를 사용하는 것이 권장됩니다.

왜 자료구조 이름과 동일하고 직관적인 Stack 대신 Deque를 사용하는지 알아보겠습니다.

Java Collection 중 관련된 Stack과 Deque의 구조입니다.

Stack은 Java 1.0부터 제공되어 Vector 클래스를 상속받습니다. Vector 클래스의 특징은 Thread Safe한 대신 동기화하지 않는 구현체보다 느립니다. Stack은 Vector를 상속받으면서 그 단점을 그대로 물려받습니다. 또 다른 Stack의 특징으로는 초기 크기를 지정하는 생성자가 없다는 점이 있습니다. 언뜻 생각하면 Stack도 Queue처럼 인터페이스로 정의되어 있어야 합니다. 하지만 아쉽게도 Java 초기버전에서 위와 같은 설계로 인해 Stack은 클래스로 정의되어 있습니다.

Deque는 Java 1.6부터 제공되어 Queue 인터페이스를 상속받습니다. 이름에서 보다시피 Queue의 기본적인 메서드에서 Stack의 메서드 이름들이 추가되었습니다. Java Stack docs에서도 LIFO를 사용할 때 Deque를 사용하길 권장하고 있습니다.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

Deque의 구현체로 단일 쓰레드에서 사용하는 구현체부터 보겠습니다. ArrayDeque와 LinkedList가 있으며 이름처럼 Array과 LinkedList로 구현한 차이가 있습니다. 따라서 장단점도 각자 자료구조가 가지는 장단점과 일치합니다.

• Array는 순차접근시 인덱스만 이동하면 되기 때문에 어느 위치로든 이동이 간단합니다.

• Array는 크기가 고정되어 크기의 변동이 큰 경우 불리합니다.

  • 크기보다 커지는 경우 메모리 할당이 필요합니다.
  • 커진 크기에서 삭제를 많이하는 경우 메모리 낭비가 심해집니다.

• LinkedList는 특정 노드에 접근하려면 그 사이에 있는 모든 노드를 순회해야 합니다.

• LinkedList는 다음 노드의 정보를 함께 저장해 같은 크기시 더 많은 메모리가 필요합니다.

이렇게 장단점이 있기에 메모리의 변동이 크지 않으면 ArrayDeque가 효율적입니다.

ConcurrentLinkedDeque와 LinkedBlockingQueue 구현체가 제공됩니다. 둘 모두 LinkedList로 구현되어 있으며 특정 상황에서 Thread Safe 합니다. 기본적인 Stack의 연산은 Thread Safe하지만 벌크 연산의 경우 보장하지 못합니다.

두 구현체 사이의 차이점은 BlockingQueue로 큐 크기의 제한을 둘 수 있습니다. 반대로 ConcurrentLinkedDeque는 제한이 없기 때문에 OutOfMemoryError가 발생할 수 있습니다.

Stack이 인터페이스가 아니기 때문에 두 방식 모두 LIFO를 강제하지 않습니다. 이 점을 생각 안하고, 구현체에 대해 고려하지 않으면 문제가 발생합니다.

기본적인 LIFO 라면 push, pop, peek, size 연산을 지원합니다. 이 연산만을 사용한다면 Stack, Deque 모두 같은 결과를 보장하지만 다른 연산은 아닙니다.

먼저 기본 연산 과정을 보기 위해 간단히 1, 2, 3을 순서대로 push해보겠습니다.

Stack은 우리가 쉽게 생각하듯이 배열의 0번부터 순차적으로 쌓여갑니다. pop 연산의 경우에도 마지막 인덱스에 있는 원소를 내보내면 됩니다.

ArrayDeque에서도 같을거라고 예상할 수 있습니다만..

ArrayDeque은 addFirst, removeFirst로 push와 pop을 구현합니다. 메소드 이름처럼 배열의 첫 번째에 넣고 빼는식으로 구현되어 있습니다. pop으로 결과값을 받을 때는 같겠지만 내부 구현은 완전히 반대라는 의미입니다.

Stack과 ArrayDeque는 모두 addAll이라는 함수를 지원합니다. 다른 Collection의 원소를 모두 집어넣어주는 기능을 합니다. 위의 그림에서 4, 5를 가진 Collection을 addAll 했다고 가정하겠습니다.

Stack은 이전처럼 순서대로 쌓이지만 ArrayDeque는 앞이 아닌 뒤에서부터 삽입합니다. 즉 ArrayDeque를 Stack으로써 사용하려면 제공하는 메서드만 사용해야 합니다.

마찬가지로 Stack에서 남은 리스트를 한꺼번에 가져오고 싶을 때가 있습니다. 기본적으로는 pop을 이용해 하나씩 받아와 저장하는 것이 맞습니다. 그걸 지키지 않고 toList 메서드 등을 사용하는 경우 위 그림 순서대로 반환됩니다. 제대로 알지 못하고 쓰는 경우 문제가 발생할 수 있습니다.

이 문제들은 사용자의 무지가 문제일 수도 있지만 Java 언어의 문제이기도 합니다. Stack이 인터페이스였다면 해당하는 메서드만 사용하도록 강제할 수 있으니까요. 이런 문제를 예방하기 위한 방법 중 하나로 Stack 인터페이스를 직접 구현하는 겁니다. 내부 구현은 기존의 Collection을 사용하되 LIFO를 강제하는 인터페이스를 사용하도록 합니다.

public class ArrayLifoStack<E> implements LifoStack<E> {
    private final Deque<E> deque = new ArrayDeque<>();

    @Override
    public void push(E item) {
        deque.addFirst(item);
    }

    @Override
    public E pop() {
        return deque.removeFirst();
    }

    @Override
    public E peek() {
        return deque.peekFirst();
    }

    // forward methods in Collection interface
    // to the deque object

    @Override
    public int size() {
        return deque.size();
    }
...
}

https://www.baeldung.com/java-deque-vs-stack