[자료구조] 덱 (Deque : Double-Ended-Queue) 의 구조와 구현 - 덱의 전단(front)와 후단(rear)의 입출력

 

 

 

덱은, 기존의 원형 큐에서 일부 기능이 추가된, 전단과 후단 양쪽 모두에서 삽입과 삭제의 입출력과 반환이 가능한 원형 큐이다. 

 

 

원형 큐의 구조와 구현

https://dream-and-develop.tistory.com/102

 

 

 

 

 

덱(DEQUE : Double-Ended Queue)

 

덱(Deque) 은 큐의 전단(front)과 후단(rear) 에서 모두 입출력(삽입/삭제)가 가능한 큐이다.

덱의 추상 자료형은 다음과 같다.

 

 

 

- create(MAX) : 구조체 DequeType을 구현하여 구조체 변수를 선언하는 것과 동일하다.

- init(dq) : 덱을 초기화한다. 덱의 rear, front 멤버 변수를 각각 0으로 설정한다.

- is_empty(dq) : 큐가 공백 상태인지 체크한다. 기존의 원형 큐와 동일한 방법을 사용한다. 

- is_full(dq) : 큐가 포화 상태인지 체크한다. 기존의 원형 큐와 동일한 방법

- add_front(dq, e) : 덱의 맨 앞에 요소를 추가한다. 다만, front 값을 1 감소 시킨 후, 삽입한다.

- add_rear(dq, e) : 덱의 맨 뒤에 요소를 추가한다. 기존 원형 큐의 enqueue() 연산과 동일하다. rear 값을 1 증가 후, 삽입한다.

- delete_front(dq) : 덱의 맨 앞의 요소를 반환 후 삭제한다. front 값을 1 증가 후, front가 가리키는 요소를 반환한다. 기존 원형 큐의 dequeue() 연산과 동일하다.

- delete_rear(dq) : 덱의 맨 뒤의 요소를 반환 후 삭제 한다. rear이 가리키는 요소를 반환 후, rear 값을 1 감소한다.

- get_front(dq) : 덱의 맨 앞의 요소를 반환한다. front의 값 1을 증가한 위치의 요소를 반환한다.

- get_rear(dq) : 덱의 맨 뒤의 요소를 반환한다. rear 가 가리키는 위치의 요소를 반환한다.

 

 

정리하면,

add_rear() 과 delete_front() 연산은 기존 (원형)큐의 enqueue, dequeue 연산과 동일하고, 

전단과 관련된 연산들만 사용하면, 스택이 된다.

 

따라서, add_rear() / delete_front()을 제외한,

전단에 삽입하는 add_front() / 후단의 요소를 반환하고 삭제하는 delete_rear(), 

그리고 get_rear(), get_front() 의 연산이 기존 큐에서 추가된 것이라 볼 수 있다.

 

 

---

 

위의 ADT를 코드로 구현한 것을 하나하나 자세히 살펴보자.

 

 

1. 덱의 구조체 선언

DequeType의 이름으로 typedef 시켜놓은 구조체는 다음과 같다.

element는 간단하게 정수형으로 정의하고,

MAX_QUEUE_SIZE는 10으로 정의되어 있으므로, 총 9개의 요소를 저장할 수 있는 덱의 배열,

그리고 전단(front)와 후단(rear)을 멤버 변수로 선언하였다.

 

(원형 큐의 공백, 포화를 구분하기 위해서 한 개의 공간은 항상 비워둔다 !)

 

#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}DequeType;

 

 

2. 덱 초기화, 공백/포화 상태 확인

각각 DequeType 구조체 포인터를 받아온다.

init_deque() - 덱의 front, rear 값을 0으로 초기화한다.

is_empty() - front와 rear 값이 같다면 덱이 공백 상태임을 체크

is_full() - rear이 front보다 한 칸 앞에 위치해 있다면, 덱이 포화 상태임을 체크

 

// 덱 초기화
void init_deque(DequeType* dq) {dq->front = dq->rear = 0;}

// is_empty
int is_empty(DequeType* dq) { return (dq->front == dq->rear); }

// is_full
int is_full(DequeType* dq) { return ((dq->rear + 1) % MAX_QUEUE_SIZE == dq->front); }

 

 

3. 기존 큐와 동일한 add_rear() (enqueue와 동일), delete_front() (dequeue와 동일)

add_rear() - 후단에 새로운 요소를 삽입한다. rear 값을 1 증가시킨 후, 해당 위치에 요소를 삽입한다.

delete_front() - 전단의 요소를 반환하고 삭제한다. front의 값을 1 증가시킨 후, 해당 위치의 요소를 반환한다. 

(++전위 연산 후, 반환)

 

// add_rear
void add_rear(DequeType* dq, element item) {
	// rear 값 1 증가 후 삽입

	if (is_full(dq)) {
		printf("Deque is full \n");
		exit(1);
	}
	dq->rear = (dq->rear + 1) % MAX_QUEUE_SIZE;
	dq->data[dq->rear] = item;
}

// delete_front
element delete_front(DequeType* dq) {
	// front 값 1 증가 후 반환

	if (is_empty(dq)) {
		printf("Deque is empty \n");
		exit(1);
	}
	dq->front = (dq->front + 1) % MAX_QUEUE_SIZE;
	return dq->data[dq->front];
}

 

 

4. add_front()

전단에 새로운 요소를 삽입한다.

front는 첫번째 요소가 위치한 인덱스보다 하나 앞을 가리키고 있다.

따라서 전단에 삽입하기 위해서는, 현재 front 의 값에 요소를 삽입한 다음에,

front의 값을 1 감소시킨다. 

이 때, 인덱스 0에서 음수의 값이 될 수 있는 경우를 위해, 

1 감소시킨 후에 다시 MAX_QUEUE_SIZE 만큼 더한 후에, MAX_QUEUE_SIZE로 나눈 나머지 값을 대입하도록 한다.

 

// add_front
void add_front(DequeType* dq, element item) {
	// front가 가리키는 곳에 삽입 후, front값 1 감소

	if (is_full(dq)) {
		printf("Deque is full \n");
		exit(1);
	}
	dq->data[dq->front] = item;
	dq->front = (dq->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

 

 

5. delete_rear()

후단의 요소를 반환 후 삭제한다.

rear은 마지막 요소를 가리키고 있다. 따라서 해당 요소를 반환 후 삭제하기 위해서는,

현재의 값을 반환한 다음에, rear의 값을 감소시켜야 한다.

하지만 리턴을 하게 되는 순간, 다음 rear의 값을 감소시키는 문장은 실행되지 않게 되므로,

반환할 요소의 현재 인덱스(==현재 rear이 가리키는 위치의 인덱스값)를 prev라는 새로운 변수에 대입한다.

이후 rear의 값을 1 감소 시킨 후, 기존의 인덱스 값을 저장하는 prev의 요소를 반환한다.

 

이 때에도, 기존 rear의 값이 0인 경우 1을 감소시키면 음수가 되므로,

1 감소시킨 후 MAX_QUEUE_SIZE를 더한 후에, MAX_QUEUE_SIZE로 나눈 나머지의 값을 저장하도록 한다.

 

// delete_rear
element delete_rear(DequeType* dq) {
	// rear이 가리키는 값 반환 후, rear 값 1 증가

	int prev = dq->rear;
	if (is_empty(dq)) {
		printf("Deque is empty \n");
		exit(1);
	}
	dq->rear = (dq->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return dq->data[prev];
}

 

 

6. get - 값 반환

get_front()

front 부분의 연산을 스택의 pop, push 연산이라고 치면,

전단의 요소를 반환하기만 하는 get_front() 연산은 스택에서의 peek() 연산과 동일하다고 볼 수 있겠다.

front의 값을 1 증가시킨 후에 해당 요소를 반환한다.

get_rear()

마지막 rear이 가리키고 있는 위치의 요소를 그대로 반환한다.

 

//get_front
element get_front(DequeType* dq) {
	// front 값 1 증가시킨 값의 요소를 반환
	
	if (is_empty(dq)) {
		printf("Deque is empty \n");
		return;
	}
	return dq->data[(dq->front + 1) % MAX_QUEUE_SIZE];
}

// get_rear
element get_rear(DequeType* dq) {
	// rear이 가리키는 값 반환

	if (is_empty(dq)) {
		printf("Deque is empty \n");
		return;
	}
	return dq->data[dq->rear];
}

 

 

 

---

전체 코드는 다음과 같다.

 

#include <stdio.h>

#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front, rear;
}DequeType;

// 덱 초기화
void init_deque(DequeType* dq) {dq->front = dq->rear = 0;}

// is_empty
int is_empty(DequeType* dq) { return (dq->front == dq->rear); }

// is_full
int is_full(DequeType* dq) { return ((dq->rear + 1) % MAX_QUEUE_SIZE == dq->front); }

// add_front
void add_front(DequeType* dq, element item) {
	// front가 가리키는 곳에 삽입 후, front값 1 감소

	if (is_full(dq)) {
		printf("Deque is full \n");
		exit(1);
	}
	dq->data[dq->front] = item;
	dq->front = (dq->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
}

// add_rear
void add_rear(DequeType* dq, element item) {
	// rear 값 1 증가 후 삽입

	if (is_full(dq)) {
		printf("Deque is full \n");
		exit(1);
	}
	dq->rear = (dq->rear + 1) % MAX_QUEUE_SIZE;
	dq->data[dq->rear] = item;
}

// delete_front
element delete_front(DequeType* dq) {
	// front 값 1 증가 후 반환

	if (is_empty(dq)) {
		printf("Deque is empty \n");
		exit(1);
	}
	dq->front = (dq->front + 1) % MAX_QUEUE_SIZE;
	return dq->data[dq->front];
}

// delete_rear
element delete_rear(DequeType* dq) {
	// rear이 가리키는 값 반환 후, rear 값 1 증가

	int prev = dq->rear;
	if (is_empty(dq)) {
		printf("Deque is empty \n");
		exit(1);
	}
	dq->rear = (dq->rear - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return dq->data[prev];
}

//get_front
element get_front(DequeType* dq) {
	// front 값 1 증가시킨 값을 반환
	
	if (is_empty(dq)) {
		printf("Deque is empty \n");
		return;
	}
	return dq->data[(dq->front + 1) % MAX_QUEUE_SIZE];
}

// get_rear
element get_rear(DequeType* dq) {
	// rear이 가리키는 값 반환

	if (is_empty(dq)) {
		printf("Deque is empty \n");
		return;
	}
	return dq->data[dq->rear];
}

int main() {
	DequeType deque; // MAX_QUEUE_SIZE = 10

	init_deque(&deque); // front, rear = 0

	// 0부터 9까지의 값을 add_rear
	for (int i = 0;i < 10;i++) {
		// 홀수인 경우는 후단에 삽입
		if (i % 2) {
			add_rear(&deque, i);
			printf("add_rear(%d) \t front=%d, rear=%d \n",
				get_rear(&deque), deque.front, deque.rear);
		}
		// 짝수인 경우는 전단에 삽입
		else{
			add_front(&deque, i);
			printf("add_front(%d) \t front=%d, rear=%d \n",
				get_front(&deque), deque.front, deque.rear);
		}
	}
}

 

 

마지막에 작성되어 있는 main 함수를 살펴보면,

총 9개의 요소를 저장할 수 있는 덱 deque가 초기화되었다.

 

for문 내부에서는 제어 변수 i가 0부터 9까지 총 10번 돌아가며,

i의 값이 홀수/짝수인지에 따라 홀수이면 후단 부분에, 짝수이면 전단 부분에 차례대로 삽입이 된다.

삽입이 된 후에는, front와 rear의 값을 확인해보기 위해 get_rear()과 get_front() 가 각각 실행되어 출력된다.

 

 

실행 결과는 다음과 같다.

 

 

덱의 MAX_QUEUE_SIZE가 10으로 정의되었으므로, 총 9개(0부터 8)의 요소만 삽입이 된 것을 확인할 수 있다.

그리고 i의 값이 짝수여서 전단에 삽입된 경우에는, front의 값이 0부터 1씩 감소되는 것을,

i의 값이 홀수여서 후단에 삽입된 경우에는, rear의 값이 0부터 1씩 증가되는 것을 확인할 수 있다.

 

마지막에는 (rear+1)%MAX_QUEUE_SIZE == front 가 성립되어 

9가 후단에 삽입되지 못하고 덱이 포화상태라는 문장을 출력하고 실행이 종료된다.

 

 

 

---

이중 연결 리스트 로의 확장

 

 

전단과 후단 모두에서 입출력이 이루어지는 덱(Double Ended Queue)을 살펴보았다.

포화 또는 공백 상태만 아니라면, 전단과 후단 어디에든지 요소를 삽입하고 삭제할 수 있다는 장점이 있다.

그러나 문제점은, 배열에 요소를 입출력하는 자료이므로,

정해진 크기만큼의 요소만 다룰 수 있다는 점이다.

 

따라서, 프로그램 실행 도중 사용자가 자유롭게 동적 메모리를 할당 받아 크기의 제한 없이 요소를 삽입하고,

더하여 원하는 위취에 삽입/삭제 가능할 수 있도록 '연결 리스트'로 구현하면

이중 연결리스트(Double Linked List) 가 된다. 

 

 

 

이중 연결리스트를 활용한 실습 문제

 

https://dream-and-develop.tistory.com/64