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

---

(1) 데크(Deque): 양쪽에서 삽입과 삭제가 가능한 자료구조

• Deque: Doubly-ended Queue
• Stack과 Queue를 합친 형태

---

(2) 데크 기본 구조

• 데크는 양방향에서 삽입/삭제가 가능한 구조
• 일부 기능을 제한하여 용도에 맞게 변형 가능

---

(3) 입력 제한한 데크(Scroll): 한 쪽의 입력을 제한한 데크

---

(4) 출력 제한한 데크(Shelf): 한 족의 출력을 제한한 데크

---

(5) JAVA 코드로 학습하기

---

(1) JAVA에서 제공하는 java.util.Deque 사용하기

//선형자료구조-데크
public class Main {
    public static void main(String[] args){
        Deque deque = new ArrayDeque();  //ArrayDeque가 인터페이스 Deque를 구현하고 있음 

        //Front 입력
        deque.addFirst(1);  // 앞에서부터 추가
        deque.addFirst(2);
        deque.addFirst(3);
        System.out.println(deque);
        line();

        //Rear 입력
        deque.addLast(10);  // 뒤에서부터 추가
        deque.addLast(20);
        deque.addLast(30);
        System.out.println(deque);
        line();

        //Front 출력
        System.out.println(deque.removeFirst());  // 첫 번째 요소를 꺼내고 지움
        System.out.println(deque);
        line();

        //Rear 출력
        System.out.println(deque.removeLast());  // 마지막 요소를 꺼내고 지움
        System.out.println(deque);
        line();

        System.out.println(deque.removeLast());
        System.out.println(deque.removeLast());
        System.out.println(deque.removeLast());
        System.out.println(deque.removeLast());
        System.out.println(deque);
        line();

        System.out.println(deque.pollLast());  // 데이터가 없는 경우, poll은 null 출력
        System.out.println(deque.removeLast());  // 데이터가 없는 경우, remove는 java.util.NoSuchElementException 에러 출력
    }
}

---

(2) ArrayList를 이용한 구현

//ArrayList를 이용한 구현
class MyDeque1{
    ArrayList list;  //저장할 리스트 선언

    MyDeque1(){
        list = new ArrayList();  //리스트 저장공간 생성
    }

    // 리스트가 비어있는 경우를 확인하는 함수
    public boolean isEmpty(){
        return list.isEmpty();
    }

    // 리스트의 앞부분에 data를 저장하는 함수
    public void addFirst(int data){
        this.list.add(0, data);  //index 앞부분 0에 데이터 저장
    }

    // 리스트의 마지막 부분에 data를 저장하는 함수
    public void addLast(int data){
        this.list.add(data);  // 마지막 부분에 데이터를 저장
    }

    // 앞 부분의 데이터를 가져오면서 삭제
    public Integer removeFirst(){
        if(this.isEmpty()){  //만약 리스트가 비어져있는 경우
            System.out.println("Deque is empty");
            return null;
        }
        
        int data = (int) this.list.get(0);  //제네릭을 사용하지 않아서 (int)로 형변환을 해줘야함
        this.list.remove(0);  // 앞부분 인덱스 0을 지움
        return data;
    }

    // 마지막 데이터를 가져오면서 삭제하는 함수
    public Integer removeLast(){
        if(this.isEmpty()){  //리스트가 비어져있는 경우
            System.out.println("Deque is empty");
            return null;
        }

        int data = (int) this.list.get(this.list.size()-1);  //리스트의 사이즈-1번째의 인덱스의 데이터를 가져옴
        this.list.remove(this.list.size()-1);  //마지막 원소 삭제
        return data;
    }

    // Deque의 모든 원소 출력하는 함수
    public void printDeque(){
        System.out.println(list);
    }
}

---

(3) Array를 이용한 Deque 구현

//Array를 이용한 구현(원형)
class MyDeque2{
    int[] arr;  //저장 공간 생성
    int front = 0;  //앞부분 인덱스를 가리키는 변수
    int rear = 0;  //뒷부분 인덱스를 가리키는 변수

    MyDeque2(int size){
        arr = new int[size+1]; //원형으로 관리하기 위해 원래사이즈+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;
        }
        
        this.arr[this.front] = data;  //앞 부분의 데이터 넣음
        this.front = (this.front-1 + this.arr.length) % this.arr.length;  //기존의 앞부분 인덱스를 앞으로 당김
        //나눗셈은 front가 앞에 0을 가리키고 있을 때, 원형으로 다음을 가리키기 위한 계산
    }

    // 마지막 위치에 데이터를 추가하는 함수
    public void addLast(int data){
        if(this.isFull()){  //데이터가 꽉차있는 경우
            System.out.println("Deque is full");
            return;
        }
        
        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;
        }

        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;
        }
        
        int data = this.arr[this.rear];  //현재 마지막 인덱스 위치의 데이터를 가져옴 
        this.rear = (this.rear-1 + this.arr.length) % this.arr.length;  //뒷부분의 인덱스를 앞으로 당김
        return data;
    }

    // Deque의 모든 원소를 출력하는 함수
    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.print(this.arr[i]+ " ");
        }
        System.out.println();
    }
}

• 원형으로 관리하는 방법은 큐(Queue)의 자료구조에서 (3) Array를 이용한 큐 구현(원형 큐)에 설명되어 있음
• 데이터를 추가하는 경우에는 배열(공간)이 가득 차있는지 확인하는 과정이
• 데이터를 삭제하며 출력하는 경우에는 배열(공간)이 비어져있는지 확인하는 과정이 공통적으로 필요함