C语言实现循环队列——始化、入队、出队与完整测试

队列的基本操作实现

1.队列的概念

? 队列（Queue）—— 先进先出的数据结构

队列是一种线性数据结构，遵循 “先进先出”（FIFO, First In First Out） 的原则。如现实中的排队：先来的人先被服务，后来的人排在队尾等待。

? 基本操作：

  • 入队（Enqueue）：在队尾添加一个新元素。
  • 出队（Dequeue）：从队头移除一个元素。
  • 查看队头（Front）：获取队头元素，但不移除。
  • 判空（IsEmpty）：判断队列是否为空。
  • 获取大小（Size）：返回队列中元素个数。

? 存储方式：

队列可以用两种主要方式实现：

  1. 顺序存储：使用数组实现，可优化为循环队列以避免空间浪费。
  2. 链式存储：使用链表实现，动态分配内存，灵活性高。

2.链式存储--代码实现

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int DataType_t;
// 链表节点结构体（改为 QueueNode）
typedef struct QueueNode {
 DataType_t data;
 struct QueueNode* next;
} QueueNode;
// 队列的结构体（改为 LinkedQueue，表示链式队列）
typedef struct {
 QueueNode* rear; // 指向队尾节点
 int size;
} LinkedQueue;
// 为 LinkedQueue* 定义别名 Queue，表示一个队列的指针
typedef LinkedQueue* Queue;
/**
 * 初始化队列
 * @param q 指向队列指针的指针（二级指针），用于返回队列的地址
 * @return 成功返回 1，失败返回 0
 */
int InitQueue(Queue* q)
{
 if (q == NULL) return 0;
 // 申请内存存储管理队列的结构体
 *q = (Queue)malloc(sizeof(LinkedQueue));
 if (*q == NULL) return 0;
 (*q)->size = 0;
 (*q)->rear = NULL;
 return 1; 
}
/**
 * 入队操作：一个新元素入队列
 * @param q 队列指针
 * @param data 要入队列的数据
 * @return 成功返回 1，失败返回 0
 */
int EnQueue(Queue q, DataType_t data)
{
 if (q == NULL) return 0;
 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
 if (newNode == NULL) return 0;
 newNode->data = data;
 // 如果队列空
 if (q->rear == NULL) {
 newNode->next = newNode;
 q->rear = newNode;
 } else {//新节点放到尾节点之后，再更新rear指向
 newNode->next = q->rear->next;
 q->rear->next = newNode;
 q->rear = newNode;
 }
 q->size++;
 return 1;
}
// 判断队列是否空
bool IsEmpty(Queue q) {
 return q == NULL || q->rear == NULL;
}
// 计算队列元素个数
int GetSize(Queue q) {
 if (q == NULL) return -1;
 return q->size;
}
/**
 * 出队操作：
 * @param q 队列指针
 * @param data 存储出队元素的值 
 * @return 成功返回 1，失败返回 0
 */
int DeQueue(Queue q, DataType_t* data) {
 if (q == NULL || q->rear == NULL) {
 return 0; // 空队列或无效队列
 }
 QueueNode* frontNode = q->rear->next; // 队头是 rear->next
 *data = frontNode->data;
 if (q->rear == frontNode) {
 // 只有一个节点
 free(frontNode);
 q->rear = NULL;
 } else {
 // 多个节点
 q->rear->next = frontNode->next; // 跳过队头
 free(frontNode);
 }
 q->size--;
 return 1;
}
void DestroyQueue(Queue* q) {
 if (q == NULL || *q == NULL) return;
 if ((*q)->rear != NULL) {
 QueueNode* current = (*q)->rear->next; // 队头
 QueueNode* head = current;
 QueueNode* temp;
 do {
 temp = current;
 current = current->next;
 free(temp);
 } while (current != head);
 }
 free(*q);
 *q = NULL;
}
void PrintQueue(Queue q) {
 if (IsEmpty(q)) {
 printf("Queue is empty.\n");
 return;
 }
 QueueNode* current = q->rear->next; // 从队头开始
 printf("Queue (front -> rear): ");
 do {
 printf("%d ", current->data);
 current = current->next;
 } while (current != q->rear->next);
 printf("\n");
}
int main() {
 Queue myQueue;
 
 if (!InitQueue(&myQueue)) {
 printf("Failed to initialize queue.\n");
 return -1;
 }
 printf("EnQueue: 10, 20, 30\n");
 EnQueue(myQueue, 10);
 EnQueue(myQueue, 20);
 EnQueue(myQueue, 30);
 PrintQueue(myQueue);
 printf("Size: %d\n", GetSize(myQueue));
 DataType_t val;
 printf("DeQueue: ");
 while (DeQueue(myQueue, &val)) {
 printf("%d ", val);
 if (IsEmpty(myQueue)) break;
 }
 printf("\n");
 printf("After dequeue all: empty? %s\n", IsEmpty(myQueue) ? "yes" : "no");
 DestroyQueue(&myQueue);
 return 0;
}

运行结果

顺序存储--（循环队列）代码实现

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 定义队列中元素的数据类型为 int
typedef int DataType_t; 
// 循环队列结构体定义
typedef struct CircularQueue 
{
	DataType_t *Addr;	// 指向动态分配的数组，用于存储数据
	int 	 Rear;	// 队尾索引（指向下一个插入位置）
	int 	 Front;	// 队头索引（指向当前第一个元素）
	unsigned int Size;	// 队列总容量（数组大小）
}CircQueue_t;
/**
 * 初始化循环队列
 * @param size 队列的最大容量
 * @return 成功返回队列指针，失败则退出程序
 */
CircQueue_t* CircQueue_init(unsigned int size)
{
	CircQueue_t *Manager = (CircQueue_t*)calloc(1,sizeof(CircQueue_t));
	if(Manager == NULL){
	perror("calloc for Manager is failed!\n");
	exit(-1);
	}
	// 为数据数组分配内存
	Manager->Addr = (DataType_t *)calloc(size,sizeof(DataType_t));
	if(Manager->Addr == NULL){
	perror("calloc for Eelement is failed\n");
	free(Manager);
	exit(-1);
	}
	Manager->Size = size;	// 设置容量
	Manager->Rear = 0;	// 初始队尾为0
	Manager->Front = 0; 	// 初始队头为0
	return Manager; 	// 返回初始化后的队列
}
/**
 * 判断队列是否已满
 * @param Manager 队列指针
 * @return 满则返回 true，否则返回 false
 */
bool CircQueueIsfull(CircQueue_t *Manager)
{
	// 当 (Rear+1) % Size == Front 时，队满（牺牲一个空间，用空间换时间）
	return ((Manager->Rear+1)%Manager->Size == Manager->Front)?true:false;
}
/**
 * 判断队列是否为空
 * @param Manager 队列指针
 * @return 空则返回 true，否则返回 false
 */
bool CircQueueIsEmpty(CircQueue_t *Manager)
{
	 // Front == Rear 表示队列为空
	return ( Manager->Front == Manager->Rear)?true:false;
}
/**
 * 入队操作
 * @param Manager 队列指针
 * @param data 要入队的数据
 * @return 成功返回 true，失败（队满）返回 false
 */
bool CircQueue_Push(CircQueue_t *Manager,DataType_t data)
{	
	
	if(CircQueueIsfull(Manager)){
	printf("Full!\n");
	return false;
	}
	Manager->Addr[Manager->Rear] = data;	// 数据放入队尾;
	Manager->Rear = (Manager->Rear+1)%Manager->Size;	// rear 向后移动，循环
	return true;
}
/**
 * 出队操作
 * @param Manager 队列指针
 * @param data 用于保存出队的数据（通过指针返回）
 * @return 成功返回 true，失败（队空）返回 false
 */
bool CircQueue_Pop(CircQueue_t* Manager, DataType_t* data)
{
 // 检查队列是否为空
 if (CircQueueIsEmpty(Manager)) {
 printf("Empty!\n");
 return false; // 出队失败
 }
 // 取出队头元素
 *data = Manager->Addr[Manager->Front];
 // 移动队头指针：向后移动一位，模 Size 实现循环
 Manager->Front = (Manager->Front + 1) % Manager->Size;
 return true; // 出队成功
}
int main(int argc, char const *argv[])
{
 // 初始化一个大小为 3 的循环队列
 CircQueue_t* q = CircQueue_init(3);
 DataType_t val;
 // --- 测试入队 ---
 printf("=== 入队测试 ===\n");
 if (CircQueue_Push(q, 10)) {
 printf("成功入队: 10\n");
 }
 if (CircQueue_Push(q, 20)) {
 printf("成功入队: 20\n");
 }
 if (CircQueue_Push(q, 30)) {
 printf("成功入队: 30\n");
 }
 if (CircQueue_Push(q, 40)) {
 printf("成功入队: 40\n");
 } else {
 printf("入队 40 失败：循环队列队列已满！\n");
 }
 // --- 测试出队 ---
 printf("\n=== 出队测试 ===\n");
 if (CircQueue_Pop(q, &val)) {
 printf("成功出队: %d\n", val);
 }
 if (CircQueue_Pop(q, &val)) {
 printf("成功出队: %d\n", val);
 }
 // --- 测试循环入队 ---
 printf("\n=== 测试循环特性 ===\n");
 if (CircQueue_Push(q, 40)) {
 printf("成功入队: 40\n");
 }
 if (CircQueue_Push(q, 50)) {
 printf("成功入队: 50\n");
 } else {
 printf("入队 50 失败：循环队列队列已满！\n");
 }
 // --- 出队剩余元素 ---
 printf("\n=== 清空队列 ===\n");
 while (CircQueue_Pop(q, &val)) {
 printf("成功出队: %d\n", val);
 }
 printf("队列已空，测试结束。\n");
 // --- 释放资源 ---
 free(q->Addr); // 释放数据数组
 free(q); // 释放队列结构体
 return 0;
}

运行结果

作者:Yue+原文地址:https://www.cnblogs.com/YueZone/p/19022040
0
分享 2025-08-05

%s 个评论

要回复文章请先登录或注册

关于我们 • 赞助与捐赠 • 站点地图 • 联系我们 • 网站合作 • 免责声明
友情链接： 乐读文化 • 开发者 • MySQL Workbench • 大牛教程 • 交换链接
本站为个人网站，部分内容来自于互联网，版权归原作者所有。如本站内容有侵权，敬请来信联系我们，我们将及时删除清理。
© 2025 大牛教程