[Java]Stack 대신 Deque 사용하기

😮서론

스택이 필요해서 사용하려고 하던 중 소나린트에서 Stack 대신 Deque를 사용하는게 좋다는

안내가 나왔고, 왜 그런지 알아보려 한다.

---

😎본론

스택(Stack)이란?

- 자료구조의 하나로서 후입선출(Last In First Out)를 의미한다.

- 후입선출이란 마지막에 들어온 데이터가 가장 먼저 나가는 방식을 의미한다.

- 자바에서는 Stack을 class 형태로 지원해주고 있다.

스택(Stack)

 

반대개념 큐(Queue)

- Queue의 경우는 선입선출(First In First Out)를 의미한다.

- 선입선출이란 처음에 들어온 데이터를 가장 먼저 내보내는 방식을 의미한다.

- 자바에서 Queue는 인터페이스로 구현이 되어 있어 보통 LinkedList를 사용해서 구현하곤 한다.

큐(Queue)

 

그럼 Deque란?

- 자바 1.6부터 지원하게된 Deque는 'Queue' 인터페이스를 확장하여 만들어진 인터페이스다.

- 양쪽 끝에서 추가, 삭제가 가능한 '양방향 대기열'을 지원함으로써 스택, 큐를 사용할 수 있다.

- 인덱스를 통해 검색, 추가, 삭제가 불가능하다.

---

Stack를 지양하는 이유는?

자바 공식문서에서 해당 문구가 있다.

 

보다 완전하고 일관된 LIFO 스택 작업은 Deque 인터페이스 및 해당 구현에 의해 제공됩니다.

Deque<Integer> stack = new ArrayDeque<Integer>();

그럼 공식문서에서 조차 Stack 클래스 보다 Deque 인터페이스를 사용하도록 권장하는 이유는 뭘까?

 

1. Class vs Interface

Stack == class

public class Stack<E> extends Vector<E> { ... }

스택은 클래스 입니다.

즉, 자체적으로 Stack을 만들어 사용하고 싶으면 Stack.class을 상속해서 사용해야 합니다.

여기서 첫 번째 단점이 나오는데 그 이유는 자바는 다중상속을 지원하지 않기 때문입니다.

 

public class UserActivityStack extends ActivityCollection { ... }

위와 같은 'UserActivityStack'는 이미 'ActivityCollection'의 하위 클래스 입니다.

따라서 Stack.class도 확장할 수 없어 Stack 클래스를 사용하고 싶다면 디자인 구조를 변경하여 사용해야 합니다.

 

Deque == interface

public interface Deque<E> extends Queue<E> { ... }

반면 Deque은 인터페이스 입니다.

인터페이스는 클래스 상속보다 더욱 유연하기 때문에 이미 상속을 받은 클래스라 할 지라도

인터페이스를 구현할 수 있습니다.

 

public class UserActivityStack extends ActivityCollection implements Deque<UserActivity> { ... }

 

이렇기 때문에 인터페이스인 Deque가 클래스인 Stack보다 객체지향관점에서 더욱 많은 유연성을 지원합니다.

 

2. 동기화 메소드 및 성능

Stack 클래스는 위에 코드를 보다시피 Vector.class를 상속하여 사용하고 있다.

'Vector.class'는 쓰레드안전성(Thread Safe)를 위한 전통적인 방법이다.

이로 인해 여러 단점들이 발생한다.

- 모든 작업에서 Lock이 걸려 성능저하를 발생시킬 수 있다.
- 단일 스레드 작업 시 성능저하를 발생시킬 수 있다.

 

반면 Deque은 쓰레드안전성(Thread Safe)을 기본적으로 지원하지 않기 때문에

Stack.class보다 더 나은 성능을 보여줄 수 있다.

 

3. 인덱스 접근

Deque와 다르게 Stack은 인덱스로 접근하여 추가, 삭제, 검색이 가능하다.

이는 LIFO 규칙을 위반하는 상황이다.

public static void main(String[] args) {
  Stack<String> stack = new Stack<>();
  stack.add("첫번째");
  stack.add("두번째");
  stack.add("세번째");

  System.out.println(stack.size()); // 3
  System.out.println(stack.get(1)); // 두번째
  System.out.println(stack.remove(1)); // 두번째
  System.out.println(stack.size()); // 2
  System.out.println(stack.get(1)); // 세번째
}

---

Deque의 LIFO 위반사항

반면 Deque 또한 LIFO를 위반하는 행위가 있다.

Deque는 LIFO를 지원함과 동시에 FIFO를 지원하기 때문에 앞뒤 요소를 삽입, 삭제 할 수 있다.

public static void main(String[] args) {
  Deque<String> stack = new ArrayDeque<>();
  stack.add("첫번째");
  stack.add("두번째");
  stack.add("세번째");

  System.out.println(stack.getLast()); // 세번째
  System.out.println(stack.getFirst()); // 첫번째
  System.out.println(stack.removeFirst()); // 첫번째
  System.out.println(stack.getFirst()); // 두번째
}

😋결론

특별한 상황(쓰레드 안전성)이 아닌 이상 Deque를 사용하여 Stack을 구현하는 것이

성능, 확장성 등 더 많은 면에서 좋은 점을 보여주고 있다.

 

물론, Deque 또한 LIFO를 위반하는 상황이 발생하기 때문에 정말 Stack의 기능만 사용하고 싶다면

따로 확장하여 사용하면 될 것이다.

 

위 특별한 상황이라고 하였지만.. 그 경우도 ConcurrentLinkedDeque, LinkedBlockingDeque 와 같이

Stack을 사용하지 않고, Deque를 사용하는 이미 구현되어 있는 클래스들을 통해 쓰레드 안정성을 얻을 수 있을 것이다.

 

참고사이트

https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/
https://www.baeldung.com/java-deque-vs-stack
https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D
https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)