数据结构——队的基本操作

一、顺序队

队的用法：先进先出

跟平时我们遇到的大多情况一样，队的主要思想就是先进先出，比如我去食堂打饭，我先排那么就是我先打到饭咯

顺序队：其实说白了就是一块空间用两个指针去指向，为了实现先进先出的功能

需要注意：这里的两个指针指向，每次入队，队尾指针++，每次出队，队头指针也是++

而且入队要考虑从无到有的情况，出队要考虑从有到无的情况

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;

}