数据结构——队的基本操作
一、顺序队
队的用法：先进先出
跟平时我们遇到的大多情况一样，队的主要思想就是先进先出，比如我去食堂打饭，我先排那么就是我先打到饭咯
顺序队：其实说白了就是一块空间用两个指针去指向，为了实现先进先出的功能
需要注意：这里的两个指针指向，每次入队，队尾指针++，每次出队，队头指针也是++
而且入队要考虑从无到有的情况，出队要考虑从有到无的情况
1、定义
队的定义
//数据类型的定义
typedef int ElemType;
//顺序栈的定义
typedef struct Circlequeue
{
ElemType data[MAX_LEN];//直接定义一个数组
int front;//队首的下标
int rear;//队尾下标
int num;//队中元素的个数
}CQ;
需要注意的是这里的front rear num都是整型，不是指针 ，后面画图的时候，将front和rear用一条直线连向空间，不是指向哦，不是指针，只是为了表示下标的位置
2、初始化
首先创建一个空队列，使它存在
/*
函数名：InitQueue
参数列表：无
返回值：创建空队的地址
*/
CQ* InitQueue()
{
//创建一个队列，并且初始化
CQ* cq=(CQ*)malloc(sizeof(CQ));
cq->front=-1;
cq->rear=-1;
cq->num=0;
//返回队列的地址
return cq;
}
3、入队
将一个数值入队，例如：EnQueue(cq,1)
/*
函数名：EnQueue
参数列表：需要入队的队的地址@cq 要入队的元素d
返回值：成功入队返回1，失败返回0
*/
int EnQueue(CQ* cq,ElemType d)
{
//如果不能入队的情况
if(cq==NULL||cq->num==MAX_LEN)
{
return 0;
}
//入队
if(cq->num==0)
{
cq->front=(cq->front+1)%MAX_LEN;
cq->rear=(cq->rear+1)%MAX_LEN;
//只能从队尾入队
cq->data[cq->rear]=d;
}
else
{
cq->rear=(cq->rear+1)%MAX_LEN;
ca->data[ca->rear]=d;
}
cq->num++;
return 1;
}
4、出队
将一个数值出队到某一特定的空间中去（d)，例如：DeQueue(cq，&d)
/*
函数名：DeQueue
参数列表：要出队的队列@cq，出队的数据存放地址
返回值：成功返回1，失败返回0
*/
CQ* DeQueue(CQ* cq,ElemType* d)
{
if(cq==NULL||cq->num==0)
{
return 0;
}
*d=cq->data[ca->front];
cq->num--;
if(cq->num==0)
{
//假如出队出完了:队头和队尾都要重新改变
cq->front=(cq->front+1)%MAX_LEN;
cq->rear=(cq->rear+1)%MAX_LEN;
}
{
//只能从队头出队
cq->front=(cq->front+1)%MAX_LEN;
}
return 1;
}
5、求队列长度
/*
函数名：Queuelength
参数列表：传进去一个队列的地址@cq
返回值：返回队列的长度
*/
int Queuelength(CQ* cq)
{
if(cq==NULL||cq->num==0)
{
return 0;
}
return cq->num;
}
6、获取队头数据
/*
函数名：Gethead
参数列表：传进去一个队的地址@cq，还有一个存放队头数据的空间地址@&d
返回值：成功获取返回1，失败返回0
*/
ElemType Gethead(CQ* cq,ElemType* d)
{
if(cq==NULL||cq->num==0)
{
return 0;
}
*d=cq->data[ca->front];
return 1;
}
7、判断一个队列是否为空
/*
函数名：Ifempty
参数列表：传进去一个队的地址@cq
返回值：空返回1，非空返回0
*/
int Ifempty(CQ* cq)
{
if(cq==NULL||cq->num==0)
{
return 1;
}
return 0;
}
8、清空一个队
/*
函数名：Clearqueue
参数列表：传进去一个队列的地址@cq
返回值：无
*/
void Cleadqueue(CQ* cq)
{
if(cq)
{
cq->front=-1;
cq->rear=-1;
cq->num=0;
}
}
9、销毁一个顺序队
先清空，使其初始化，再释放申请的队的空间
/*
函数名：Destroyqueue
参数列表：传进去一个队列的地址@cq
返回值：无
*/
void Destroyqueue(CQ* cq)
{
//定义的时候可以互相调用
Cleadqueue(cq);
free(cq);
}
10、打印一个顺序队
/*
函数名：Print_cqueue
参数列表：传进去一个队@cq
返回值：成功打印返回1 失败返回0
*/
int Print_cqueue(CQ* cq)
{
if(cq==NULL||cq->num==0)
{
return 0;
}
ElemType d;
printf("现在顺序队开始出队，出队方式是从链头一一出：");
while(!Ifcqempty(cq))
{
//每出队一次，打印一次
Decqueue(cq,&d);
printf("%d ",d);
}
printf("\n");
return 0;
}
11、帮助理解图
二、链式队
每输入一个数据，开辟一块空间并入队，灵活存取
每出队一个数据，先保存要出队的数据，再将曾经为了保存这个数据开辟的空间释放掉，而且不能影响现有队列的结构和操作
1、链式队的定义
队中每个数据的功能先设置单一点，只能指向下一个数据，既不能双向，也不能循环
队中存放数据的数据结点的定义
typedef struct node
{
ElemType data;
struct node* next;
}
“头结点”——队的定义
typedef struct Linkqueue
{
Node* front;
Node* rear;
int num;
}LQ;
2、链式栈的初始化
/*
函数名：Initqueue
参数列表：无
返回值：返回创建好的链式队的地址
*/
LQ* Initqueue()
{
LQ* lq=(LQ*)malloc(sizeof(LQ));
lq->front=NULL;
lq->rear=NULL;
lq->num=0;
return lq;
}
3、入队
/*
函数名：Enqueue
参数列表：要入队的队列lq数值d
返回值：成功入队返回1，失败返回0
*/
int Enqueue(LQ* lq,ElemType d)
{
Node* pnew=(Node*)malloc(sizeof(Node));
pnew->data=d;
pnew->next=NULL;
if(lq==NULL)
{
return 0;
}
if(lq->num==0)
{
lq->front=pnew;
lq->rear=pnew;
}
else
{
lq->rear->next=pnew;
lq->rear=pnew;
}
lq->num++;
}
4、出队
/*
函数名：Dequeue
参数列表：出队的队列和数据lq存放的空间d
返回值：成功出队返回1 失败返回0
*/
int Dequeue(LQ* lq,ElemType* d)
{
if(lq==NULL||lq->num==0)
{
return 0;
}
//遍历删除指针
Node* px=lq->front;
*d=lq->front->data;
if(px->next==NULL)
{
//只有一个结点的时候
lq->front=NULL;
lq->next=NULL;
}
else
{
lq->front=lq->front->next;
px->next=NULL;
}
free(px;)
l->num--;
return 1;
}
5、求队列长度
/*
函数名：Queuelength
参数列表：指向队列的指针
返回值：队列长度
*/
int Queuelength(LQ* lq)
{
if(lq==NULL)
{
return 0;
}
return lq->num;
}
6、获取队头元素
/*
函数名：Gethead
参数列表：队列的地址指针lq和队首元素存放的空间d
返回值：成功返回1 失败返回0
*/
ElemType Gethead(LQ* lq,ElemType* d)
{
if(lq==NULL||lq->num==0)
{
return 0;
}
*d=lq->front->data;
return 1;
}
7、判断队列是否为空
/*
函数名：Ifempty
参数列表：传进去一个指向队列的地址lq
返回值：空返回1 非空返回0
*/
int Ifempty(LQ* lq)
{
if(lq==NULL||lq->num==0)
{
return 1;
}
return 0;
}
8、清空队列
/*
函数名：Clearqueue
参数列表：传进去指向队列的地址lq
返回值：无
*/
void Cleadqueue(LQ* lq)
{
if(lq==NULL)
{
return ;
}
//遍历清除指针
Node* px=lq->front;
while(px)
{
lq->front=lq->front->next;
px->next=NULL;
free(px);
lq->num--;
px=lq->front;
}
lq->rear=NULL;
lq->num=0;
return ;
}
9、销毁队列
/*
函数名：Destroyqueue
参数列表：传进去指向队列的地址lq
返回值：无
*/
void Destroyqueue(LQ* lq)
{
if(lq==NULL)
{
return ;
}
//遍历清除指针
Node* px=lq->front;
while(px)
{
lq->front=lq->front->next;
px->next=NULL;
free(px);
lq->num--;
px=lq->front;
}
lq->rear=NULL;
lq->num=0;
free(lq);
}
10、打印一个链式队
/*
函数名：Print_lqueue
参数列表：传进去一个队@lq
返回值：成功打印返回1 失败返回0
*/
int Print_lqueue(LQ* lq)
{
if(lq==NULL||lq->num==0)
{
return 0;
}
ElemType d;
printf("现在链式栈开始出队，出队方式是从链头一一出：");
while(!Iflqempty(lq))
{
Delqueue(lq,&d);
printf("%d ",d);
}
printf("\n");
return 0;
}
11、帮助理解图
三、主函数代码实现及运行结果演示
#include <stdio.h>
#include <stdlib.h>
#include "Treelian.h"
int main()
{
//顺序队实现:我设置了队里面最大存放个数是10
printf("现在开始验证顺序队，开辟int数据空间个数是10！\n");
CQ* cq=Initcqueue();
printf("从队尾入队：现在将2、4、6、8、10入队！\n");
//入队方式1
Encqueue(cq,2);
Encqueue(cq,4);
Encqueue(cq,6);
Encqueue(cq,8);
Encqueue(cq,10);
//入队方式2
// int d1;
// while(1)
// {
// scanf("%d",&d1);
// if(d1==0)
// {
// break;
// }
// Encqueue(cq,d1);
// }
Print_cqueue(cq);
printf("-------------------------------------------------------------------------------\n");
//链式队实现:输入一个数开辟一块空间 出队一个数释放一块空间
printf("现在开始验证链式队\n");
LQ* lq=Initlqueue();
int d2;
printf("请输入你要入队的数据（这里数据个数不做限制），规定直到输入0表示结束：\n");
while(1)
{
scanf("%d",&d2);
if(d2==0)
{
break;
}
Enlqueue(lq,d2);
}
//出队
Print_lqueue(lq);
return 0;
}
这个是gcc编译器调试结果示意图
以上是我对数据结构中栈内容的学习记录， 其中有说法不准确的地方欢迎各位朋友指出！