Stack 대신 Deque를 사용하는 이유

[sangjun121]

📆 일자: 26년 7월 21일(화)

🤔 아직 주제가 어렵게 느껴진다면, 기본 질문만 답변하는 것을 목표로 진행해주세요. 시간 여유가 된다면 심화 질문을 추가 학습하는 것을 권장합니다. 추후 질문은 다음 디스커션 이후 다시 다뤄볼 질문입니다. 오늘 작성하지 않아도 괜찮습니다. (25기 이상은 심화 질문까지 다뤄보는 것을 권장합니다.)

오늘의 질문

자바의 자료구조에서 Stack 대신 Deque를 사용하는 이유를 설명하세요.

[k9425mino]

자바의 자료구조에서 Stack 대신 Deque를 사용하는 이유를 설명하세요.

자바 공식 문서에서는 Stack 클래스에 대해서, Stack 클래스를 사용하기 보다는 Deque 인터페이스와 그 구현체를 사용하라고 말한다.

Queue는 FIFO(선입선출)의 특징을 가지고 있는 자료구조이다. 자바에서는 java.util.Queue<E> 인터페이스를 통해 해당 자료형을 제공한다.

Queue<Integer> queue = new LinkedList<>();
queue.offer(1);

Queue는 보통 구현체로 LinkedList를 사용한다.

Stack은 LIFO(후입선출)의 특징을 가지고 있는 자료구조이다. 자바에서는 java.util.Stack<E> 클래스를 통해 해당 자료형을 제공한다. 이는 Vector 클래스를 상속받아 구현되어 있다.

Stack<Integer> stack = new Stack<>();

Stack은 그 자체로 구현체이므로 다음과 같이 사용한다.

Deque는 Double Ended Queue의 약자로, 흔히 양방향 큐라고 불리는 것이다. 자바에서는 java.util.Deque<E> 인터페이스를 통해 해당 자료형을 제공한다. 이는 Queue 인터페이스를 상속받아 구현되어있다.
양방향으로 데이터를 삽입하고 삭제하는 기능을 제공한다. Queue 인터페이스를 상속한 것이므로 Queue의 메서드를 모두 제공한다. Deque는 Stack의 메서드 또한 모두 제공한다.
Deque의 구현체인 ArrayDeque 클래스는 Stack의 메서드를 다음과 같이 제공하고 있다. push, pop, peek 메서드와 같이 Stack의 메서드를 사용하면 이것에 대응되는 Deque의 메서드를 호출하도록 위힘하는 것이다. 이는 Queue의 메서드에 대해서도 마찬가지로 적용되어 있다.
결론적으로 Deque는 양방향 큐로써 접근하고 사용할 수도 있지만, Stack이나 Queue처럼 사용할 수도 있다. 이는 곧 기존의 Stack과 Queue를 사용하던 코드를 Deque로 변경하더라도 문제가 없다는 것을 의미한다.

Stack 클래스는 앞서 말했듯이 Vector 클래스를 상속하여 구현되어 있다. Vector 클래스는 List를 구현한 클래스로 자바 1.0부터 제공되어 왔다. 하지만 성능 상의 문제로 사용이 권장되지 않고 있다. 결과적으로 Stack 클래스도 사용이 권장되지 않게 된 것이다.
Vector는 동기화된 메서드로 구성되어 있어 멀티 쓰레드 환경에서 안전하다. 하지만 단일 쓰레드 환경에서도 동기화 처리에 대한 오버헤드가 발생하여 성능 저하가 발생할 수 있다. 따라서 단일 쓰레드 환경에서는 ArrayList를 사용하는 것이 성능상 유리하다.
자바 1.5 이후부터는 Collections.synchronizedList가 제공되어 ArrayList 클래스를 사용하더라도 동기화 처리를 할 수 있다. 따라서 쓰레드 환경에 무관하게 ArrayList를 사용하는 것이 좋다. 실제로 오늘날 자바를 사용하는 대부분의 프로젝트에서는 Vector를 사용하지 않고 ArrayList를 사용하고 있다.

Stack과 ArrayDeque의 관계는 Vector와 ArrayList의 관계와 매우 유사하다. 다시 말해 Stack을 사용하면 안되는 이유는 Vector를 사용하면 안되는 이유와 동일하다고 볼 수 있다.
하지만 Deque는 별도의 동기화 처리를 위한 메서드가 없다. 이를테면 Collections.synchronizedDeque와 같은 메서드가 제공되지 않는다는 것이다.

class SyncStack<E> {
   private final Deque<E> stack = new ArrayDeque<>();

   public synchroncized void push(E e) {
      stack.push(e);
   }
}

이러한 문제는 외부 동기화를 통해 해결할 수 있다. 위 예시와 같이 동기화 처리를 외부에서 해주면 Deque를 멀티 쓰레드 환경에서도 안전하게 사용할 수 있다.

요약

• Stack은 Vector를 상속받아 구현되어 있다.
• Vector는 단일 쓰레드 환경에서의 성능 저하로 사용이 권장되지 않는다.
• 따라서 Vector를 상속한 Stack 또한 사용하지 않는 것이 좋다.
• ArrayDeque는 Deque의 구현체이며 Stack과 Queue의 메서드를 모두 지원한다.
• Stack 대신 ArrayDeque를 사용하면 성능 향상을 기대할 수 있다.
• 쓰레드 안전한 ArrayDeque를 사용하기를 원한다면 외부 동기화를 사용한다.

[eunji719]

자바의 자료구조에서 Stack 대신 Deque를 사용하는 이유를 설명하세요.

stack클래스는 오래된 클래스로 설계되어 성능과 설계 측면에서 비효율적이라고 한다. stack은 vector클래스를 상속받아 모든 메서드가 동기화 되어 있다. 혼자 프로그램을 사용하는 단일 스레드 환경에서까지 동기화가 일어나면 불필요한 성능 저하가 발생할 수 있기 때문에 보통 deque를 사용한다. ArrayDeque는 스택과 큐 기능을 모두 지원하며, stack처럼 불필요환 동기화를 하지 않기 때문에 성능이 더 우수하다.