큐

• 큐(queue): 선입선출 구조
  • 인큐(enqueue): 데이터를 넣음
  • 디큐(dequeue): 데이터를 꺼냄
  • 프런트(front): 데이터를 꺼내는 쪽
  • 리어(rear): 데이터를 넣는 쪽

---

배열로 큐 만들기

• 배열 que[]={1, 2, 3}

인큐: que[3] = 4;

디큐: x = que[0];

-> 이후의 모든 요소를 한 칸씩 앞으로 옮김: 복잡도 O(n) !

---

링 버퍼로 큐 만들기

링 버퍼: 배열의 처음과 끝이 연결되었다고 보는 자료구조

첫 번째 요소가 front, 마지막 요소가 rear-1

프런트와 리어의 값을 업데이트하며 인큐와 디큐를 수행하므로 복잡도 O(1) !

 

• 헤더파일 IntQueue.h

#ifndef __IntQueue
#define __IntQueue

typedef struct {
	int max; //큐의 최대 용량
	int num; //현재 요소 개수
	int front;
	int rear;
	int* que; //큐의 맨 앞 요소에 대한 포인터
}IntQueue;

int Initialize(IntQueue* q, int max);

int Enque(IntQueue* q, int x);

int Deque(IntQueue* q, int* x);

int Peek(const IntQueue* q, int* x);

void Clear(IntQueue* q);

int Capacity(const IntQueue* q);

int Size(const IntQueue* q);

int IsEmpty(const IntQueue* q);

int IsFull(const IntQueue* q);

int Search(const IntQueue* q, int x);

void Print(const IntQueue* q);

void Terminate(IntQueue* q);

#endif

 

• 소스파일 IntQueue.c

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

int Initialize(IntQueue* q, int max) {
	q->num = q->front = q->rear = 0;
	if ((q->que = calloc(max, sizeof(int))) == NULL) {
		q->max = 0;
		return -1;
	}
	q->max = max;
	return 0;
}

int Enque(IntQueue* q, int x) {
	if (q->num >= q->max) return -1; //큐가 가득 참
	else {
		q->num++;
		q->que[q->rear++] = x;
		if (q->rear == q->max) q->rear = 0;
		return 0;
	}
}

int Deque(IntQueue* q, int* x) {
	if (q->num <= 0) return -1;
	else {
		q->num--;
		*x = q->que[q->front++];
		if (q->front == q->max) q->front = 0;
		return 0;
	}
}

int Peek(const IntQueue* q, int* x) {
	if (q->num <= 0) return -1;
	*x = q->que[q->front];
	return 0;
}

void Clear(IntQueue* q) {
	q->num = q->front = q->rear = 0;
}

int Capacity(const IntQueue* q) {
	return q->max;
}

int Size(const IntQueue* q) {
	return q->num;
}

int IsEmpty(const IntQueue* q) {
	return q->num <= 0;
}

int IsFull(const IntQueue* q) {
	return q->num >= q->max;
}

int Search(const IntQueue* q, int x) {
	int i, idx;
	for (i = 0; i < q->num; i++) {
		if (q->que[idx = (q->front + i) % q->max] == x) return idx;
	}
	return -1;
}

void Print(const IntQueue* q) {
	int i;
	for (i = 0; i < q->num; i++) 
		printf("%d ", q->que[(q->front + i) % q->max]);
	putchar('\n');
}

void Terminate(IntQueue* q) {
	if (q->que != NULL) free(q->que);
	q->max = q->num = q->front = q->rear = 0;
}

 

• 큐를 사용하는 프로그램 IntQueueTest.c

#include <stdio.h>
#include "IntQueue.h"

int main(void) {

	IntQueue que;

	if (Initialize(&que, 64) == -1) {
		puts("큐의 생성에 실패하였습니다.");
		return -1;
	} 
	while (1) {
		int m, x;

		printf("현재 데이터 수: %d / %d \n", Size(&que), Capacity(&que));
		printf("(1)인큐 (2) 디큐 (3)피크 (4)출력 (0)종료 : ");
		scanf_s("%d", &m);
		
		if (m == 0) break;
		switch (m) {
		case 1:
			printf("데이터 : ");
			scanf_s("%d", &x);
			if (Enque(&que, x) == -1) puts("오류: 인큐에 실패하였습니다.");
			break;

		case 2:
			if (Deque(&que, &x) == -1) puts("오류: 디큐에 실패하였습니다.");
			else printf("디큐한 데이터는 %d입니다.\n", x);
			break;

		case 3:
			if (Peek(&que, &x) == -1) puts("오류: 피크에 실패하였습니다.");
			else printf("피크한 데이터는 %d입니다.\n", x);
			break;

		case 4:
			Print(&que);
			break;
		}
	}
	Terminate(&que);
	return 0;
}