一.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质；
入队列：进行插入操作的一端称为队尾 ；
出队列：进行删除操作的一端称为队头；
队列适合用链表来实现，入队列即尾插，出队列即头删，直接改变指针指向即可
如果用数组类实现的话，需要头删，要挪动数据，效率低；
二.队列的实现
为了方便，可以存储一个尾指针，这样尾插的时候就不需要去找尾，提高效率；
出队的时候为头删，需要改变头指针的指向，在链表的时候我们是通过二级指针来解决的，这里用一个新的方法；即将队尾指针和队头指针存放到一个结构体中，通过传结构体指针来访问头指针和尾指；同时还可以在结构体中放一个int记录队列中有效数据的个数
typedef int QueueDateType; typedef struct QueueNode { struct Queue* next; //指向下一个的位置 QueueDateType val; //存储的数据 }QNode; //节点的结构体 typedef struct Queue { QNode* plist; //指向队头的指针 QNode* tail; //指向队尾的指针 int size; //有效数据的个数 }Que;
2.1功能函数的实现
队列一般需要这样几个功能：
- 初始化队列
- 队头入数据
- 队尾出数据
- 取队头数据
- 取队尾数据
- 获取队列中有效数据个数
- 判断队列是否为空
- 队列的销毁
1.初始化队列
void QueInit(Que* pq) { assert(pq); pq->plist = pq->tail = NULL; //先置空处理 pq->size = 0; }
2.队头入数据
void QuePush(Que* pq, QueueDateType x) { assert(pq); QNode* newnode = (QNode* )malloc(sizeof(QNode)); //创建一个节点 if (newnode == NULL) { perror("malloc fail"); //判断 exit(-1); } newnode->next = NULL; //将后节点置空处理 newnode->val = x; //赋值 if (pq->plist == NULL) //队列为空 { pq->plist= pq->tail = newnode; } else //队列不为空 { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; //有效数据个数++ }
3.队尾出数据
分为两种情况处理：
第一种：队列只有一个数据时，需要处理尾指针
第二种：队列的数据个数大于1时，不需要对尾指针进行处理
void QuePop(Que* pq) { assert(pq); assert(pq->size); //当队列为空时，不出数据 QNode* tmp = NULL; if (pq->size==1) //当队列的有效数据只有一个时，需要特殊处理 { //因为出队列后，为空列表了，尾指针需要改变 free(pq->plist); pq->plist = pq->tail == NULL; } else //队列不为空，直接头删 { tmp = pq->plist->next; //先保存下一个节点 free(pq->plist); //释放 pq->plist = tmp; } pq->size--; //有效数据个数--; }
4.取队头的数据
QueueDateType QueFront(Que* pq) { assert(pq); return pq->plist->val; //直接返回数据 }
5.取队尾的数据
QueueDateType QueBack(Que* pq) { assert(pq); return pq->tail->val; //直接返回数据 }
6.获取队列中有效数据个数
int QueSize(Que* pq) { assert(pq); return pq->size; }
7.判断队列是否为空
bool QueEmpty(Que* pq) { assert(pq); return pq->plist; }
8.销毁队列
bool QueEmpty(Que* pq) { assert(pq); return pq->plist; }
2.2总代码
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int QueueDateType; typedef struct QueueNode { struct Queue* next; QueueDateType val; }QNode; typedef struct Queue { QNode* plist; QNode* tail; int size; }Que; void QueInit(Que* pq); void QueDestory(Que* pq); void QuePush(Que* pq,QueueDateType x); void QuePop(Que* pq); QueueDateType QueFront(Que* pq); QueueDateType QueBack(Que* pq); int QueSize(Que* pq); bool QueEmpty(Que* pq);
#include"Queue.h" void QueInit(Que* pq) { assert(pq); pq->plist = pq->tail = NULL; pq->size = 0; } void QueDestory(Que* pq) { assert(pq); QNode* cur = pq->plist; QNode* Next = NULL; while (cur) { Next = cur->next; free(cur); cur =Next; } pq->plist = pq->tail == NULL; } void QuePush(Que* pq, QueueDateType x) { assert(pq); QNode* newnode = (QNode* )malloc(sizeof(QNode)); //创建一个节点 if (newnode == NULL) { perror("malloc fail"); //判断 exit(-1); } newnode->next = NULL; //将后节点置空处理 newnode->val = x; //赋值 if (pq->plist == NULL) //队列为空 { pq->plist= pq->tail = newnode; } else //队列不为空 { pq->tail->next = newnode; pq->tail = newnode; } pq->size++; //有效数据个数++ } void QuePop(Que* pq) { assert(pq); assert(pq->size); //当队列为空时，不出数据 QNode* tmp = NULL; if (pq->size==1) //当队列的有效数据只有一个时，需要特殊处理 { //因为出队列后，为空列表了，尾指针需要改变 free(pq->plist); pq->plist = pq->tail == NULL; } else //队列不为空，直接头删 { tmp = pq->plist->next; //先保存下一个节点 free(pq->plist); //释放 pq->plist = tmp; } pq->size--; //有效数据个数--; } QueueDateType QueFront(Que* pq) { assert(pq); return pq->plist->val; //直接返回数据 } QueueDateType QueBack(Que* pq) { assert(pq); return pq->tail->val; //直接返回数据 } int QueSize(Que* pq) { assert(pq); return pq->size; } bool QueEmpty(Que* pq) { assert(pq); return pq->plist; }
