[학습 로그] Stack vs Deque

Prolog - Stack vs Deque

우아한테크코스 학습로그 저장소

저번 블랙잭 미션을 하면서 카드를 저장할 자료구조를 고민하다가 Stack보다는 Deque이 좋다는 토리의 조언을 듣고, Stack과 Deque에 대해 알아보았습니다.

Stack과 Deque 차이점

Stack

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

• Last In First Out 방식
• List 컬렉션의 Vector를 상속받은 클래스

Deque

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

• 양방향 입출력이 가능한 방식
• Queue 인터페이스를 확장한 인터페이스

---

Stack을 지양하라?

그렇다면 Stack보다 Deque을 사용해야 하는 이유는 뭘까?

 

자바 공식 문서에서도 Stack보다는 Deque을 사용해야 한다고 말하고 있다.

📎 Stack 관련 자바 공식 문서

Stack (Java SE 11 & JDK 11 )

더 완전하고 일관된 LIFO 스택 작업은 Deque 인터페이스와 그 구현체에 의해 제공되며, 이 클래스보다 우선적으로 사용되어야 한다.

성능

여러 차이점들이 있겠지만, 그 중에서도 우리가 느끼기에 중요한 차이점은 성능일 것이다.

 

Stack은 Vector를 상속받았기 때문에 Vector와 마찬가지로 Thread-Safe하다는 특징을 가지고 있다.

Thread Safe하다는 것은 멀티 스레드 환경에서 동기화가 잘 되어있다는 뜻인데, 동기화와 성능 간에는 Trade-Off가 발생하기 때문에 마냥 좋은 것만은 아니다.
동기화를 위해 모든 작업에 Lock이 걸리기 때문에 성능이 떨어진다.

또한, 우리는 주로 단일 스레드 환경에서 작업하는데 이럴 경우 동기화의 이점도 없고, 성능도 좋지 않다.

 

반면에 Deque의 경우에는 기본적으로 Thread-Safe하지 않기 때문에 Stack에 비해 성능이 좋다고 볼 수 있다.

---

그럼 무조건 Stack보다 Deque..?

블랙잭 미션에 대한 코드 리뷰를 받으면서, 이 부분이 너무 궁금해서 리뷰어에게도 질문했고 다음과 같은 답변을 받았다.

다만 Stack 구조는 개발자들이 대부분 잘 알고있는 구조인데 비해 Deque는 조금 낯설 수도 있겠다는 생각이 들어요.
(물론 구성 메소드를 보니, 이해를 못해서 실패할 가능성은 낮아보이지만요)
페어와 시간 날 때 이야기 나눠보고, 가독성과 효율 중 망고는 어느 쪽에 더 가치를 두는지, 
Stack과 Deque는 어떤 차이가 있는지 고민해보면 큰 자산이 될 것으로 생각됩니다. 💯

당연히 성능이 좋으면 무조건 좋은거야! 라고 생각했었는데, 충분히 고민해볼만한 내용이었다.
많은 사람에게 서비스하는 경우 성능도 중요하지만, 그만큼 많은 사람들이 작업해야 하기 때문에 가독성 또한 중요하게 여겨진다.
가독성이 아니더라도 다른 코드들과의 통일성 또한 고려해야 할 것이다.

 

그렇기 때문에 무작정 Stack보다는 Deque! 이라고 선택하기보다는 자신이 처한 상황에 맞게 Trade-Off를 비교해가며 선택하는 것이 올바른 방향이라고 생각한다.

---

Deque 구현체

그렇다면 Deque의 구현체는 어떤 것들이 있을까?

 

주로 ArrayDeque혹은 LinkedList를 사용해 구현한다.

ArrayDeque

• Deque 인터페이스의 구현체
• 양쪽 끝에 값 추가, 제거에 효율적
• null 추가 불가능

LinkedList

• List 의 구현체
• 반복 중 현재 요소를 제거하는 것에 효율적
• null 추가 가능
• ArrayDeque 보다 더 많은 메모리를 소모

---

Reference

https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/
https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Stack.html