[📗c언어 쉽게 풀어쓴 자료구조5] 큐 (QUEUE)

👑 큐 추상 데이터 타입

: 선입선출 (First-in First-out), rear(후단-삽입), front(전단-삭제)

• is_empty(): front=rear
• is_ful(): front = rear + 1
• enqueue(): rear에서 삽입
• dequeue(): front에서 삭제

👑 선형 큐

• 초기값: front=rear = -1
• rear 증가 후 삽입
• front 증가 후 삭제
• 공백 상태: front=rear
• 포화 상태: rear = MAX_QUEUE_SIZE-1

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

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

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

//초기화 함수
void init_queue(QueueType* q) {
	q->rear = -1;
	q->front = -1;
}

//큐 출력 함수
void queue_print(QueueType* q) {
	for (int i = 0;i < MAX_QUEUE_SIZE;i++) {
		if (i <= q->front || i > q->rear)
			printf(" | ");
		else
			printf("%d | ", q->data[i]);
	}
}

//포화 함수
int is_full(QueueType  *q) {
	if (q->rear == (MAX_QUEUE_SIZE - 1))
		return 1;
	else
		return 0;
}

//공백 함수
int is_empty(QueueType* q) {
	if (q->front == q->rear)
		return 1;
	else
		return 0;
}

//삽입 함수
void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		error("큐가 포화상태입니다\n");
		return;
	}
	q->data[++(q->rear)] = item;
}

//삭제 함수
int dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백상태입니다.\n");
		return -1;
	}
	int item = q->data[++(q->front)];
	return item;
}

int main(void)
{
	int item = 0;
	QueueType q;
	init_queue(&q);

	enqueue(&q, 10);queue_print(&q);
	enqueue(&q, 20);queue_print(&q);
	enqueue(&q, 30);queue_print(&q);

	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	item = dequeue(&q); queue_print(&q);
	return 0;
}

👑 원형 큐

• 초기값: front = rear = 0
• front: 증가 후 삭제 (초기 값의 하나 앞)
• rear: 증가 후 삽입
• 공백 상태: front=rear
• 포화 상태: front = (rear + 1)%MAX_QUEUE_SIZE
• 나머지 연산 (끝과 처음이 연결되어있는 것으로 가정)

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 5

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

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

//초기화 함수
void init_queue(QueueType* q) {
	q->rear = q->front = 0;
}

//큐 출력 함수
void queue_print(QueueType* q) {
	printf("QUEUE(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");
}

//포화 함수
int is_full(QueueType  *q) {
	if (q->front == (q->rear+1) % MAX_QUEUE_SIZE)
		return 1;
	else
		return 0;
}

//공백 함수
int is_empty(QueueType* q) {
	if (q->front == q->rear)
		return 1;
	else
		return 0;
}

//삽입 함수
void enqueue(QueueType* q, int item) {
	if (is_full(q)) {
		error("큐가 포화상태입니다\n");
		return;
	}
	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
	q->data[q->rear] = item;
}

//삭제 함수
int dequeue(QueueType* q) {
	if (is_empty(q)) {
		error("큐가 공백상태입니다.\n");
		return -1;
	}
	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
	return q->data[q->front];
}

int main(void)
{
	QueueType q;
	int element;

	init_queue(&q);
	printf("--데이터 추가 단계--\n");
	while (!is_full(&q)) {
		printf("정수를 입력하시오: ");
		scanf_s("%d", &element);
		enqueue(&q, element);
		queue_print(&q);
	}
	printf("큐는 포화상태입니다.\n");

	printf("--데이터 삭제 단계--\n");
	while (!is_empty(&q)) {
		element = dequeue(&q);
		printf("꺼내진 정수: %d\n", element);
		queue_print(&q);
	}
	printf("큐는 공백상태입니다.\n");
	return 0;
}

👑 덱

: 전단과 후단에서 모두 삽입, 삭제가 가능한 큐

• add_front, delete_front: 스택의 push, pop과 같음
• add_rear, delete_front: 큐의 기존 enqueue, dequeue와 같음
  *기존 큐에 없던 함수 2가지 (처리 후 감소!)
• add_front(): 넣고 감소
• delete_rear(): 반환 후 감소

⭕ TIL (Today I learned)

& 스택에서 push는 증가 후 삽입 (증가 후 처리), pop은 반환 후 감소 (처리 후 감소)
선형큐, 원형큐에서는 항상 증가 후 삽입, 삭제!! (증가 후 처리)
덱의 add_front와 delete_rear에서는 삽입 후 감소, 반환 후 감소!!! (처리 후 감소)

-> 원형큐의 나머지로 나누는 것이 잘 이해가 되지 않았음. 직접 상상하며 대입해보며 해결함. 머릿속으로 상상해가면서 코드 보기!! 큐에서 front는 최초값의 앞이라는 것 기억하기!!! (증가하기 전에는 front에 아무 값도 없다는 것)