[자료구조][Java] 데크(Deque)

 

[ 목차 ]

---

📢 데크

• 양쪽에서 삽입과 삭제가 모두 가능한 자료구조
• Deque : Doubly-ended Queue
• Stack + Queue 한 상태

---

📢 데크의 기본 구조

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

💻 입력제한 데크(Scroll)

• 한 쪽의 입력을 제한한 데크

💻 출력제한 데크(shelf)

• 한 쪽의 출력을 제한한 데크

💻 그림 예시

---

📢 Deque 사용 예시

💻 Deque(기본)

public class Main {
    public static void main(String[] args) {

        //기본 Deque를 이용한 예제
        Deque deque = new ArrayDeque();

        // Front 부분 입력
        deque.addFirst(1);
        deque.addFirst(2);
        System.out.println(deque);  //[2, 1]

        // Rear 부분 입력
        deque.addLast(10);
        deque.addLast(20);
        System.out.println(deque);  //[2, 1, 10, 20]

        // Front 부분 출력
        System.out.println(deque.removeFirst());  /2
        System.out.println(deque);  //[1, 10, 20, 30]

        // Rear 부분 출력
        System.out.println(deque.removeLast());  //20
        System.out.println(deque);  //[2, 1, 10]

        //비어 있는 상황이라면
        System.out.println(deque.pollLast());   //null
        System.out.println(deque.remove());     //Exception Error
    }
}

💻 Deque (ArrayList 사용)

// Practice1
// ArrayList 를 이용한 데크 구현

import java.util.ArrayList;

class MyDeque1 {
    ArrayList list;

    MyDeque1() {
        this.list = new ArrayList();
    }

    public boolean isEmpty() {
        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.isEmpty()){
            System.out.println("Deque is empty");
            return null;
        }

        //[this.list.get(0)] : 맨 앞 인덱스
        int data = (int)this.list.get(0);
        this.list.remove(0);
        return data;
    }

    public Integer removeLast() {
        if(this.isEmpty()){
            System.out.println("Deque is empty");
            return null;
        }

        //[this.list.size()-1] : 가장 끝 인덱스
        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);
    }

}

public class Main {
    public static void main(String[] args) {
        // Test code
        MyDeque1 myDeque = new MyDeque1();
        // Front 부분 입력
        myDeque.addFirst(1);
        myDeque.addFirst(2);
        myDeque.printDeque();    // 2 1

        // Rear 부분 입력
        myDeque.addLast(10);
        myDeque.addLast(20);
        myDeque.printDeque();    // 2 1 10 20

        // Front 부분 출력
        System.out.println(myDeque.removeFirst());  // 2
        myDeque.printDeque();    // 1 10 20

        // Rear 부분 출력
        System.out.println(myDeque.removeLast());   // 20
        myDeque.printDeque();    // 1 10

        System.out.println(myDeque.removeLast());   // 10
        System.out.println(myDeque.removeLast());   // 1
        myDeque.printDeque();
    }
}

💻 Deque (배열 사용)

// Practice2
// 배열을 이용한 기본 데크 직접 구현

class MyDeque2 {
    int[] arr;
    int front = 0;
    int rear = 0;

    MyDeque2(int size) {
        this.arr = new int[size + 1];
    }

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

    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[front] = data;
        
        //[this.arr.length] 를 더하는 이유는 앞이 막히면 뒤로 가야하기 때문에 배열 갯수에 맞게 값을 조정
        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;
        }
        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;
    }

    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();
    }

}

public class Main {
    public static void main(String[] args) {
        // Test code
        MyDeque2 myDeque = new MyDeque2(5);
        // Front 부분 입력
        myDeque.addFirst(1);
        myDeque.addFirst(2);
        myDeque.printDeque();   // 2 1

        // Rear 부분 입력
        myDeque.addLast(10);
        myDeque.addLast(20);    // Deque is full!
        myDeque.printDeque();        // 2 1 10 20

        // Front 부분 출력
        System.out.println(myDeque.removeFirst());  // 2
        myDeque.printDeque();   // 1 10 20

        // Rear 부분 출력
        System.out.println(myDeque.removeLast());   // 20
        myDeque.printDeque();    // 1 10

        System.out.println(myDeque.removeLast());   // 10
        System.out.println(myDeque.removeLast());   // 1
        System.out.println(myDeque.removeLast());   // Deque is empty!
    }
}

---