Stack vs Deque

Stack

후입 선출(LIFO): 나중에 들어간 값이 먼저 나오는 자료구조를 구현한 자바 클래스

• List Collection의 Vector를 상속 받은 스택 메모리 클래스 제공
• 배열 기반 데이터 구조
• 인덱스로 요소에 접근할 수 있다

Stack의 다음과 같은 단점 때문에 Stack 대신 Deque의 구현체인 ArrayDeque 사용을 제안하고 있다 Java에서 vetor는 특정 상황에서 효율적이지 않기 때문에 Thread Safe 않다고 할 수 있다.

Vector를 상속받은 Stack은 다음과 같은 단점이 존재

• 초기 용량 설정을 지원하지 않는다
• 모든 작업 Lock이 사용된다
  • 단일 스레드 실행 성능이 저하 될 수 있다
  • 단순한 Iterator의 탐색 작업에서도 get() 메서드 실행시 매번 Lock이 발생하게 되므로 오버헤드가 커진다.
• Stack은 vector 상속 받았기 때문에 다중 상속을 지원하지 않는다

Queue

선입 선출(FIFO): 먼저 들어간 값이 먼저 나오는 자료구조를 구현한 자바 인터페이스

• 인덱스 요소로 요소에 접근이 불가능하다

Deque

자료의 입출력을 양 끝에서 할 수 있는 자바 인터페이스

• ⭐️Deque 인터페이스는 필요한 모든 스택 작업을 제공한다.
• Queue 인터페이스를 확장한 인터페이스
• 인덱스로 요소에 액세스, 삽입, 제거를 허용하지 않는다
• 작업에 Lock을 사용하지 않기 때문에 단일 스레드에서도 문제가 발생하지 않는다
  다만 다중 스레드 실행의 경우 문제가 될 수 있지만 ArrayDeque에 대한 동기화 데코레이터를 구현할 수 있다
  • 데코레이터는 메서드가 실행되기 전에 먼저 실행되는 메서드를 말한다
• Stack 클래스의 초기 용량 설정 부족 문제를 해결
• ArrayDeque는 생성자로 배열의 초기 크기를 지정할 수 있고 용량이 초과하면 기존 용량의 2배로 늘려주거나 줄여주는 로직이 존재한다

public class Application {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("첫 번째 요소"); // "첫 번째 요소"
        deque.add("두 번째 요소"); // "첫 번째 요소", "두 번째 요소"
        deque.push("세 번째 요소"); // "세 번째 요소", "첫 번째 요소", "두 번째 요소"
        System.out.println(deque.pop());
        System.out.println(deque.pop());
    }
}
// 실행 결과
// > Task :Application.main()
// 세 번째 요소
// 첫 번째 요소

Deque의 종류

일반적으로 Deque의 구현체는 ArrayDeque와 LinkedList가 있다
둘의 차이점으로는 아래와 같다

• ArrayDeque

  • Deque 인터페이스의 구현체이며 크기를 재설정 할 수 있다.
  • null 요소 추가 불가
  • 양쪽 끝에서 추가, 제거하는 것이 효율적이다
  • 메모리 소모량이 적을 때는 iterate 효율이 좋은 ArrayDeque를 사용하는 것이 좋다

• LinkedList

  • List의 구현체
  • null 요소를 추가할 수 있다
  • 반복중에 현재 요소를 제거하는 것이 효율적이다
  • ArrayDeque 보다 많은 메모리를 소모한다
  • 스택의 사이즈가 커지거나 심한 변동이 예상될 때는 즉각적인 메모리 공간 확보를 위해 LinkedList 사용

대부분의 상황에서는 Deque를 사용할 때 ArrayDeque를 사용한다

---

참고

• https://tecoble.techcourse.co.kr/post/2021-05-10-stack-vs-deque/