队列相关定义
- 队列：它是一种操作受限的线性表，其限制在表的一端进行插入，另一端进行删除。
- 对尾、对头：可进行插入的一端称为队尾（rear）,可进行删除的一端称为队头（front）
- 入队、出队：向队中插入元素叫入队，新元素进入之后就称为新的队尾元素。从队中删除元素叫出队，元素出队后，其后继结点元素就称为新的队头元素。
特点：先进先出
几种队列图
一、循环队列
循环队列.png
定义
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
/* 队列结构 */
typedef struct
{
ElemType *data;
int front; /* 记录队首元素位置 */
int rear; /* 记录对尾元素位置 */
int max; /* 记录开辟内存空间的大小 */
}SqQueue;
复制代码初始化创建队列
/// 初始化创建队列
/// @param Q 队列指针
/// @param n 指定开辟空间大小，一个空间大小是 sizeof(ElemType)
Status InitQueue(SqQueue *Q, int n)
{
Q->data = malloc(sizeof(ElemType) * n);
if (Q->data == NULL) return ERROR;
Q->max = n;
Q->front = Q->rear = 0;
return OK;
}
获得元素个数
/// 获取队列元素个数(包括rear指向的空位置)
/// @param Q 队列
int GetLength(SqQueue Q)
{
return (Q.rear - Q.front + Q.max) % Q.max;
}
判断是不是空
Status QueueEmpty(SqQueue Q)
{
if (Q.front == Q.rear) {
return OK;
}
return ERROR;
}
队满
Status QueueFull(SqQueue Q)
{
if ((Q.rear+1) % Q.max == Q.front)
{
return OK;
}
else
{
return ERROR;
}
}
获得队首元素
Status GetFront(SqQueue Q, ElemType *e)
{
if (QueueEmpty(Q) == OK) {
return ERROR;
}
*e = Q.data[Q.front];
return OK;
}
入队
/// 入队操作
/// @param Q 队列
/// @param e 新数据
Status EnQueue(SqQueue *Q, ElemType e)
{
// 判断队列有没有满
if (QueueFull(*Q)) return ERROR;
Q->data[Q->rear] = e;
// 队尾向后移动，取模运算，超出队尾，实现循环继续从队首开始
Q->rear = (Q->rear+1) % Q->max;
return OK;
}
出队
/// 出队列
/// @param Q 队列
/// @param e 出的元素
Status DeQueue(SqQueue *Q, ElemType *e)
{
// 判断对了是不是空
if (QueueEmpty(*Q) == OK) return ERROR;
*e = Q->data[Q->front];
// 队首位置向后移动一位
Q->front = (Q->front+1) % Q->max;
return OK;
}
遍历输出
Status QueuePrint(SqQueue *Q)
{
/* 从队首开时输出，直到对尾 */
int i = Q->front;
while (i != Q->rear) {
printf("%d ",Q->data[i]);
i = (i+1) % Q->max;
}
printf("\n");
return ERROR;
}
测试输出
指定队列最大存储5个单元，方便观看
int main(int argc, const char * argv[]) {
SqQueue queue;
InitQueue(&queue, 5);
printf("插入数据:");
for (int i = 0; i < 30; i++) {
EnQueue(&queue, i);
}
QueuePrint(&queue);
int e ;
printf("出队:");
if (DeQueue(&queue, &e))
{
QueuePrint(&queue);
}
if (DeQueue(&queue, &e))
{
QueuePrint(&queue);
}
int frontE;
if (GetFront(queue, &frontE)) {
printf("队头：%d\n",frontE);
}
printf("插入数据:");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入数据:");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入数据:");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("插入数据:");
scanf("%d",&e);
EnQueue(&queue, e);
QueuePrint(&queue);
printf("开始清空队列\n");
ClearQueue(&queue);
QueuePrint(&queue);
DestoryQueue(&queue);
return 0;
}
二、链式队列
链式队列与循环队列的区别：
- 无需判断队列是否满了
- 在内存空间中是不连续的，而循环对列是开辟连续的内存空间
- 链式队列出队或清空队列时需要释放内存空间。
链式队列.png
老规矩先定义数据结构
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
typedef struct QueueNode {
ElemType data;
struct QueueNode *next;
} QueueNode, *QueueNodePtr;
typedef struct {
QueueNodePtr front;
QueueNodePtr rear;
} LinkQueue;
初始化
先创建一个头节点，让Q.front和Q.rear指向头节点，头节点的next为NULL
/// 初始化
Status InitQueue(LinkQueue *Q)
{
// 初始队列为空,只有头节点，不是有效数据的节点
*Q->front = *Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
if (*Q->front == NULL) return ERROR;
// 头节点的后面为空
*Q->front->next = NULL;
return OK;
}
判断队列为空
当队列为空时，恰入上图初始化的状态，只剩一个头节点，此时 Q.front == Q.rear
/// 判断是否为空
Status QueueEmpty(LinkQueue Q)
{
if (Q.front == Q.rear) return TRUE;
return FALSE;
}
进入队列
进入队列的操作，是将新元素，追加到rear指向的队尾之后，rear->next = 新元素，再将rear指向新元素，此时，新元素成为队尾。因为不受存储空间限制（内存占满另说），所以不需要一开始就判断是否队满，也没有队满的操作。
- 创建新节点p
- 追加到队尾
- 队列的rear指向p，标记成新队尾
Status EnQueue(LinkQueue *Q, ElemType e)
{
QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
if (p == NULL) return ERROR;
p->data = e;
p->next = NULL;
// 追加到队尾
*Q->rear->next = p;
// 标记成队尾
*Q->rear = p;
return OK;
}
出队列
出队列操作，是将首元节点从链队删除。
- 判断队列是否为空
- 找到队首节点head（此时已拿到节点，将该节点的data回调出去），等待删除
- 更改标记head后面的节点s为首元节点，即head->next
- 判断是否是最后一个节点，是的话，rear也指向头节点
- 释放原首节点head
Status DeQueue(LinkQueue *Q, ElemType *e)
{
if (QueueEmpty(*Q)) return ERROR;
QueueNodePtr head;
// 找到要删除的节点
head = *Q->front->next;
// 回调到函数外
*e = head->data;
// 更改头节点
*Q->front->next = head->next;
// 如果删到了队尾最后一个元素
if (*Q->rear == head)
*Q->rear = *Q->front;
// 删除临时指针指向的头节点
free(head);
return OK;
}
清空
仅清空头节点以外的全部节点，有头节点在，清空完，还能继续EnQueue()操作。又回到初始化后的状态
[图片上传中...(image-ef4e5c-1587723441456-1)]
<figcaption></figcaption>
#### 清空队列
Status ClearQueue(LinkQueue *Q)
{
if (*Q->front->next == NULL) return ERROR;
QueueNodePtr temp, p; // 首元节点
*Q->rear = *Q->front;
p = *Q->front->next;
*Q->front->next = NULL;
// 此时只有temp指向首元节点
while (p) {
temp = p;
p = p->next;
free(temp);
}
return OK;
}
销毁
销毁操作，和清空不一样，清空仅仅删除除头节点以外的所有节点，清空后还可以再入队。但是销毁已经彻底不使用，需要连头节点也一并free掉，所以代码中是从front开始，而非front->next。
已free所有的节点
/// 销毁队列
Status DestoryQueue(LinkQueue *Q)
{
if (*Q->front->next == NULL) return ERROR;
/*
说明，头节点也是个malloc开辟的，也需要释放
*/
while (*Q->front) {
*Q->rear = *Q->front->next;
free(*Q->front);
*Q->front = *Q->rear;
}
return OK;
}
获取队首
不更改队列，不破坏队列现有结构，仅查找。所以首元节的数据直接读取 Q.front->next->data，
Status GetHead(LinkQueue Q, ElemType *e)
{
if (QueueEmpty(*Q)) return ERROR;
*e = Q.front->next->data;
return OK;
}
