[자료구조] Deque

자료구조

---

Deque

Deque (Double_Ended Queue)은 양쪽 끝에서 삽입과 삭제가 가능한 자료구조.

Deque은 Queue처럼 한쪽 끝에서 삽입하고 다른 쪽 끝에서 삭제하는 것이 아니라, 양쪽에서 끝에서 자유롭게 삽입과 삭제가 가능.
이러한 특성으로 덱은 Stack과 Queue의 특성을 모두 가지고 있음.

package deque;

import java.util.Deque;
import java.util.LinkedList;

public class Deque01 {
    public static void main(String[] args) {
        Deque<Integer> deque = new LinkedList<>();

        // 요소 추가
        deque.addFirst(1);  // 앞쪽에 1 추가
        deque.addLast(10);  // 뒤쪽에 10 추가

        System.out.println(" >>>>> " + deque);

        // 앞쪽과 뒤쪽에서 요소 가져오기
        System.out.println(" F >>>>> " + deque.getFirst());
        System.out.println(" L >>>>> " + deque.getLast());

        // 앞쪽과 뒤쪽에서 요소 제거
        deque.removeFirst();
        deque.removeLast();

        System.out.println(" >>>>> " + deque);
    }
}

위 코드에서 처럼 addFirst와 addLast를 통해서 요소의 앞과 뒤에 데이터를 넣을수 있음.

덱의 주요 연산

addFirst(e) : 덱의 앞쪽에 요소를 추가

addLast(e) : 덱의 뒤쪽에 요소를 추가

removeFirst() : 덱의 앞쪽에서 요소를 제거하고 반환

removeLast() : 덱의 뒤쪽에서 요소를 제거하고 반환

getFirst() : 덱의 앞쪽 요소를 반환 (제거하지 않음)

getLast() : 덱의 뒷쪽 요소를 반환 (제거하지 않음)

isEmpty() : 덱이 비어있는지 여부를 확인

---

Deque 구현 

>  ArrayDeque : 배열을 기반으로한 덱으로, 고정 크기 없이 동적으로 크기가 조정됨. 일반적으로 스택과 큐로 사용하기 적합하며 빠른 성능이 특징

> LinkedList : 연결 리스트를 기반으로 한 덱, 삽입과 삭제가 빠르지만 메모리 사용량이 높음.

활용

> 회문 검사

> 슬라이딩 윈도우 문제