[자료구조] 선형 자료구조 - 데크 (Deque)

1. 데크 (Deque) 란 무엇인가?

---

데크 (Deque) 란 Double-Ended Queue 의 줄임말로 큐의 양쪽에서 데이터를 삽입하고 삭제할 수 있는 자료구조이다.

Deque의 앞쪽으로 데이터를 넣고 뒤쪽에서 빼면, 큐(Queue)처럼 사용할 수 있고, Deque의 앞쪽에서 데이터를 넣고 앞쪽으로 데이터를 빼면 스택(Stack)처럼 사용할 수 있다. 

데크는 양쪽으로 입출력이 모두 가능하지만, 이 중 한쪽으로만 입력이 가능하도록 설정한 데크를 스크롤(Scroll) 이라고 한다.

한쪽으로만 출력할 수 있도록 설정한 데크는 셸프(Shelf) 라고 한다.

 

 

 

---

 

 

 

2. 데크 (Deque) 사용법

---

(1) Deque 선언

• Java에서의 Deque는 인터페이스로 구현되어 있기 때문에 new Deque() 사용이 불가능하다.
• 이를 구현한 여러 가지 클래스를 이용하여 구현해야 한다. (ArrayDeque, LinkedBlockingDeque, LinkedList 등)

// String 타입의 Deque 생성
Deque<String> deque1 = new ArrayDeque<>();
Deque<String> deque2 = new LinkedBlockingDeque<>();
Deque<String> deque3 = new LinkedList<>();


// 선언과 동시에 초기값 세팅
Deque<Integer> que1 = new ArrayDeque<Integer>(Arrays.asList(1,2,3));

 

 

 

 

 

---

 

 

 

 

 

(2) Deque 데이터 추가

메소드	설명
addFirst()	Deque의 앞쪽에 데이터를 삽입, 용량 초과 시 Exception
offerFirst()	Deque의 앞쪽에 데이터를 삽입 , 용량 초과시 false 리턴
addLast()	Deque의 뒤쪽에 데이터를 삽입, 용량 초과 시 Exception
add()	addLast() 와 동일
offerLast()	Deque의 뒤쪽에 데이터를 삽입, 용량 초과 시 false
offer()	offerLast() 와 동일
push()	addFirst() 와 동일

• add로 시작하는 메소드는 용량 초과 시 예외가 발생하고, offer로 시작하는 메소드는 용량 초과 시 false를 리턴한다는 차이점이 있다.

 

 

 

 

 

 

---

 

 

 

 

 

(3) Deque 데이터 삭제

메소드	설명
removeFirst()	Deque의 제일 앞에 있는 데이터 삭제, 비어있으면 Exception 발생
remove()	removeFirst() 와 동일
poll()	Deque의 제일 앞에 있는 데이터 삭제, 비어있으면 null 리턴
pollFirst()	poll() 과 동일
removeLast()	Deque의 가장 뒤에 있는 데이터 삭제, 비어있으면 Exception 발생
pollLast()	Deque의 가장 뒤에 있는 데이터 삭제, 비어있으면 null 리턴
pop()	removeFirst() 와 동일

• remove로 시작하는 메소드는 Deque가 비어있을 때 예외를 발생시키고, poll로 시작하는 메소드는 Deque가 비어있을 때 null을 리턴하는 차이점이 있다.

 

 

 

 

 

 

---

 

 

 

 

 

(4) Deque 값 출력하기

• Deque의 첫 번째 데이터를 가져오는 방법에는 getFirst(), peekFirst(), peek() 메서드가 있다.
• Deque의 마지막 데이터를 가져오는 방법에는 getLast(), peekLast() 메서드가 있다.
• get으로 시작하는 메소드는 Deque 가 비어있을 때 예외를 발생시키고, peek으로 시작하는 메소드는 Deque가 비어있을 때 null을 리턴한다.

 

 

 

---

 

 

 

 

 

(5) Deque 구현하기

ArrayList를 이용하여 Deque 구현하기

class MyDeque {
    ArrayList list;
    MyDeque() {   // 생성자
        this.list = new ArrayList();
    }
    public boolean isEmpty() {    // Deque가 비어있는지 확인하는 메소드
        if(this.list.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

    public void addFirst(int data) {   // 첫번째 위치에 데이터 추가
        this.list.add(0,data);
    }
    public void addLast(int data) {    // 마지막 위치에 데이터 추가
        this.list.add(data);
    }
    public Integer removeFirst() {    // 첫번째 위치에 있는 데이터 삭제
        if(this.list.isEmpty()) {
            System.out.println("Deque is Empty");
            return null;
        }
        int data = (int)this.list.get(0);
        this.list.remove(0);
        return data;
    }
    public Integer removeLast() {    // 마지막 위치에 있는 데이터 삭제
        if(this.list.isEmpty()) {
            System.out.println("Deque is Empty");
            return null;
        }
        int data = (int)this.list.get(this.list.size()-1);
        this.list.remove(this.list.size()-1);
        return data;
    }
    public void printDeque() {
        System.out.println(this.list);
    }
}

 

 

 

 

배열을 이용하여 Deque 구현하기

// ArrayList 를 이용한 데크 구현
class MyDeque1 {
    int[] arr;
    int front = 0;
    int rear = 0;

    MyDeque1(int size) {
        arr = new int[size + 1];
    }

    public boolean isEmpty() {
        return this.front == this.rear;
    }

    public boolean isFull() {
        return (this.rear + 1) % this.arr.length == this.front;
    }

    public void addFirst(int data) {
        if (this.isFull()) {
            System.out.println("Deque is Full");
            return;
        } else {
            this.arr[this.front] = data;
            this.front = (this.front -1 + this.arr.length) % this.arr.length;
        }
    }

    public void addLast(int data) {
        if (this.isFull()) {
            System.out.println("Deque is Full");
            return;
        } else {
            this.rear = (this.rear +1 ) % this.arr.length;
            this.arr[this.rear] = data;
        }
    }

    public Integer removeFirst() {
        if (this.isEmpty()){
            System.out.println("Deque is Empty");
            return null;
        } else {
            this.front = (this.front +1 ) % this.arr.length;
            return this.arr[this.front];
        }
    }

    public Integer removeLast() {
        if (this.isEmpty()){
            System.out.println("Deque is Empty");
            return null;
        } else {
            int data = this.arr[this.rear];
            this.rear = (this.rear -1 + this.arr.length) % this.arr.length;
            return data;
        }
    }

    public void printDeque() {
        int start = (this.front +1 ) % this.arr.length;
        int end = (this.rear + 1) % this.arr.length;

        for (int i = start; i != end; i = (i+1) % this.arr.length) {
            System.out.println(this.arr[i] + " ");
        }
    }
}