一.队列的概念及结构
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的性质；
入队列：进行插入操作的一端称为队尾 ；
出队列：进行删除操作的一端称为队头；
队列适合用链表来实现，入队列即尾插，出队列即头删，直接改变指针指向即可
如果用数组类实现的话，需要头删，要挪动数据，效率低；
二.队列的实现
为了方便，可以存储一个尾指针，这样尾插的时候就不需要去找尾，提高效率；
出队的时候为头删，需要改变头指针的指向，在链表的时候我们是通过二级指针来解决的，这里用一个新的方法；即将队尾指针和队头指针存放到一个结构体中，通过传结构体指针来访问头指针和尾指；同时还可以在结构体中放一个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;
}
