자료구조 (원형 큐)

---

개요

이번에는 자료구조의 원형큐에 대해서 알아 보겠습니다.

 

---

큐(Queue) 란?

 

큐(queue)는 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말하는데, 이와 같은 알고리즘은 실생활에서 놀이기구의 줄을 서는 방식으로 설명 할 수 있다.

큐는 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념입니다.

프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용이 됩니다.

 

#include <stdio.h>
#include <stdlib.h>
#define Q_SIZE 6

typedef char element;
typedef struct {
	element queue[Q_SIZE];
	int front, rear;

}Qtype;
int isEmpty(Qtype* Q) {
	if (Q->front == Q->rear) {
		printf("큐는 비어있습니다");
		return 1;
	}
	else {
		return 0;
	}
}
int isFull(Qtype* Q) {
	if (((Q->rear + 1) % Q_SIZE) == Q->front) {
		return 1;
	}
	else {
		return 0;
	}
}

Qtype* createQueue() {
	Qtype* Q;
	Q = malloc(sizeof(Qtype));
	Q->front = 0;
	Q->rear = 0;
	return Q;
}
void enQueue(Qtype* Q, int item) {
	if (isFull(Q)) {
		return;
	}
	else {
		Q->rear = ((Q->rear + 1) % Q_SIZE);
		Q->queue[Q->rear] = item;
	}
}
element deQueue(Qtype* Q) {
	if (isEmpty(Q)) {
		return 0;
	}
	else {
		Q->front = ((Q->front + 1) % Q_SIZE);
		return Q->queue[Q->front];
	}
}
element Peek(Qtype* Q) {
	if (isEmpty(Q)) {
		exit(1);
	}
	else {
		return Q->queue[(Q->front + 1) % Q_SIZE];
	}
}


void printQ(Qtype* Q) {
	int i, first, last;
	first = (Q->front + 1) % Q_SIZE;
	last = (Q->rear + 1) % Q_SIZE;
	i = first;
	while (i != last) {
		printf("%3c", Q->queue[i]);
		i = (i + 1) % Q_SIZE;
	}

}

void main() {
	Qtype* Q1 = createQueue();
	element data;
	enQueue(Q1, 'A');
	enQueue(Q1, 'B');
	enQueue(Q1, 'C');
	enQueue(Q1, 'D');
	enQueue(Q1, 'E');



	printQ(Q1);
	printf("\n-------------------------------------\n");
	data = Peek(Q1);
	printf("Peek item %c\n", data);
	printf("\n 삭제 > ");
	data = deQueue(Q1);
	printQ(Q1);

}

 

 

실행화면

삽입 후 삭제