【数据结构】队列篇

1.队列

1.1 队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称尾队头。

2. 队列的实现

队列和栈一样，既可以用数组来实现也可以用链表来实现，不过因为队列不仅会用到队尾还会用到队头的特性，用链表来实现更优一些，用数组会降低效率。
入队演示

出队演示

2.1 准备工作

创建两个结构体，一个结构体用来维护队列的节点，一个结构体用来维护队列的首尾。
还可以在queue中再维护一个size，用来记录链表的节点数量。当然这里我没有这样写

#define Datatype int
//节点，维持队列的节点
typedef struct Node
{Datatype data;struct Node* next;
}Node;//队列，维护队列的头和尾
typedef struct Queue
{Node* front;Node* tail;
}Queue;

2.2 队列的初始化

因为初始时是没有节点的，把队列的首尾都初始化尾NULL

//初始化
void InitQueue(Queue* pq)
{assert(pq);pq->front = NULL;pq->tail = NULL;
}

2.3 队尾入队列

创建节点后开始判断，如果当前节点为空，那么我们就把队列的头和尾都指向这个新创建的节点。
如果队列已经有节点了，那么我们就把它链接的队尾的next，然后再更新队尾指针。

//队尾入队列
void PushQueue(Queue* pq, Datatype x)
{assert(pq);//创建节点Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL)//如果队列为空{//此时队头和队为指向同一节点pq->front = newnode;pq->tail = newnode;}else{pq->tail->next = newnode;//更新队尾指针pq->tail = newnode;}
}

2.4 队头出队列

出队列就是要删除嘛，不能是空的，为此我们加一个断言就好了。
删除队列节点时，因为是队首节点，删它前我们先要找到队首节点的下一个节点以防链表丢失，然后更新队首指针。
注意：如果队列就只有一个节点，再删除后要感谢队首和队尾指针。
。

//队头出队列
void PopQueue(Queue* pq)
{assert(pq);assert(pq->front);//防止队列为空if (pq->front == pq->tail){free(pq->front);pq->front = pq->tail = NULL;return;}Node* cur = pq->front->next;free(pq->front);pq->front = cur;
}

2.5 获取队列头部元素

因为队首指针存在，直接返回队首指针指向节点的值。

//获取队列头部元素
Datatype FrontQueue(Queue* pq)
{assert(pq);assert(pq->front);return pq->front->data;
}

2.6 获取队列队尾元素

因为队尾指针存在，直接返回队尾指针指向节点的值。

//获取队列队尾元素
Datatype BackQueue(Queue* pq)
{assert(pq);assert(pq->tail);return pq->tail->data;
}

2.7 获取队列有效元素个数

因为在准备阶段我们并没有用队列维护一个size，所以这里要遍历队列来求有效元素的个数。

//获取队列有效元素个数
int SizeQueue(Queue* pq)
{assert(pq);int sz = 0;Node* cur = pq->front;while (cur){sz += 1;cur = cur->next;}return sz;
}

2.8 检测队列是否为空

检测队列是否为空，如果为空返回真,否则返回假，注意别搞反了！

//检测队列是否为空，如果为空返回真,否则返回假
bool EmptyQueue(Queue* pq)
{assert(pq);return pq->front == NULL;
}

2.9 销毁队列

使用了动态内存一定要记得销毁，不然会有内存泄漏的~

//销毁队列
void DestoryQueue(Queue* pq)
{assert(pq);Node* cur = pq->front;while (cur){Node* next = cur->next;free(cur);cur = NULL;cur = next;}
}

3. 代码整合

//queue.h
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>#define Datatype int
//节点，维持队列的节点
typedef struct Node
{Datatype data;struct Node* next;
}Node;//队列，维护队列的头和尾
typedef struct Queue
{Node* front;Node* tail;
}Queue;//初始化
void InitQueue(Queue* pq);//队尾入队列
void PushQueue(Queue* pq, Datatype x);//队头出队列
void PopQueue(Queue* pq);//获取队列头部元素
Datatype FrontQueue(Queue* pq);//获取队列队尾元素
Datatype BackQueue(Queue* pq);//获取队列有效元素个数
int SizeQueue(Queue* pq);//检测队列是否为空，如果为空返回真,否则返回假
bool EmptyQueue(Queue* pq);//销毁队列
void DestoryQueue(Queue* pq);//queue.c
#include "queue.h"//初始化
void InitQueue(Queue* pq)
{assert(pq);pq->front = NULL;pq->tail = NULL;
}//队尾入队列
void PushQueue(Queue* pq, Datatype x)
{assert(pq);//创建节点Node* newnode = (Node*)malloc(sizeof(Node));if (newnode == NULL){perror("malloc");exit(-1);}newnode->data = x;newnode->next = NULL;if (pq->tail == NULL)//如果队列为空{//此时队头和队为指向同一节点pq->front = newnode;pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}
}//队头出队列
void PopQueue(Queue* pq)
{assert(pq);assert(pq->front);if (pq->front == pq->tail){free(pq->front);pq->front = pq->tail = NULL;return;}Node* cur = pq->front->next;free(pq->front);pq->front = cur;
}//获取队列头部元素
Datatype FrontQueue(Queue* pq)
{assert(pq);assert(pq->front);return pq->front->data;
}//获取队列队尾元素
Datatype BackQueue(Queue* pq)
{assert(pq);assert(pq->tail);return pq->tail->data;
}//获取队列有效元素个数
int SizeQueue(Queue* pq)
{assert(pq);int sz = 0;Node* cur = pq->front;while (cur){sz += 1;cur = cur->next;}return sz;
}//检测队列是否为空，如果为空返回真,否则返回假
bool EmptyQueue(Queue* pq)
{assert(pq);return pq->front == NULL;
}//销毁队列
void DestoryQueue(Queue* pq)
{assert(pq);Node* cur = pq->front;while (cur){Node* next = cur->next;free(cur);cur = NULL;cur = next;}
}//test.c
#include "queue.h"void test1()
{//Queue q;//InitQueue(&q);//PushQueue(&q,1);//PushQueue(&q,2);//PushQueue(&q,3);//PushQueue(&q,4);//printf("%d\n", SizeQueue(&q));//printf("%d\n", BackQueue(&q));//printf("%d\n", FrontQueue(&q));//DestoryQueue(&q);
}
int main()
{test1();return 0;
}

完