C语⾔数据结构--队列C语⾔数据结构--队列
基本概念
队列是⼀种 先进先出(FIFO)的线性表
顾名思义，就和排队⼀样，先加⼊队伍的⼈先离开队伍，后加⼊队伍的⼈后离开队伍
队列只允许在队尾插⼊元素，在队头删除元素
既然队列是线性表的⼀种，那么肯定也有两种存储形式
链队列 ——链式映像
循环队列——顺序映像
栈⼀般使⽤顺序表来实现，队列⼀般使⽤链表实现，即链队列
链队列
原理
⽤链表表⽰的队列简称为链队列
⼀个链队列需要两个分别指⽰对头和队尾的阵阵才能唯⼀确定。
基本操作
队列的链式存储结构
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ERROR -1;
#define OK 1;
typedef char QElemType;
typedef struct QNode{//结点类型
QElemType data;//队列中结点的数据域
struct QNode *next;//结点的指针域
}QNode,*QueuePtr;
typedef struct{//链队列类型
QueuePtr front;//队头指针
QueuePtr rear;//队尾指针
}LinkQueue;
注意，我们队头指针指向链队列的头结点，队尾指针指向终端结点（虽然头结点不是必须，但为了⽅便操作，我们⼀般加上头结点）初始化队列InitQueue
⽰意图：
代码
LinkQueue *InitQueue(){
LinkQueue *Q =(LinkQueue *)malloc(sizeof(LinkQueue));
Q->front = Q->rear =(QueuePtr)malloc(sizeof(QNode));
Q->front->next =NULL;
printf("初始化队列成功！\n");
return Q;
}
⼊队列EnQueue
⼊队列是从队尾插⼊元素，就像排队，肯定是从队尾排队。
如何到队尾呢？
这就要⽤到队尾指针了。
⽰意图：
代码
/**
* ⼊队列
* 1. 创建⼀个新结点分配内存
* 2. 初始化新结点
* 3. 插⼊新结点并移动队尾指针
*/
Status EnQueue(LinkQueue *Q, QElemType *e){
//创建⼀个新结点并分配内存
QueuePtr T =(QueuePtr)malloc(sizeof(QNode));
if(!T){
printf("分配内存失败!");
exit(OVERFLOW);
}
//初始化新结点
T->data = e;
T->next =NULL;
/
/插⼊新结点并移动队尾指针
Q->rear->next = T;
Q->rear = T;
return OK;
}
注意
代码⾥有⼀段代码
Q->rear->next = T;//将新元素插⼊到队列末尾
Q->rear = T;//队尾指针移动位置
我刚开始直接使⽤ Q->rear = p；错过了前⾯⼀步。前⾯的⼀步是必不可少的。
因为第⼀步代码是先将队列插⼊，第⼆步是移动队尾指针位置，两者并不重复。都很重要。出队列DeQueue
思考思路：
1）判断是否为空队列
2）出队列即从队头删除元素，是不是似曾相识的感觉，没错，出栈和出队列的原理⼏乎相同。⽰意图：
程序
/**
* 出队列
* 1. 判断队列是否为空
* 2. 删除队⾸元素
* 3. 如果刚刚删除的是最后⼀个元素，将该队列置空
* 4. 释放空间
*/
Status DeQueue(LinkQueue *Q, QElemType *e){
QueuePtr p;
//判断队列是否为空
if(Q->front == Q->rear){
printf("队列为空！");
exit(OVERFLOW);
}
/
/删除队⾸元素
p = Q->front->next;
*e = p->data;
Q->front->next = p->next;
//如果刚刚删除的是最后⼀个元素，将该队列置空
if(Q->rear == p){
Q->rear = Q->front;//这⾥⽆所谓顺序，也可以写成 Q->front = Q->rear
}
free(q);
return OK;
}
注意：
当在删除最后⼀个元素后，需要使队列置空
sizeof 指针//如果刚刚删除的是最后⼀个元素，将该队列置空
if(Q->rear == p){
Q->rear = Q->front;//这⾥⽆所谓顺序，也可以写成 Q->front = Q->rear
}
销毁队列
链队列建⽴在内存的动态区，因此当队列不再有⽤时，应当及时销毁队列，以免占⽤内存空间。程序
void DestroyQueue(LinkQueue *Q){
while(Q->front){
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
}
输出队列元素
程序
/**
* 输出队列
* 1. 判断队列是否已空
* 2. 遍历队列，移动指针
*/
void display(LinkQueue *Q){
QueuePtr temp = Q->front;
if(Q->front == Q->rear){
printf("队列已空！");
exit(OVERFLOW);
}
while(temp != Q->rear){
printf("%d    ",temp->next->data);
temp = temp->next;
}
printf("\n");
}
链队列基本操作代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef int Status;
typedef int QElemType;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct LinkQueue{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
/**
* 创建⼀个队列
* 1. 在内存创建⼀个头结点
* 2. 分配内存失败情况
* 3. 将队列的头指针和尾指针指向这个⽣成的头结点，此时是空队列 */
Status InitQueue(LinkQueue *Q){
Q->front = Q->rear =(QNode *)malloc(sizeof(QNode));
if(!Q ){
printf("分配内存失败");
exit(OVERFLOW);
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。