덱

덱

덱(deque: double-ended queue)은 front, rear에서 삽입과 삭제가 전부 가능한 자료구조이다.

---

덱 ADT

데이터
element E

메소드	내용
addFirst(E e)	덱의 맨 앞에 데이터를 추가한다.
addLast(E e)	덱의 맨 뒤에 데이터를 추가한다.
pollFirst()	덱의 맨 앞의 데이터를 제거하고 반환한다.
pollLast()	덱의 맨 뒤의 데이터를 제거하고 반환한다.
peekFirst()	덱의 맨 앞의 데이터를 반환한다.
peekLast()	덱의 맨 뒤의 데이터를 반환한다.
size()	덱의 크기를 반환한다.
isEmpty()	덱이 비어있는지 검사한다.

---

덱의 삽입 연산

덱의 맨 앞에 데이터를 추가하는 연산이다.

덱의 맨 뒤에 데이터를 추가하는 연산이다.

---

덱의 삭제 연산

덱의 맨 앞의 데이터를 삭제하는 연산이다.

덱의 맨 뒤의 데이터를 삭제하는 연산이다.

---

덱 구현

덱을 배열을 이용해서 구현하는 방법은 원형 큐를 구현하는 방법과 동일하다. 한 가지만 추가로 신경쓰면 된다. 원형 큐에서는 front, rear이 단조 증가했지만 덱에서는 감소할 수 있다. 따라서 front - 1, rear - 1의 값이 0보다 작을 수 있으므로 capacity를 더해준 다음 모듈러 연산을 해야한다. 그 외에는 연산에 따라 front, rear만 알맞게 움직여주면 된다. 연결리스트를 이용해 구현하는 방법도 이전의 이중 연결 리스트와 동일하게 구현하면 된다.

---

배열을 이용한 구현

class Deque<E> {
	private E[] data;
	private int capacity;
	private int front;
	private int rear;
	private int dequeSize;
	
	Deque() {
		capacity = 100;
		data = (E[]) new Object[capacity];
		front = rear = 0;
		dequeSize = 0;
	}
	
	private void grow() {
		E[] newData = (E[]) new Object[capacity + 100];
		
		for(int i = 1; i <= dequeSize; i++) {
			newData[i] = data[(front + i) % capacity];
		}
		
		capacity += 100;
		front = 0;
		rear = dequeSize;
		data = newData;
	}
	
	public void addFirst(E e) {
		if((rear + 1) % capacity == front) {
			grow();
		}
		
		data[front] = e;
		dequeSize++;
		front = (front - 1 + capacity) % capacity;
	}
	
	public void addLast(E e) {
		if((rear + 1) % capacity == front) {
			grow();
		}
		
		rear = (rear + 1) % capacity;
		data[rear] = e;
		dequeSize++;
	}
	
	public E pollFirst() {
		if(isEmpty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		else {
			front = (front + 1) % capacity;
			dequeSize--;
			return data[front];
		}
	}
	
	public E pollLast() { 
		if(isEmpty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		else {
			E ret = data[rear];
			rear = (rear - 1 + capacity) % capacity;
			dequeSize--;
			return ret;
		}
	}
	
	public E peekFirst() { 
		if(isEmpty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		else {
			return data[(front + 1) % capacity];
		}
	}
	
	public E peekLast() {
		if(isEmpty()) {
			throw new ArrayIndexOutOfBoundsException();
		}
		else {
			return data[rear];
		}
	}
	
	public int size() { 
		return dequeSize;
	}
	
	public boolean isEmpty() { 
		if(front == rear) {
			return true;
		}
		else {
			return false;
		}
	}
}

---

연결 리스트를 이용한 구현

class Deque<E> {
	private Node<E> headNode = new Node<>(null);
	private int dequeSize = 0;
	
	private class Node<E> {
		Node<E> prev, next;
		E data;
		
		Node(E data) {
			this.data = data;
			prev = next = null;
		}
	}
	
	public void addFirst(E e) {
		Node<E> node = new Node<>(e);
		
		if(dequeSize == 0) {
			headNode.prev = headNode.next = node;
		}
		else {
			headNode.next.prev = node;
			headNode.next = node;
		}
		
		dequeSize++;
	}
	
	public void addLast(E e) {
		Node<E> node = new Node<>(e);
		
		if(dequeSize == 0) {
			headNode.prev = headNode.next = node;
		}
		else {
			headNode.prev.next = node;
			headNode.prev = node;
		}
		
		dequeSize++;
	}
	
	public E pollFirst() {
		if(dequeSize == 0) {
			throw new NullPointerException();
		}
		else {
			E ret = headNode.next.data;
			headNode.next = headNode.next.next;
			dequeSize--;
			return ret;
		}
	}
	
	public E pollLast() { 
		if(dequeSize == 0) {
			throw new NullPointerException();
		}
		else {
			E ret = headNode.prev.data;
			headNode.prev = headNode.prev.prev;
			dequeSize--;
			return ret;
		}
	}
	
	public E peekFirst() { 
		if(dequeSize == 0) {
			throw new NullPointerException();
		}
		else {
			return headNode.next.data;
		}
	}
	
	public E peekLast() {
		if(dequeSize == 0) {
			throw new NullPointerException();
		}
		else {
			return headNode.prev.data;
		}
	}
	
	public int size() { 
		return dequeSize;
	}
}

---

컬렉션 프레임워크

Deque

Deque

덱도 큐처럼 클래스가 아니라 인터페이스다. Deque dq = new ArrayDeque<>(); 형식으로 사용.