덱(deque)이란?

덱(deque)은 double-ended queue의 줄임말로 큐의 front와 rear에서 모두 삽입과 삭제가 가능한 큐를 말한다. 하지만 여전히 중간에서 삽입하거나 삭제하는 것은 허용하지 않는다.

덱의 추상 자료형

객체	전단과 후단을 통한 접근을 허용하는 요소들의 모음
연산	addFront(e): 주어진 요소 e를 덱의 맨 앞에 추가한다.
	deleteFront(): 덱이 비어 있지 않으면 맨 앞 요소를 삭제하고 반환한다.
	addRear(e): 주어진 요소 e를 덱의 맨 뒤에 추가한다.
	deleteRear(): 덱이 비어 있지 않으면 맨 뒤 요소를 삭제하고 반환한다.
	isEmpty(): 덱이 비어 있지 않으면 true, 아니면 false를 반환한다.
	getFront(): 덱이 비어 있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.
	getRear(): 덱이 비어 있지 않으면 맨 뒤 요소를 삭제하지 않고 반환한다.
	isFull(): 덱이 가득 차 있으면 true, 아니면 false를 반환한다.
	display(): 덱의 모든 요소들을 출력한다.

배열을 이용한 원형 덱의 구현

배열을 이용한 원형 덱의 동작은 원형 큐와 거의 비슷하다.

앞에서 큐 클래스를 설계하여 구현했으므로 덱을 큐 클래스를 이용해서 설계해보면

#pragma once
#include "CircularQueue.h"

class CircularDeque : public CircularQueue {
public:
	CircularDeque()	{ }
	void addRear( int val ) { enqueue(val);} // enqueue() 호출
	int deleteFront( ) { return dequeue(); } // dequeue() 호출
	int getFront( )    { return peek(); }	 // peek() 호출
	void addFront( int val ) {		// 전단에 삽입		
		if( isFull() )
			error("  error: 덱이 포화상태입니다\n");
		else {
			data[front] = val;
			front = (front-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
		}
	}
	int deleteRear( ) {		// 후단에서 삭제
		if( isEmpty() )
			error("  Error: 덱이 공백상태입니다\n");
		else {
			int ret = data[rear];
			rear = (rear-1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
			return ret;
		}
	}
	int getRear( ){			// 후단에서 peek
		if( isEmpty() )
			error("  Error: 덱이 공백상태입니다\n");
		else return data[rear];
	}
	void display( ) {		
		printf( "덱의 내용 : ");	
		int maxi = (front < rear) ? rear : rear+MAX_QUEUE_SIZE;
		for( int i = front+1 ; i<=maxi ; i++ )
			printf( "[%2d] ", data[i%MAX_QUEUE_SIZE]);
		printf( "\n");
	}
};

연결된 덱

스택이나 큐와는 달리 덱은 전단과 후단에서 모두 삽입, 삭제가 가능하기 때문에 하나의 노드에서 알아야할 정보가 더 많다. 구체적으로는 선행노드와 후속노드를 가리키는 포인터 변수를 가져야 하는데, 이러한 구조를 이중 연결 리스트(double linked list)라고 한다.