Data Structures 10 - Circular Queue

Code

#include <stdio.h>
#include <malloc.h>

#define TOTAL_SPACE 5

/**
 * Circular integer queue.
 */
typedef struct CircleIntQueue{
	int data[TOTAL_SPACE];

	int front;

	int rear;
}*CircleIntQueuePtr;

/**
 * Initialize the queue.
 */
CircleIntQueuePtr initQueue() {
	CircleIntQueuePtr resultPtr = (CircleIntQueuePtr)malloc(sizeof(struct CircleIntQueue));
	resultPtr->front = 0;
	resultPtr->rear = 0;

	return resultPtr;
}// End of initQueue

/**
 * Enqueue operation.
 * 
 * @param paraValue The value of the new node.
 */
void enqueue(CircleIntQueuePtr paraPtr, int paraValue) {
	printf("Enqueue: %d ", paraValue);
	if ((paraPtr->rear + 1) % TOTAL_SPACE == paraPtr->front) {
		printf("Queue is full.\r\n");
		return;
	} // If queue is full

	paraPtr->data[paraPtr->rear] = paraValue;
	paraPtr->rear = (paraPtr->rear + 1) % TOTAL_SPACE;
}// End of enqueue

/**
 * Dequeue operation.
 * 
 * @return The value at the front.
 */
int dequeue(CircleIntQueuePtr paraPtr) {
	int resultValue;
	if (paraPtr->front == paraPtr->rear) {
		printf("Queue is empty.\r\n");
		return -1;
	} // If queue is empty

	resultValue = paraPtr->data[paraPtr->front];
	paraPtr->front = (paraPtr->front + 1) % TOTAL_SPACE;

	return resultValue;
}// End of dequeue

/**
 * Output the queue.
 */
void outputCircleIntQueue(CircleIntQueuePtr paraPtr){
	int i;
	if (paraPtr->front == paraPtr->rear) {
		printf("Empty queue.");
		return;
	} // If queue is empty

	printf("Elements in queue: ");
	for (i = paraPtr->front; i != paraPtr->rear; i = (i + 1) % TOTAL_SPACE) {
		printf("data[%d] = %d, ", i, paraPtr->data[i]);
	} // For loop over i

	printf("\r\n");
}// End of outputCircleIntQueue

/**
 * Unit test.
 */
void testCircleIntQueue(){
	int i = 10;
	CircleIntQueuePtr tempPtr = initQueue();
	for (; i < 16; i ++) {
		enqueue(tempPtr, i);
	}// For loop over i

	outputCircleIntQueue(tempPtr);

	for (i = 0; i < 6; i ++) {
		printf("Dequeued %d\r\n", dequeue(tempPtr));
	}// For loop over i

	for (i = 3; i < 6; i ++) {
		enqueue(tempPtr, i);
	}// For loop over i
	for (i = 20; i < 30; i ++) {
		enqueue(tempPtr, i);
		printf("Dequeued %d\r\n", dequeue(tempPtr));
		outputCircleIntQueue(tempPtr);
	}// For loop over i
}// End of testCircleIntQueue

/**
 * Main function.
 */
int main(){
	testCircleIntQueue();
	return 1;
}// End of main

Code Summary:

1. Defines a circular integer queue data structure CircleIntQueue, containing an integer array data and two pointers front and rear pointing to the front and rear of the queue respectively.

2. The initQueue function initializes the queue, allocates memory, and sets the front and rear pointers to 0.

3. The enqueue function enqueues an element; if the queue is full, it outputs a message and returns.

4. The dequeue function dequeues an element; if the queue is empty, it outputs a message and returns -1.

5. The outputCircleIntQueue function outputs all elements in the queue.

6. The testCircleIntQueue function is a unit test for testing the enqueue, dequeue, and output functionality of the queue.

7. The main function is the program entry point, calling the testCircleIntQueue function to run the test.

Running Result