Deque(Double-Ended Queue)

Kkd·2024년 12월 28일

매일메일 개념정리

목록 보기

47/93

Deque (Double-Ended Queue)

Deque는 "Double-Ended Queue"의 약자로, 양쪽 끝에서 데이터를 삽입(enqueue)하거나 삭제(dequeue)할 수 있는 선형 자료구조입니다. 즉, 큐와 스택의 성질을 모두 가지고 있으며, 앞(front)과 뒤(rear) 양쪽에서 작업을 처리할 수 있는 유연성을 제공합니다.

Deque의 특징

양방향 작업 가능:
- 앞(front)에서 삽입과 삭제 가능.
- 뒤(rear)에서 삽입과 삭제 가능.
유연성:
- 큐처럼 선입선출(FIFO) 방식으로 동작 가능.
- 스택처럼 후입선출(LIFO) 방식으로 동작 가능.
순차적 데이터 처리:
- 양쪽 끝에서 작업하므로 다양한 알고리즘에서 사용 가능.

Deque의 주요 연산

삽입:
- addFirst(E element): 앞에 데이터 삽입.
- addLast(E element): 뒤에 데이터 삽입.
삭제:
- removeFirst(): 앞에서 데이터 제거 및 반환.
- removeLast(): 뒤에서 데이터 제거 및 반환.
조회:
- getFirst(): 앞의 데이터를 제거하지 않고 반환.
- getLast(): 뒤의 데이터를 제거하지 않고 반환.
기타:
- isEmpty(): Deque가 비어 있는지 확인.
- size(): Deque의 크기 반환.

Deque의 구현 방법

Deque는 주로 배열(Array) 또는 연결 리스트(Linked List)를 기반으로 구현됩니다. Java에서는 ArrayDeque와 LinkedList로 제공됩니다.

Java에서 Deque 사용 예제

1. Deque 인터페이스와 ArrayDeque 클래스

import java.util.Deque;
import java.util.ArrayDeque;

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

        // 데이터 삽입
        deque.addFirst(10); // 앞에 삽입
        deque.addLast(20);  // 뒤에 삽입
        deque.addLast(30);

        System.out.println(deque); // 출력: [10, 20, 30]

        // 데이터 조회
        System.out.println("앞 데이터: " + deque.getFirst()); // 출력: 앞 데이터: 10
        System.out.println("뒤 데이터: " + deque.getLast());  // 출력: 뒤 데이터: 30

        // 데이터 삭제
        deque.removeFirst(); // 앞 데이터 제거
        System.out.println(deque); // 출력: [20, 30]
        deque.removeLast(); // 뒤 데이터 제거
        System.out.println(deque); // 출력: [20]
    }
}

2. Deque를 이용한 스택 동작

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeAsStack {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

        // 스택 동작
        stack.push(10); // 데이터 삽입
        stack.push(20);
        stack.push(30);

        System.out.println(stack); // 출력: [30, 20, 10]

        // 데이터 제거 및 반환
        System.out.println(stack.pop()); // 출력: 30
        System.out.println(stack);       // 출력: [20, 10]
    }
}

3. Deque를 이용한 큐 동작

import java.util.Deque;
import java.util.ArrayDeque;

public class DequeAsQueue {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();

        // 큐 동작
        queue.addLast(10); // 뒤에 데이터 삽입
        queue.addLast(20);
        queue.addLast(30);

        System.out.println(queue); // 출력: [10, 20, 30]

        // 데이터 제거 및 반환
        System.out.println(queue.removeFirst()); // 출력: 10
        System.out.println(queue);              // 출력: [20, 30]
    }
}