[C언어] - 원형 덱 double-ended queue

🔵 원형 덱 double-ended queue

원형 큐는 항상 하나의 자리를 비워둠

front, rear에서 모두 삽입, 삭제가 가능한 큐

front, rear 모두 0으로 초기화

공백 상태 > front == rear

포화 상태 > front = (rear + 1) % M큐크기

 

🟡 원형 덱 코드

add_rear 뒤로 이동 > 빈 공간에 삽입

get_front 뒤로 이동 > 해당 값 삭제

get_rear 삭제 > 앞으로 이동

add_front 삽입 > 앞으로 이동

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

#define MAX_SIZE 10

typedef int element;
typedef struct {
	int front, rear;
	element data[MAX_SIZE];
} QueueType;

void init(QueueType* q) {
	q->front = -1;
	q->rear = -1;
}

int is_full(QueueType* q) {
	return q->front == (q->rear + 1) % MAX_SIZE;	// 원형 큐의 경우
}

int is_empty(QueueType* q) {
	return q->front == q->rear;
}

// rear에서 삽입
void add_rear(QueueType* q, int item) {
	if (is_full(q)) {
		printf("에러");
		return;
	}
	else {
		q->rear = (q->rear + 1) % MAX_SIZE;
		q->data[(q->rear)] = item;
	}
}

// rear에서 삭제
int get_rear(QueueType* q) {
	int prev = q->rear;

	if (is_empty(q)) {
		printf("에러");
		return;
	}
	else {
		q->rear = (q->rear - 1 + MAX_SIZE) % MAX_SIZE;
		return q->data[(prev)];
	}
}

// front에서 삭제
int get_front(QueueType* q) {
	if (is_empty(q)) {
		printf("에러");
		return;
	}
	else {
		q->front = (q->front + 1) % MAX_SIZE;
		return q->data[(q->front)];
	}
}

// front에서 삽입
void add_front(QueueType* q, int item) {
	if (is_full(q)) {
		printf("에러");
		return;
	}
	else {
		q->data[(q->front)] = item;
		q->front = (q->front - 1 + MAX_SIZE) % MAX_SIZE;
	}
}

int main() {
	int i;
	QueueType q;
	init(&q);

	add_rear(&q, 1);
	add_rear(&q, 2);
	add_rear(&q, 3);

	i = get_rear(&q);
	printf("%d\n", i);
	return 0;
}

 

* 한 칸 뒤로 이동 시

q->front = (q->front + 1) % MAX_SIZE;

* 한 칸 앞으로 이동 시 

q->front = (q->front - 1 + MAX_SIZE) % MAX_SIZE;