[자료구조] 데크

데크 (Dequeue) 란?

 

https://cdn.programiz.com/sites/tutorial2program/files/deque.png

 

- 양쪽에서 삽입과 삭제가 모두 가능한 구조

- Double-ended-queue의 줄임말

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

- 출력 제한 데크 : 한 쪽 출력을 제한한 데크 (Shelf)

 

데크의 연산

● addFirst() : front 부분 입력

● addLast() : last 부분 입력

● removeFirst() / removeLast() : 출력

 

위 메서드 말고도 poll, offer, push, pop 모두 사용 가능하다.

---

1) 데크의 구현

아래와 같이 ArrayDeque를 통해 Deque를 구현할 수 있다. 

 

import java.util.ArrayDeque;
import java.util.Deque;
 
public class Main {
    public static void main(String[] args) {
        Deque deque = new ArrayDeque();
 
        // Front 부분 입력
        deque.addFirst(1);
 
        // Rear 부분 입력
        deque.addLast(10);
        deque.addLast(20);
 
        // Front 부분 출력
        System.out.println(deque.removeFirst());
       
        // Rear 부분 출력
        System.out.println(deque.removeLast());
 
        System.out.println(deque.pollLast());
        System.out.println(deque);
    }
}

class MyDeque {
    ArrayList list;

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

    public boolean isEmpty() {
        if (this.list.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

데크의 경우, 양방향에서 데이터 삽입, 반출이 가능하기 때문에 각 연산에 해당되는 메서드들을 ArrayList 구조에 맞춰 구현해주어야한다.

 

데이터 삽입

> Front 방향으로 데이터를 삽입할 경우, 위치를 지정해주어야하지만 Last라면 그냥 데이터를 추가하면 된다.

 

데이터 삭제 

> 데이터를 삭제할 때는 데크의 empty 여부를 먼저 확인해주어야한다.

> 해당 위치에 해당하는 데이터의 값을 data 변수에 넣는다.

> 실제 list 안에 해당 위치의 데이터를 삭제하고 data를 반환한다.

 

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()) {
    	return null;
    }
    int data = (int)this.list.get(0);
    this.list.remove(0);
    return data;
}

public Integer removeLast() {
	if (this.isEmpty()) {
    	return null;
    }
    int data = (int)this.list.get(this.list.size()-1);
    this.list.remove(this.list.size()-1);
    return data;
}