今日励志语句:别总听悲伤的歌,别总想从前的事,别让过去拖住脚,别让未来被辜负。
前言:前面写了一篇 栈的实现,接下来学习一下它的"兄弟"
一、队列的概念:
队列:
也是数据结构的一种,也属于特殊的线性表,是不是有点栈的味儿呢??它只允许一端插入数据,另一端删除数据,两个操作在两端进行,满足先进先出 FIFO(First In First Out )原则;因此它和它的好兄弟栈又恰恰相反,反目成仇了!
入队(Front):
进行插入操作的一端(队尾)
出队(Rear):
进行删除操作的一端(队头)
空队列:
不含任何数据
一个图就记住了!!!有点像水管,入管道的水,会先流出管道
流完了,数据也就都出去了
走安全出口,是不是先进去的先下去,后面的跟着在走,陆续出去
队列的两种写法:
①顺序队列:在顺序表的基础上实现的队列结构。
分配一块连续的存储单元存放队列中的元素,并附设两个指针:头指针 front指向队头元素,尾指针 rear 指向队尾元素的下一个位置(思考方向和栈类似,但是又有所不同)
②链队列:在链表的基础上实现的队列结构。
分配一块逻辑上连续的存储单元存放列中的元素,并设2个指针:头指针指向队头的节点,尾指针指向队尾的节点(今天来实现它)
两者的区别是在链表和顺序表的区别,在物理空间上,数据集中存储就是顺序队列,数据分散存储就是链队列;
二、设计队列和初始化队列:
设计:
先从遵循的原则出发,队列是先进先出,那么我们可以写一个单链表
头删和尾插 实现即可
节点创建:变量a就是数据 next存下一个节点的指针
但是我们发现我们要记录头和尾 ,为何不在建立一个结构体呢???专门保存头和尾
头和尾也是节点 用的类型是上面的Queue*
这个结构体的成员就是节点的集合:
头里面放了一个节点的地址,这个节点又会存放指向下一个节点的地址!!!拆开就是如此
头和尾的结构体
提醒:我是写完了,写的过程发现了应该添加数据,所以给结构体成员再添加了一份子(记录数数)
初始化:
根据设计,我们要对Queue结构体操作:无非就是给个空指针,初始化数据个数!!
三、尾插:
和单链表尾插一样的,直接开写,就是得注意不要忘记判断一下,若尾节点是NULL,说明头与尾都还没有存节点,要先存一个
四、 头删:
删除头节点,头的位置就会不断向尾靠近,当到达尾时,需要同时给head和tail赋值NULL,不然会变成野指针 “野狗”
这里q->size的作用就用到了(不止这一个作用);判断数据个数是否为0,若是0,就是2个指针都指向了NULL,千万别忘记了NULL是不能被操作的
五、取头和取尾以及返回数据个数:
我的意思是取这个队列的队头和队尾,你排队的时候,想知道到你自己还有几个人吧?尾-头=还要等待的人数
注意函数返回类型:为存储的数据类型;
顺便加个数据个数:
六、判空:
栈里面已经实现过了,万变不离其宗
若是数据个数为0,我就是传真,个数不为0,传假
七、销毁:
销毁的话,其实和单链表销毁一样,不论你有几个节点,我从头开始销毁,将所有节点所申请的空间还给操系统
销毁完以后,要注意的就是将头尾置空,毕竟被“野狗”咬一口可不好受啊
其实,在你用删除的时候,若是一个一个节点删完了,走完了 其实可以不要用到销毁这个函数,但是总有情况需要的,比如,你想清楚这个水管,把水闸关了,里面水瞬间没了(例子罢了,理解即可,勿较真)
八、分装代码实现:
Queue.h头文件
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<stdlib.h>
typedef int QUDataType;
//节点
typedef struct QueueNode{
QUDataType a;
//一定要用指针,不然结构体的大小就无法确定了
struct QueueNode *next;
}QuNode;
//再建立一个保存头和尾的结构体
typedef struct Queue {
QuNode* head;
QuNode* tail;
int size;
}Queue;
//初始化头尾节点
void QuInto(Queue* q);
//尾插
void QuPush(Queue* q,QUDataType x);
//头删
void QuPop(Queue* q);
//判空
bool QuEmpty(Queue* q);
//数据个数
int QuSize(Queue* q);
//取头数据
QUDataType QuFront(Queue* q);
//取尾数据
QUDataType QuBack(Queue* q);
//销毁空间(写进数据,想要一次性释放完就来用)
void QuDestroy(Queue* q);
Queue.c源文件
#define _CRT_SECURE_NO_WARNINGS 3
#include"Queue.h"
//初始化头尾节点
void QuInto(Queue* q)
{
//不能传空指针 即(q=NULL)
assert(q);
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
//尾插(2种情况:1.头尾都为NUL 2.又数据入队列了)
void QuPush(Queue* q, QUDataType x)
{
//申请空间
QuNode* newnode = (QuNode*)malloc(sizeof(QuNode));
//判空
if (newnode == NULL)
{
perror("malloc");
return;
}
newnode->a = x;
newnode->next = NULL;//节点创建完成
//判断尾的位置
if (q->tail == NULL)
{
q->head = q->tail = newnode;
}
else
{
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
//头删(删除到尾以后,就不能再删了)
void QuPop(Queue* q)
{
assert(q);
//头的位置也不能为空
assert(q->size!=0);
//此时数据个数为1(也就是最后一个节点)
if (q->head->next==NULL)
{
free(q->head);
q->head = q->tail = NULL;
}
else//q->head != q->tail;
{
QuNode* next = q->head->next;
free(q->head);
q->head = next;
}
//数据个数也要减去
q->size--;
}
//判空
bool QuEmpty(Queue* q)
{
assert(q);
//头尾都相等时到达同一个位置,此时就为真,其他的情况都为假;
return q->size==0;
}
//取头数据
QUDataType QuFront(Queue* q)
{
assert(q);
assert(q->head);
return q->head->a;
}
//取尾数据
QUDataType QuBack(Queue* q)
{
assert(q);
//队尾都为空了,已经没数据了
assert(q->tail);
return q->tail->a;
}
//数据个数
int QuSize(Queue* q)
{
assert(q);
return q->size;
}
//销毁空间(写进数据,想要一次性释放完就来用)
void QuDestroy(Queue* q)
{
assert(q);
QuNode* cur = q->head;
while (cur)
{
QuNode* next = cur->next;
free(cur);
cur = next;
}
q->head = q->tail =NULL;
q->size = 0;
}
tast.c源文件
#define _CRT_SECURE_NO_WARNINGS 3
#include"Queue.h"
int main()
{
Queue p;
QuInto(&p);
QuPush(&p,1);
QuPush(&p, 2);
QuPush(&p, 3);
QuPush(&p, 4);
while (!QuEmpty(&p))
{
printf("%d ", QuFront(&p));
QuPop(&p);
}
//可写可不写。因为上面循环的时候会释放掉所有申请的空间
//QuDestroy(&p);
return 0;
}
鉄汁们,你们的三连就是对博主最大的支持!!!