Blue Peach

덱(Deck)은 큐의 양방향 끝에서 삽입(인큐)와 삭제(디큐)를 하는 자료구조이다.

덱을 이용하여 스택과 큐의 구현이 가능하다는 장점이 있는 반면에, 복잡하고 어렵다는 단점이 있다. 

또다른 장점으로는

1. 크기가 가변적이고, 데이터의 삽입, 삭제가 빠르다.

2. 원하는 요소에 바로 접근이 가능한다.

단점은

1. 데이터 중간의 삽입, 삭제가 용이하지 않다.

이렇게 때문에 덱은 자주 사용하지 되지 않는다. 주로 앞, 뒤에서 삽입과 삭제가 이루어질 때 사용되거나 데이터가 가변적일 때 일반적으로 사용된다.

소스코드를 보며 Deque에 대해 이해 보려고 한다.

(여기서 Empty와 Overflow일 때 발생하는 예외 처리는 생략하고 작성할 것이다. 실제 코딩할 때는 따로 예외 처리를 해야 한다.)

1. Deque 생성자

public Deque(int capacity){
    max = capacity;
    num = rear = front;
    try{
    	que = new int[max];
    }catch(OutOfMemoryError e){
    	max = 0;
    }
}

▶ max를 5로 지정할 것이다.

2. 앞쪽(Front)에서 삽입(Enque)

public int EnqueFront(int x){
    num++;
    if(--front < 0)
        front = max -1;
    que[front] = x;
    return x;
}

▶ 첫번째,  x = 13

▶ 두번째,  x = 20

3. 뒤쪽(Rear)에서 삽입(Enque)

public EnqueRear(int x){
    que[rear++] = x;
    num++;
    if(rear == max)
        rear = 0;
    return x;
}

▶ 첫번째,  x = 6

▶ 두번째,  x = 17

4. Dump(앞쪽에서부터 뒤쪽으로 검색하기)

public void dump(){
    for(int i = 0; i < num; i++)
        System.out.print(que[(i + front) % max]+ ", ");
    System.out.println();
}

현재 front는 3이다. 

i 가 0일 때, que[(0 + 3) % 5]는 que[3]이므로 첫 번째 요소는 20이다.

i가 1일 때, que[(1 + 3) % 5]는 que[4]이므로 두 번째 요소는 13이다.

i가 2일 때, que[(2 + 3) % 5]는 que[0]이므로 세 번째 요소는 6이다.

i가 3일 때, que[(3 + 3) % 5]는 que[1]이므로 네 번째 요소는 17이다.

i가 4일 때, num과 같으므로 for문에서 나온다.

20, 13, 6, 17이 된다.

▷ 큐의 성질대로 먼저 넣은 쪽으로 안으로 들어간다.

5. 앞쪽(Front)에서 삭제(디큐)

public int DequeFront(){
    int x = que[front++];
    num--;
    if(front == max)
        rear = 0;
    return x;
}

5. 뒤쪽(Rear)에서 삭제(Deque)

public int DequeRear(){
    num--;
    if(--rear < 0)
        rear = max - 1;
    return que[rear];
}

6. 자바 컬렉션 프레임웍의 Deque(= 발음 Deck)

java.util 패키지에 소속되어 있고 null 요소를 사용하지 못한다.

◎ 덱 값 추가

1.  addFirst() : 덱의 앞쪽에 데이터 삽입. 용량 초과 시 Exception (=Push)
2. offerFirst() : 덱의 앞쪽에 데이터 삽입 후 true, 용량 초과 시 false
3. addLast() : 덱의 뒤쪽에 데이터 용량 삽입. 용량 초과 시 Exception (=add)
4. offerLast() : 덱의 뒤쪽에 데이터 삽입 후 true, 용량 초과 시 false (=offer)

◎ 덱 값 제거

1. removeFirst() : 덱의 앞쪽 데이터 하나를 삭제. 비어 있으면 Exception (=pop, remove)
2. pollFirst() : 덱의 앞쪽 데이터 하나를 삭제, 비어있으면 Null (=poll)
3. removeLast() : 덱의 뒤쪽 데이터 하나를 삭제. 비어 있으면 Exception
4. pollLast() : 덱의 뒤쪽 데이터 하나를 삭제, 비어있으면 Null