[자료구조] 9. 큐(Queue) - 덱 ADT / 덱 구현

 

9.1. 덱의 ADT

 

9.2 배열 기반 덱 구현

    1) 덱 구현

    2) 덱 연산 구현

 

 

덱(deque)은 double-ended-queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입 및 삭제가 가능하다. 

덱을 구현하는 방법도 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있다. 

 

---

9.1 덱의 ADT

 

◾ 객체 :  n개의 element형 요소들의 순서 있는 모임

◾ 연산
     • create() : 덱을 생성
     • initDeque(dq) :  덱을 초기화
     • isEmpty(dq) : 덱이 공백 상태인지 검사
     • isFull(dq) : 덱이 포화 상태인지 검사
     • addFront(dq,e) : 덱의 전단에 요소를 추가     
     • addRear(dq,e) : 덱의 후단에 요소 추가
     • deleteFront(dq) : 덱의 전단 요소를 반환한 다음 삭제
     • deleteRear(dq) : 덱의 후단 요소를 반환한 다음 삭제
     • getFront(dq) : 덱의 전단 요소를 삭제하지 않고 반환
     • getRear(dq) : 덱의 후단 요소를 삭제하지 않고 반환 

 

---

9.2 배열 기반 덱 구현

 

1) 덱 구현

 

//[배열 기반 덱 구현]

#define MAX_QUEUE_SIZE 100   //덱의 최대 크기

typedef int element; // 덱에 저장될 요소의 자료형

// 덱 정의
typedef struct {
	int front;                        //front 변수
	int rear;                         //rear 변수
	element data[MAX_QUEUE_SIZE];     //요소들을 저장할 배열
} DequeArr;

 

 

2) 덱 연산 구현

 

덱의 연산 중 isEmpty(), isFull(), initDeque(), printDeque(), addRear(), deleteFront(), getFront() 등의 연산은 원형큐에서의

동작 방식과 같다. 

덱에서 새롭게 추가된 연산에는 deleteRear(), addFront(), getRear()가 있다.  deleteRear()와 addFront()의 경우, 원형큐의 반대 방향으로 회전이 필요하다. 즉 후단 삭제, 전단 삽입 연산 시에는 front와 rear의 값을 감소시켜야 한다. 이때 front와 rear가 감소하여 음수가 될수 있으므로 MAX_DEQUE_SIZE를 더해준 후 나머지 연산을 통해 front와 rear의 값을 변경시켜야 한다. 

 

 

//[배열 기반 덱 연산 구현]

//덱 구조체 초기화 함수
void initDeque(DequeArr *q) {
	q->front = 0;
	q->rear = 0;
}

// 오류 함수
void error(char* message) {
	fprintf(stderr, "%s\n", message);
	exit(1);
}

// 덱 출력 함수
void dequePrint(DequeArr* q) {
	printf("DEQUE (front=%d, rear=%d) = ", q->front, q->rear);
	
	if (!isEmpty(q)) {
		int i = q->front;
		do {
			i = (i + 1) % MAX_QUEUE_SIZE;
			printf("%d | ", q->data[i]);
			if (i == q->rear)
				break;
		} while (i != q->front);
	}
	printf("\n");
}

// 공백 및 포화 상태 검사 함수
int isEmpty(DequeArr *q) {
	return (q->front == q->rear);
}

int isFull(DequeArr* q) {
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);    //front가 rear보다 하나 앞에 있는 상태가 포화 상태이기 때문에 'rear+1'을 하고, front와 rear가 회전하기 때문에 나머지 연산을 한다. 
}

// 항목 삽입 함수
void addRear(DequeArr* q, element item) {
	if (isFull(q)) 
		error("큐가 포화 상태입니다.");

	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;    //front 시계 방향 이동
	q->data[q->rear] = item;                     //요소 삽입
}

void addFront(DequeArr* q, element item) {
	if (isFull(q))
		erorr("큐가 포화상태입니다.");
	q->data[q->front] = item;       //원형큐에서 front는 첫 번째 항목의 하나 앞을 가리키기 때문에 먼저 요소를 삽입하고 front의 값을 감소한다.
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;    //front 반시계 방향 이동
}

// 항목 삭제 함수
element deleteFront(DequeArr* q) {
	if (isEmpty(q)) 
		error("큐가 공백 상태입니다. ");

	q->front = (q->front + 1) % MAX_QUEUE_SIZE;      //rear 시계 방향 이동
	return q->data[q->front];      
}

element deleteRear(DequeArr* q) {
	int prev = q->rear;      //삭제 및 반환할 요소의 인덱스
	if (isEmpty(q))
		error("큐가 공백 상태입니다.");
	q->rear = (q->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;     //rear 반시계 방향 이동
	return q->data[prev];
}

// 항목 추출 함수
element getFront(DequeArr* q) {
	if (isEmpty(q))
		erorr("큐가 공백 상태입니다.");
	return q->data[(q->front + 1)] % MAX_QUEUE_SIZE;
}

element getRear(DequeArr* q) {
	if (isEmpty(q))
		error("큐가 공백 상태입니다.");
	return q->data[q->rear];
}