큐 (Queue)

• 스택과 비슷한 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트

• 큐는 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조

  • 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)됨 -> 선입선출 구조 (FIFO, First-In-First-Out)

큐의 front와 rear

• front: 저장된 첫 번째 원소의 인덱스 저장

• rear: 저장된 마지막 원소의 인덱스 저장

스택과 큐의 삽입과 삭제 연산 비교

큐의 enQueue() 알고리즘

데이터를 삽입하는 기능을 수행함. 마지막 데이터의 위치가 변하므로 rear이 -1만큼 이동함.

큐의 deQueue() 알고리즘

데이터를 내보내는 기능을 수행함. 맨 앞에 있는 데이터가 바뀌므로 front가 +1만큼 이동함.

코드

header

#define Q_SIZE 4
typedef char element;

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

main

QueueType* createQueue() {
	QueueType* Q;
	Q = (QueueType*)malloc(sizeof(QueueType));
	Q->front = -1;
	Q->rear = -1;
	return Q;
}

int isQueueEmpty(QueueType* Q) {
	if (Q->front == Q->rear) {
		printf(" Queue is empty \n");
		return 1;
	}
	else {
		return 0;
	}
}

int isQueueFull(QueueType* Q) {
	if (Q->rear == Q_SIZE - 1) {
		printf(" Queue is full \n");
		return 1;
	}
	else {
		return 0;
	}
}

void enQueue(QueueType* Q, element item) {
	if (isQueueFull(Q)) {
		return;
	}
	else {
		Q->rear++;
		Q->queue[Q->rear] = item;
	}
}

element deQueue(QueueType* Q) {
	if (isQueueEmpty(Q)) {
		return;
	}
	else {
		Q->front++;
		return Q->queue[Q->front];
	}
}

element peekQ(QueueType* Q) {
	if (isQueueEmpty(Q)) return; // 공백 상태이면 연산 중단
	else return Q->queue[Q->front + 1];
}

void printQ(QueueType* Q) {
	int i;
	printf(" Queue : [");
	for (i = Q->front + 1; i <= Q->rear; i++) {
		printf("%3c", Q->queue[i]);
	}
	printf(" ]");
}

큐의 문제점

• 큐의 배열이 가득참.

  • 더이상 데이터를 넣을 수 없음. 공간 제한이 생김.

• 큐의 배열이 가득차지는 않았지만 rear이 마지막 인덱스를 가리키고 있으며, 앞의 공간이 비어있다.

  • 데이터를 넣을 공간을 마련하기 위해 데이터를 전체적으로 앞으로 이동시켜야함. 비효율적인 작업이 생김.

큐의 문제점 해결

원형큐

원형 큐

• 원형 큐는 선형 큐의 문제점을 해결하기 위해 구조화한 것

• 배열의 마지막 인덱스에서 다음 인덱스로 넘어갈 때 '(index+1)%배열 사이즈'를 이용하여 OutOfBoundsException이 일어나지 않고 인덱스 0으로 순환되는 구조를 가짐

  ---

• 선형 큐를 원형 큐로..

코드

header

#define Q_SIZE 4
typedef char element;

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

main

QueueType* createQueue() {
	QueueType* Q;
	Q = (QueueType*)malloc(sizeof(QueueType));
	Q->front = 0;
	Q->rear = 0;
	return Q;
}

int isQueueEmpty(QueueType* Q) {
	if (Q->front == Q->rear) {
		printf(" Queue is empty \n");
		return 1;
	}
	else {
		return 0;
	}
}

int isQueueFull(QueueType* Q) {
	if (((Q->rear + 1) % Q_SIZE) == Q->front) {
		printf(" Queue is full \n");
		return 1;
	}
	else {
		return 0;
	}
}

void enQueue(QueueType* Q, element item) {
	if (isQueueFull(Q)) {
		return;
	}
	else {
		Q->rear = (Q->rear + 1) % (Q_SIZE);
		Q->queue[Q->rear] = item;
	}
	return;
}

element deQueue(QueueType* Q) {
	if (isQueueEmpty(Q)) {
		return;
	}
	else {
		Q->front = (Q->front + 1) % (Q_SIZE);
		return Q->queue[Q->front];
	}
}

void printQ(QueueType* Q) {
	int i = Q->front;
	if (isQueueEmpty(Q)) {
		printf("\n공백 큐\n");
		return;
	}
	do {
		i = (i + 1) % Q_SIZE;
		printf("%d | ", Q->queue[i]);
		if (i == Q->rear) {
			break;
		}
	} while (i != Q->front);
	printf("\n\n");
	return;
}

[참고]
https://mailmail.tistory.com/41