目录

一、队列的定义和特点

二、循环队列

2.1 - CircularQueue.h

2.2 - CircularQueue.c

2.3 - test.c

三、链队

3.1 - LinkQueue.h

3.2 - LinkQueue.c

3.3 - test.c

一、队列的定义和特点

和栈相反，队列（queue）是一种先进先出（First In First Out, FIFO）的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾（rear），允许删除的一端则称为队头（front）。假设队列为 q = (a1, a2, ..., an)，那么 a1 就是队头元素，an 则是队尾元素。队列中的元素是按照 a1, a2, ..., an 的顺序进入的，退出队列也只能按照这个次序依次退出。

队列在程序设计中也经常出现。一个最典型的例子就是操作系统中的作业排队。在允许多道程序运行的计算机系统中，同时有几个作业运行。如果运行的结果都需要通过通道输出，那就按请求输入的先后次序排队。每当通道传输完毕可以接受新的输出任务时，队头的作业先从队列中退出做输出操作。凡是申请输出的作业都是从队尾进入队列。

二、循环队列

2.1 - CircularQueue.h

#pragma once#include 
#include // 循环队列
#define MAXQSIZE 6typedef int DataType;typedef struct CircularQueue
{DataType* data;int front;int rear;
}CircularQueue;// 基本操作
void CircularQueueInit(CircularQueue* pq);  // 初始化bool CircularQueueEmpty(CircularQueue* pq);  // 判断是否为空队列
bool CircularQueueFull(CircularQueue* pq);  // 判断队列是否满了void CircularQueuePush(CircularQueue* pq, DataType e);  // 入队
void CircularQueuePop(CircularQueue* pq);  // 出队DataType CircularQueueFront(CircularQueue* pq);  // 返回队列头元素
DataType CircularQueueBack(CircularQueue* pq);  // 返回队列尾元素int CircularrQueueSize(CircularQueue* pq);  // 获取队列中有效元素个数void CircularQueueDestroy(CircularQueue* pq);  // 销毁

2.2 - CircularQueue.c

#define _CRT_SECURE_NO_WARNINGS 1#include "CircularQueue.h"
#include 
#include // 初始化（为队列分配一个最大容量为 MAXQSIZE 的数组空间，即队列的长度为 MAXQSIZE - 1）
void CircularQueueInit(CircularQueue* pq)
{assert(pq);pq->data = (DataType*)malloc(sizeof(DataType) * MAXQSIZE);if (NULL == pq->data){perror("initialization failed!");exit(-1);}pq->front = pq->rear = 0;
}// 判断是否为空队列
bool CircularQueueEmpty(CircularQueue* pq)
{assert(pq);return pq->front == pq->rear;
}// 判断队列是否满了
bool CircularQueueFull(CircularQueue* pq)
{assert(pq);return (pq->rear + 1) % MAXQSIZE == pq->front;
}// 入队
void CircularQueuePush(CircularQueue* pq, DataType e)
{assert(pq);assert(!CircularQueueFull(pq));  // 前提是队列不满pq->data[pq->rear] = e;pq->rear = (pq->rear + 1) % MAXQSIZE;
}// 出队
void CircularQueuePop(CircularQueue* pq)
{assert(pq);assert(!CircularQueueEmpty(pq));pq->front = (pq->front + 1) % MAXQSIZE;
}// 返回队列头元素
DataType CircularQueueFront(CircularQueue* pq)
{assert(pq);assert(!CircularQueueEmpty(pq));return pq->data[pq->front];
}// 返回队列尾元素
DataType CircularQueueBack(CircularQueue* pq)
{assert(pq);assert(!CircularQueueEmpty(pq));// 方法一：/*if (pq->rear == 0)return pq->data[MAXQSIZE - 1];elsereturn pq->data[pq->rear - 1];*/// 方法二：return pq->data[(pq->rear - 1 + MAXQSIZE) % MAXQSIZE];
}// 获取队列中有效元素个数
int CircularrQueueSize(CircularQueue* pq)
{assert(pq);// 对于非循环队列，尾指针和头指针的差值便是队列的长度；// 而对于循环队列，差值可能为负数，所以需要将差值加上 MAXQSIZE，然后与 MAXQSIZE 求余。return (pq->rear - pq->front + MAXQSIZE) % MAXQSIZE;
}// 销毁
void CircularQueueDestroy(CircularQueue* pq)
{assert(pq);free(pq->data);pq->data = NULL;pq->front = pq->rear = 0;
}

2.3 - test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "CircularQueue.h"int main()
{CircularQueue q;// 初始化CircularQueueInit(&q);// 入队：1 2 3 4 5 --> 队满CircularQueuePush(&q, 1);CircularQueuePush(&q, 2);CircularQueuePush(&q, 3);CircularQueuePush(&q, 4);CircularQueuePush(&q, 5);// 出队：1 2CircularQueuePop(&q);CircularQueuePop(&q);// 入队：6 7 --> 队满CircularQueuePush(&q, 6);CircularQueuePush(&q, 7);// 出队：3 4 5 6 7while (!CircularQueueEmpty(&q)){printf("%d ", CircularQueueFront(&q));CircularQueuePop(&q);}printf("\n");// 销毁CircularQueueDestroy(&q);return 0;
}

三、链队

链队是指采用链式存储结构实现的队列。通常链队用单链表来表示，如下图所示。

一个链队显然需要两个分别指示队头和队尾的指针（分别称为头指针和尾指针）才能唯一确定。队列的链式存储结构表示如下：

typedef struct QueueNode
{DataType data;struct QueueNode* next;
}QueueNode;
​
typedef struct
{QueueNode* front;  // 队头指针QueueNode* rear;  // 队尾指针int size;
}LinkQueue;

3.1 - LinkQueue.h

#pragma once#include 
#include // 链队
typedef int DataType;typedef struct QueueNode
{DataType data;struct QueueNode* next;
}QueueNode;typedef struct
{QueueNode* front;  // 队头指针QueueNode* rear;  // 队尾指针int size;
}LinkQueue;// 基本操作
void LinkQueueInit(LinkQueue* pq);  // 初始化bool LinkQueueEmpty(LinkQueue* pq);  // 判断是否为空队列void LinkQueuePush(LinkQueue* pq, DataType e);  // 入队
void LinkQueuePop(LinkQueue* pq);  // 出队DataType LinkQueueFront(LinkQueue* pq);  // 返回队头元素
DataType LinkQueueBack(LinkQueue* pq);  // 返回队尾元素int LinkQueueSize(LinkQueue* pq);  // 获取队列中有效元素个数void LinkQueueDestroy(LinkQueue* pq);  // 销毁

3.2 - LinkQueue.c

#define _CRT_SECURE_NO_WARNINGS 1#include "LinkQueue.h"
#include 
#include // 初始化
void LinkQueueInit(LinkQueue* pq)
{assert(pq);pq->front = pq->rear = NULL;pq->size = 0;
}// 判断是否为空队列
bool LinkQueueEmpty(LinkQueue* pq)
{assert(pq);return pq->size == 0;
}// 入队
void LinkQueuePush(LinkQueue* pq, DataType e)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (NULL == newnode){perror("malloc failed!");return;}newnode->data = e;newnode->next = NULL;if (LinkQueueEmpty(pq))  // 如果队列为空{pq->front = pq->rear = newnode;}else{pq->rear->next = newnode;pq->rear = newnode;}++pq->size;
}// 出队
void LinkQueuePop(LinkQueue* pq)
{assert(pq);assert(!LinkQueueEmpty(pq));  // 前提是队列不为空if (pq->size == 1){free(pq->front);pq->front = pq->rear = NULL;}else{QueueNode* tmp = pq->front;pq->front = pq->front->next;free(tmp);}--pq->size;
}// 返回队头元素
DataType LinkQueueFront(LinkQueue* pq)
{assert(pq);assert(!LinkQueueEmpty(pq));return pq->front->data;
}// 返回队尾元素
DataType LinkQueueBack(LinkQueue* pq)
{assert(pq);assert(!LinkQueueEmpty(pq));return pq->rear->data;
}// 获取队列中有效元素个数
int LinkQueueSize(LinkQueue* pq)
{assert(pq);return pq->size;
}// 销毁
void LinkQueueDestroy(LinkQueue* pq)
{assert(pq);QueueNode* cur = pq->front;while (cur != NULL){QueueNode* tmp = cur;cur = cur->next;free(tmp);}pq->front = pq->rear = NULL;pq->size = 0;
}

3.3 - test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "LinkQueue.h"int main()
{LinkQueue q;// 初始化LinkQueueInit(&q);// 入队：1 2 3 4LinkQueuePush(&q, 1);LinkQueuePush(&q, 2);LinkQueuePush(&q, 3);LinkQueuePush(&q, 4);printf("当前队列中有效元素个数为：%d\n", LinkQueueSize(&q));  // 4// 出队：1 2 3 4while (!LinkQueueEmpty(&q)){printf("%d ", LinkQueueFront(&q));LinkQueuePop(&q);}printf("\n");// 销毁LinkQueueDestroy(&q);return 0;
}