원형 큐

원형 큐를 배열로 구현하는 방법

front = 가장 먼저 들어온 원소 = 가장 먼저 삭제될 원소

rear = 가장 마지막에 들어온 원소 = 가장 마지막에 삭제될 원소 

구조를 배열로 생성한 다음 (rear+1)%maxsize에 원소를 추가한다. rear++이 아니라 mod 연산을 이용하는 이유는 rear의 범위가 자연스럽게 0 ~ maxsize-1가 되어 index를 벗어나지 않고 자연스럽게 순환하는 구조가 만들어진다. 

 

 

 

Code

#include <stdio.h>
#define MAX 10
int arr[MAX] = { 0 };

int front = -1; // 가장 먼저 들어온 데이터 
int rear = -1;	// 가장 마지막에 들어온 데이터 

void enqueue(int data);
void dequeue();
void printArr();

int main(void) {
	for (int i = 0; i < MAX+1; i++)
	{
		enqueue(i);
	}
	printArr();
	for (int i = 0; i < MAX+1; i++)
	{
		dequeue();
	}
	printArr();
	return 0;
}

void enqueue(int data) {
	// 공백일 경우
	if (front == -1 && rear == -1) {
		arr[rear = front = 0] = data;
	}
	// 배열이 가득 차 있을 경우
	else if (front == (rear + 1) % MAX) {
		printf("배열이 가득참\n");
		return;
	}
	else {
		arr[rear = (rear + 1) % MAX] = data;
	}
}

void dequeue() {
	// 배열이 공백일 경우
	if (front == -1 && rear == -1) {
		printf("공백입니다 dequeue불가능\n");
		return;
	}
	// 마지막 원소일 경우
	else if (front == rear) {
		printf("마지막 원소가 삭제되었습니다.\n");
		arr[front] = 0;
		front = rear = -1;
	}
	else {
		arr[front%MAX] = 0;
		front = (front + 1) % MAX;
	}
}

void printArr() {
	for (int i = 0; i < MAX; i++) {
		printf("arr[%d] = %d\n", i, arr[i]);
	}
}

 

 

실행결과

배열이 가득참
arr[0] = 0
arr[1] = 1
arr[2] = 2
arr[3] = 3
arr[4] = 4
arr[5] = 5
arr[6] = 6
arr[7] = 7
arr[8] = 8
arr[9] = 9
마지막 원소가 삭제되었습니다.
공백입니다 dequeue불가능
arr[0] = 0
arr[1] = 0
arr[2] = 0
arr[3] = 0
arr[4] = 0
arr[5] = 0
arr[6] = 0
arr[7] = 0
arr[8] = 0
arr[9] = 0