[C++知识库]C语言 实现循环队列

C语言 实现循环队列

一、基本概念及注意事项

1.基本概念

队列是一种特殊的线性表结构，特殊之处在于它只允许在表的前端(front)删除元素，在表的尾端(rear)插入元素。因此队列是一种先入先出(FIFO)的数据结构。进行插入操作的端称为队尾，进行删除操作的端称为队头。

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。

2.注意事项

1.在循环队列中，当队列为空时，有front=rear；而当队列满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。
2.计算循环队列中的元素个数，有rear>front，元素个数为：rear-front；也有rear<fornt，这时元素个数为：(rear-fornt+MaxSize)%MaxSize。

二、C语言实现一个简单的循环队列

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Queue
{
	void** arr;
	size_t cal;
	int rear;
	int front;	
}Queue;

// 创建队列
Queue* create_queue(size_t cal)
{
	Queue* queue = malloc(sizeof(Queue));
	queue->arr = malloc(sizeof(void*)*(cal+1));
	queue->cal = cal+1;
	queue->rear = 0;
	queue->front = 0;
	
	return queue; 
}

// 销毁队列
void destroy_queue(Queue* queue)
{
	free(queue->arr);
	free(queue);
}

// 判断队列是否已满
bool full_queue(Queue* queue)
{
	return (queue->rear+1)%queue->cal == queue->front;
}

// 判断队列是否为空
bool empty_queue(Queue* queue)
{
	return queue->rear == queue->front;
}

// 入队
void push_queue(Queue* queue,void* ptr)
{
	queue->arr[queue->rear] = ptr;
	queue->rear = (queue->rear+1)%queue->cal;
}

// 出队
void pop_queue(Queue* queue)
{
	queue->front = (queue->front+1)%queue->cal;
}

// 获取对头元素
void* front_queue(Queue* queue)
{
	return queue->arr[queue->front];
}

// 获取队尾元素
void* rear_queue(Queue* queue)
{
	return queue->arr[(queue->rear-1+queue->cal)%queue->cal];
}

// 计算队列的元素数量
size_t size_queue(Queue* queue)
{
	return (queue->rear-queue->front+queue->cal)%queue->cal;
}