덱(Deque) 2

2024.07.25 - [Algorithm] - 덱 (deque)

덱 (deque)

 

덱 (Double ended queue)의 줄임말로 양방향 front rear 상관없이 모두의 방향으로 원소의 저장과 삭제가 가능한 큐를 말함

원형 큐의 ADT에서 front에서의 enque, rear에서의 deque,front에서의 peek or get(return) 모두가 가능하기때문에 각각의 기능을 하는 함수들을 추가하면된다.

초기화와 공백,포화 검사함수에 있어서 시작이 모두 인덱스 0인것과 공백상태일때 front와 rear가 같을때, 포화상태일때 front==(rear+1)%MAX_QUEUE_SIZE인것도 같지만 단지, 원래 원형큐에는 존재하지않던 함수인 front_enque나 rear_delete일때, 반대방향의 회전을 해줘야한다는 것이다.이때는 다음과 같이 변경된다.

• front=(front-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;
• rear=(rear-1+MAX_QUEUE_SIZE)%MAX_QUEUE_SIZE;

전체 소스는 아래와 같다.

---

구현

#include <stdio.h>
#include <stdlib.h>

#define MAX_QUEUE_SIZE 5
typedef int element;
typedef struct {
	element data[MAX_QUEUE_SIZE];
	int front;
	int rear;
}DequeType;

void error(char* message) 
{
	fprintf(stderr, "%s\n", message);
	exit(1);
}
void init_deque(DequeType* q)
{
	q->front = 0;
	q->rear = 0;
}
int is_empty(DequeType* q)
{
	return (q->front == q->rear);
}
int is_full(DequeType* q)
{
	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void deque_print(DequeType* q)
{
	printf("DEQUE(front=%d rear=%d) = ", q->front, q->rear);
	if (!is_empty(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");
}

void add_rear(DequeType* q,element item)
{
	if (is_full(q)) {
		error("큐가 포화 상태입니다.");
	}
	q->rear = (q->rear +1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

element delete_front(DequeType* q)
{
	if (is_empty(q)) {
		error("큐가 공백 상태입니다.");
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

element get_front(DequeType* q)
{
	if (is_empty(q))
	{
		error("큐가 공백 상태입니다.");
	}
	return q->data[ (q->front + 1) % MAX_QUEUE_SIZE];
}

void add_front(DequeType* q, element item)
{
	if (is_full(q)) {
		error("큐가 포화 상태입니다.");
	}
	q->data[q->front] = item;
	q->front = (q->front - 1 + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	
}

element delete_rear(DequeType* q)
{
	int prev = q->rear;
	if (is_empty(q)) {
		error("큐가 공백 상태입니다.");
	}
	q->rear = (q->rear - 1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;
	return q->data[prev];
}

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

int main(void) {
	DequeType queue;
	init_deque(&queue);

	for (int i = 0; i < 3; i++)
	{
		add_front(&queue, i);
		deque_print(&queue);
	}
	for (int i = 0; i < 3; i++)
	{
		delete_rear(&queue);
		deque_print(&queue);
	}
	return 0;
}