[Data Structure 기초] Deque

Study for Backend/Data Structure

[Data Structure 기초] Deque

지미니박 2024. 2. 23. 22:18

Deque(덱 혹은 데크)

- 양쪽에서 삽입과 삭제가 모두 가능한 자료구조

- 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.

- 큐와 스택을 합친 형태로 생각할 수 있다.

Stack 시간복잡도

삽입 : O(1)
삭제 : O(1)

탐색 : O(1)

연산
addFirst()	맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생
offerFirst()	맨 앞에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴
addLast()	맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 Exception 발생
offerLast()	맨 뒤에서 데이터를 삽입. 용량을 초과하는 경우 false 리턴
removeFirst()	맨 앞에서 데이터를 삭제. 비어있다면 Exception 출력
pollFirst()	맨 앞에서 데이터를 삭제. 비어있다면 null 리턴
removeLast()	맨 뒤에서 데이터를 삭제. 비어있다면 Exception 출력
pollLast()	맨 뒤에서 데이터를 삭제. 비어있다면 null 리턴
remove(Object)	Deque에서 Object를 찾아 삭제
clear()	Deque의 모든 데이터를 삭제

//데크 사용예제
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

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

        //Front 부분
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addFirst(3);
        System.out.println(deque);

        //Rear부분
        deque.addLast(10);
        deque.addLast(20);
        deque.addLast(30);
        System.out.println(deque);

        //Front 부분
        System.out.println(deque.removeFirst());
        System.out.println(deque);

        //Rear부분
        System.out.println(deque.removeLast());
        System.out.println(deque);
    }
}

장점

- 데이터의 삽입과 삭제가 빠르다.
- 크기가 가변적이다.
- 앞, 뒤에서 데이터를 삽입/삭제할 수 있다.
- index로 임의 원소 접근이 가능하다.
- 새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.

단점

- 중간에서의 삽입과 삭제가 어렵다.

- 구현이 어렵다.