[Java] Stack 대신 Deque

Deque

자바에서 Deque(Double Ended Queue) 는 Queue 인터페이스를 상속받은 인터페이스이며, Queue 와 Stack 의 메서드를 모두 제공한다.

자료의 입출력을 양 끝에서 할 수 있다. 인덱스로 요소에 액세스, 삽입, 제거를 허용하지 않는다.

삽입

삭제

조회

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());
    }
}
// [출력 결과]
// 세 번째 요소
// 첫 번째 요소

종류

Deque<Integer> queue = new ArrayDeque<>();
Deque<Integer> queue2 = new LinkedList<>();

일반적으로 Deque의 구현체는 ArrayDeque 와 LinkedList 가 있다.

ArrayDeque

• Deque 인터페이스의 구현체이며 크기를 재설정 할 수 있다.

• null 요소 추가 불가

• 양쪽 끝에서 추가, 제거하는 것이 효율적이다

• 메모리 소모량이 적을 때는 iterate 효율이 좋은 ArrayDeque 를 사용하는 것이 좋다

LinkedList

• List 의 구현체다.

• null 요소를 추가할 수 있다

• 반복중에 현재 요소를 제거하는 것이 효율적이다

• ArrayDeque 보다 많은 메모리를 소모한다

• 스택의 사이즈가 커지거나 심한 변동이 예상될 때는 즉각적인 메모리 공간 확보를 위해 LinkedList 를 사용한다.

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

그럼 Deque 만 써도 되는거 아님?

1. 문제 상황에 따른 선택

스택과 큐가 각자 잘 맞는 상황이 있습니다. 예를 들어, 괄호 짝 맞추기 문제는 스택을, 프린터 큐 문제는 큐를 사용하는 것이 더 자연스럽습니다. 덱을 사용하면 구현이 복잡해질 수 있습니다.

2. 가독성과 유지 보수

스택과 큐는 각각의 역할이 명확하므로, 코드의 가독성을 높이고 유지 보수를 용이하게 합니다. 덱을 사용하면 코드가 복잡해지고 오류 발생 가능성이 높아질 수 있습니다.

3. 효율성

스택과 큐는 각각의 목적에 맞게 최적화된 연산을 제공합니다. 반면에 덱은 양쪽 끝에서의 연산을 모두 지원하므로, 특정 상황에서는 스택이나 큐보다 덜 효율적일 수 있습니다.

출처 : GPT-4 답변

---

정리

Deque(덱 또는 데크) 란 쉽게 말해 양방향 큐이다.
Stack 과 Queue 대신 Deque 를 사용할 수 있다.

LinkedList 나 ArrayDeque 로 사용될 수 있으며, ArrayDeque 로 사용 시 Stack 으로 사용하면 Stack 보다 빠르고, Queue 로 사용하면 LinkedList 보다 빠를 수 있다.

출처

https://soft.plusblog.co.kr/24
https://ttl-blog.tistory.com/170
https://velog.io/@may_yun/JAVA-Stack-대체-Collection-Deque