[자료구조] 덱(Deque)의 개념과 구현(Java)

 

덱(Deque, Double-Ended Queue)은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말합니다. 이 이름은 Double-Ended Queue에서 나왔습니다. 스택과 큐의 일반적인 특성을 모두 가지고 있어서 스택처럼 LIFO(Last In First Out) 구조, 큐처럼 FIFO(First In First Out) 구조로 사용할 수 있습니다.

 

덱이란?

• 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조를 말함
• 스택과 큐의 일반적인 특성을 모두 가지고 있음
• 덱이란 앞쪽 뒤쪽 모두 삽입 삭제가 많이 이루어지는 작업에 적합
• 인덱스 조회 후 삽입 삭제에는 불리함

덱의 구현

• 원형 배열
• 연결 리스트

이 글에선 원형 배열로만 구현하겠습니다.

 

덱의 자료구조 설계

• add_front: 덱의 앞쪽에 요소를 추가
• add_rear: 덱의 뒤쪽에 요소를 추가.
• delete_front: 덱의 앞쪽에서 요소를 제거하고 반환
• delete_rear: 덱의 뒤쪽에서 요소를 제거하고 반환
• isFull(가득 찼는지 검사)
• isEmpty(비었는지 검사)
• 자료의  rear(초기값 0) , front(초기값 0)

초기값

 

 

 

front = 0

rear = 0

 

add_front

front가 가리키는 인덱스에 원소 추가

추가 후 front = (front-1)% size

add_rear

rear = (rear+1)% size 후

rear 인덱스에 원소 추가

delete_front

front = (front+1)% size

front가 가리키는 인덱스에 원소 추가

delete_rear

rear 인덱스에 원소 추가

rear = (rear-1)% size

원형 배열을 사용하였기 때문에 % size를 하였고,
인덱스 범위를 넘어가도 인덱스 범위를 오버하지 않고 배열의 크기를 사용하기 위해 원형 배열을 사용하였습니다.

isEmpty

rear == front

rear와 front 가 같으면 비었다고 봅니다.

isFull

rear == (front-1)%size ( 또는 (rear+1) %size )

isEmpty연산과 구별을 위해 항상 원형 배열의 가득 찬 경우는 size 보다 1개를 더 적게 사용합니다.

 

수행시간

• 앞 뒤 삽입 삭제: O(1)

 

구현 (Java)

public class Deque <E>{
    private int size;
    private int front;
    private int rear;
    private E[] deque;
    public Deque(int size){
        this.size = size;
        this.front = 0;
        this.rear = 0;
        this.deque = (E[])new Object[this.size];
    }
    public Deque(){
        this(10);
    }
    public boolean isEmpty(){
        return front == rear;
    }
    public boolean isFull(){
        return (rear+1)%size == front;
    }
    public void add_front(E data){
        if (isFull()){
            return;
        }
        else{
            deque[front] = data;
            front = (front - 1 + size) % size;
        }
    }
    public void add_rear(E data){
        if (isFull()){
            return;
        }
        else{
            rear = (rear+1)%size;
            deque[rear] = data;
            return;
        }
    }
    public E delete_front(){
        if (isEmpty()){
            return null;
        }
        else {
            front = (front + 1) % size;
            return deque[front];
        }
    }
    public E delete_rear(){
        if (isEmpty()){
            return null;
        }
        else {
            E temp = deque[rear];
            rear = (rear - 1) % size;
            return temp;
        }
    }
    public void Print(){
        if (isEmpty()){
            System.out.println("없음");
            return;
        }
        else{
            int f = front;
            int r = rear;
            System.out.print("front->");
            while(f!=r){
                f = (f+1)%size;
                System.out.print(deque[f]+ "->");
            }
            System.out.println();
        }
    }
}

 

<이미지 출처>

• Implementation of Deque using circular array - GeeksforGeeks
• Deque Implementation using Circular Array - Simplerize
• [C code] 원형 큐 (Circular Queue) (tistory.com)