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처럼 불필요환 동기화를 하지 않기 때문에 성능이 더 우수하다.

[9ga0]

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

Stack과 Deque의 큰 차이점은 출입구의 개수이다. Stack은 접시를 위에 쌓아 사용하는 탑으로 표현한다면, Deque는 양쪽이 모두 뚫린 종이박스와 같다. 이것만 봐도 Deque가 Stack에 비해 제약이 적고 활용도, 속도 측면에서 더 효율적인 자료구조라고 판단 가능하다. 앞에서 넣고 앞에서 빼면 스택처럼, 앞에서 넣고 뒤에서 빼면 큐처럼 Deque로 구현 가능하다.

코드예시)
다음은 ArrayDeque를 스택처럼 쓴 예시이다.

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
	    //Stack<Integer> stack = new Stack<>(); 대신 아래 사용
        Deque<Integer> stack = new ArrayDeque<>();

        stack.push(10);
        stack.push(20);
        stack.push(30);

        System.out.println(stack.pop());  // 30
        System.out.println(stack.pop());  // 20
        System.out.println(stack.pop());  // 10
    }
}

참고)
실무에서도 예시와 같이 ArrayDeque를 사용하는 추세라고 한다.

Q. Deque와 ArrayDeque의 차이점은?

• Deque는 인터페이스이며, "양쪽 끝에서 넣고 뺄 수 있는 자료구조"라는 규칙/기능의 정의이다. 동작으로는 push, pop, addFirst, addLast, removeFirst, removeLast 같은 동작을 약속한다.
• ArrayDeque는 Deque를 구현한 클래스이며, 실제로 메모리 안에서 어떻게 저장할지 정한 구현체이다. 배열 기반이라 빠르고, 스택/큐 둘 다처럼 사용가능하다.

Q. ArrayDeque가 배열 기반이라 빠르다했는데, 배열은 addFirst동작같이 추가,삭제 작업에서 비효율적인 자료구조 아닌가?

• ArrayDeque는 배열의 중간을 제외한 처음과 끝에만 추가/삭제 작업을 수행하며, 배열 전체를 한 칸씩 밀어서 넣는 방식이 아니라, head, tail 인덱스를 옮기며, 새 값을 추가/삭제한다.
• 동작예시)

   배열: [  , A, B, C,  ]
   head -> A
   tail -> 다음 위치
   
   addFirst(X) 하면:
   head를 왼쪽으로 한 칸 이동
   그 자리에 X 저장
  

또다른 이유

Stack은 Vector를 상속받고 있어, Stack의 주원칙인 LIFO에 맞지 않는 메서드를 지원할 가능성이 있다. 또한 Vector는 멀티스레드 환경여부와 상관없이 성능저하를 일으킨다. 그래서 SonarLint와 자바 공식문서에서는  stack 대신 deque을 사용하는 것을 추천한다. 아래 사진과 같이 Deque는 Queue를 상속받으며, Queue는 Collection을 상속받기에 더욱 안정적인 LIFO 형태의 기능을 제공할 수 있다.

다음에 추가 공부)

또한 Vector는 멀티스레드 환경여부와 상관없이 성능저하를 일으킨다.

->
이유2. Vector 메서드는 동기화되어 있어 속도가 느리다
Vector의 소스코드를 보면 메서드에 synchronized 키워드가 걸려있는 것을 볼 수 있다. 동기화여부를 따지느라(이 메서드를 다른 쓰레드가 쓰는지 확인하느라) 일반 메서드보다 속도가  느려질 수 있다.
이유3. Vector는 동기화 자체도 온전하지 않다
Vector의 동기화는 메서드에만 synchornized 키워드로 되어 있어 메서드 자체 실행에는 안전하지만 Vector 인스턴스 객체 자체에는 동기화가 되어 있지 않아 동시다발적으로 객체에 접근해 메서드 호출이 가능하다. 즉, Vector는 온전한 동기화 처리가 안되어 있다. 이말은 안전성을 위해서라도 성능을 위해서라도 Vector를 사용할 합리적인 이유가 없음을 의미한다
https://hellobrocolli.tistory.com/153

[gundoan]

1. Stack 은 Vector 클래스를 상속받아 만들어졌다. 이로인해 본래의 Stack 의 성질을 부수고 , 임의의 위치에 데이터에 접근하거나 조작이 가능하다. → 자바에서 Stack 클래스를 만들었는데, 잘못만들었다. → 코드 재사용을 위해 Vector 를 상속받았음.
2. Stack 을 사용하면 불필요한 동기화 오버헤드가 발생한다. → 왜? → 주요 메서드에 synchronized 키워드가 선언되어있음. → 왜 synchronized 키워드를 추가했을까? → Stack 만들 당시에(옛날에) 멀티스레드 환경을 가정하고 프로그램 안정성을 위해 synchronized 를 박고 봄.

정리

자바에서 옛날에 Stack 을 만들긴 만들었는데, 막상 만들고 보니 허점이 많음. → Deque를 쓰자

[JM-220]

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

• Java 의 Stack은 'Vector 를 상속받아' Java 1.0 에서 구현되었다.

vector 를 상속받은게 문제가 됨.

우선 상속은 isA 관계가 성립할 때 사용하는 객체지향 프로그래밍 기법이다. 근데 엄격한 LIFO 가 지켜져야 하는 stack 은 일반 리스트와는 다른 개념을 가지고 있다. stack 클래스 설계 시, 잘못된 설계방법으로 인해 isA 관계가 아님에도 불구하고 상속으로 구현된 것이다. 그래서 부모인 vector 클래스가 가지고 있는 public 메서드 add, remove 같은 LIFO를 지키지 않는 메서드가 stack 에서 사용가능한 상태가 된다. 따라서 vector 상속이 java 에서 stack 을 사용하지 않는 원인 중 하나가 된다.

또한, vector 의 대부분의 메서드는 synchronized 가 붙어있어서, 동기방식으로만 작동하기 때문에 메서드 단위로 락을 건다. os에서 아사현상과 유사하게, 락을 걸어도, 아사현상이 발생할 수 있기 때문에 외부에서 동기처리를 해주어야 하고, 비동기 환경(멀티스레드) 가 아니더라도 락을 열고 거는 오버헤드가 발생하기 때문에 비효율적인 클래스가 되었다.
반면에, deque은 중간데이터가 오염될 일이 없고, 비동기 방식으로 작동하기 때문에 보다 빠른 연산이 가능하다

[dnnals]

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

먼저 Stack은 후입선출로 마지막에 들어간 데이터가 가장 먼저 나오는 자료구조이고 Deque은 양방향 자료구조로 어디로든 삽입 삭제가 가능한 자료구조입니다. 그런데 Stack 대신 Deque를 사용하는 이유는 Stack은 Vector를 상속받은 자료구조입니다. 객체지향 설계로 보면 상속 관계는 is-A 관계를 가져야 하지만 Stack은 한쪽에서만 조작해야하는 자료구조이지만 Vector가 가진 다른 리스트 조작 매서드도 갖게 되고 이런 점이 Stack의 후입선출의 구조를 깨트리게 됩니다. 그리고 또 Vector와 이를 상속 받은 Stack은 주요 매서드에 synchronized 키워드가 붙어 있기 때문에 단일 스레드 환경에서도 락, 해제의 오버헤드가 존재해 성능적인 부분에서도 뒤쳐집니다. 이렇게 Stack의 객체지향 설계의 오류, 비효율적인 성능의 이유로 Deque를 사용하고 이를 자바 공식 문서에서도 권고됩니다.