[Data Structure 기초] Deque

 

 

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로 임의 원소 접근이 가능하다.
-  새로운 원소 삽입 시에, 메모리를 재할당하고 복사하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입한다.

 

단점

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

- 구현이 어렵다.

 

 

 

관련link

https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Deque

[자료구조] Deque(덱,데크)

 

https://tech-monster.tistory.com/159

Deque, LinkedList 와 ArrayDeque