C++中队列的建立与操作详细解析
什么是队列结构
队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看,队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分,队列结构可以分成两类。
顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据。在程序中,可以定义一个指定大小的结构数组来作为队列。
链式队列结构:即使用链表形式保存队列中各元素的值。
在队列结构中允许对两端进行操作,但是两端的操作不同。在表的一端只能进行删除操作,称为队头;在表的另一端只能进行插入操作,称为队尾。如果队列中没有数据元素,则称之为空队列。从数据的运算角度分析,队列是按照“先进先出”的原则处理结点的。
可以将队列结构理解成是:超市排队结账的人群,排在队首的人先结账,然后不断会有人排在队尾等待结账,这就是一个先来先服务的队列的现实中的例子。
一般队列结构的基本操作只有两个:
入队列:将一个元素添加到队尾(相当于到队列最后排队等待)
出队列:将对头的元素取出,同时删除该元素,使后一个元素成为队头。
初次之外,还有初始化队列、获取队列长度的简单运算。下面,我们就是用C++建立顺序队列结构,并完成顺序队列结构的基本运算。
准备数据
准备数据就是定义在队列操作中需要用到的变量及数据结构等。
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //队列数组
int head; //队头
int tail; //队尾
};
这里,定义了队列结构的最大长度QUEUELEN ,队列结构数据元素的类型DATA以及队列结构的数据结构SQType。在数据结构SQType中,data为数据元素,head为队首的序号,tail为队尾的序号。当head=0时表示队列为空,当tail=QUEUELEN时表示队列满。
初始化队列数据
顺序队列的初始化操作步骤如下:
(1)按符号常量QUEUELEN指定的大小申请一段内存空间,用来保存队列中的数据。
(2)设置head=0和tail=0,表示一个空栈。
示例代码如下:
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申请队列的内存空间
{
q->head=0; //设置队首
q->tail=0; //设置队尾
return q;
}
else
{
return NULL; //返回空
}
}
首先使用new申请内存,申请成功以后设置队头和队尾,然后返回申请内存的首地址,如果申请失败则返回NULL。
判断空队列
判断空队列是判断一个队列结构是否为空。如果是空队列,则表示该队列结构中国没有数据。此时可以进入如队列操作,不可以进行出队列操作。
示例代码如下:
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
输入参数q为一个指向操作的队列的指针。程序中,根据队列head是否等于tail判断队列是否为空。
判断满队列
判断满队列就是判断一个队列结构是否为满。如果是满队列,则表示该队列中没有多余的空间来保存额外数据。测试不可以进行入队列操作,可以进行出队列操作。
示例代码如下:
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN)
}
输入参数q为一个指向操作的队列的指针。程序中,根据队列tail是否等于队列的最大值QUEUELEN判断队列是否是满的。
清空队列
清空队列就是清楚一个队列中的所有的数据。示例代码如下:
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
将队列顶指针head和尾指针tail设置为0,表示执行清空操作。
释放空间
释放空间是释放队列结构所占用的内存单元。由前面可知,在初始化队列结构时,使用了new关键字分配内存单元。虽然可以使用清空队列操作,但是清空队列操作并没有释放内存空间,这就需要使用delete关键字释放所占的内存单元。
示例代码如下:
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
程序中,调用了得delete释放new申请的内存空间。
入队列
入队列是队列结构的基本操作,主要操作是将数据元素保存到队列结构。入队列操作的具体步骤如下:
(1)首先判断队尾,如果tail等于QUEUELEN,则表示溢出,进行出错处理。否则执行以下操作。
(2)设置tail=tail+1(队列顶指针加1,指向入队列地址)
(3)就将入队列元素保存到tail指向的位置
示例代码如下:
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"队列已满!操作失败!"<<endl;
return 0;
}else
{
q-data[q->tail++]=data; //将元素入队列
return 1;
}
}
输入参数q为指向操作的队列的指针,输入参数data为需要入队列的数据元素。程序中首先判断队列是否溢出,如果溢出则不进行入队列操作,否则修改队列顶指针的值,再将元素入队列。
因为tail的值从0开始,当前的值就是要插入的数组对应的元素的位置,所以写成q->tail++。
出队列
出队列是队列结构的基本操作,主要操作与入队列相反,其实从队列顶弹出一个数据元素。出队列操作的具体步骤如下:
(1)首先判断队首head,如果head等于tail,则表示为空队列,进行出错处理。否则,执行下面的步骤
(2)从队列首部取出队头元素(实际返回队头元素的指针)
(3)修改队首head的序号,使其指向后一个元素。
示例代码如下:
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
cout<<"队列已空!操作失败!"<<endl;
exit(0);
}else
{
return &(q->data[q->head++]);
}
}
输入参数q为指向操作的队列的指针。该函数返回值是一个DATA类型的数据,返回值是指向该数据元素的指针。
读结点数据
读结点数据也就是读取队列结构中结点的数据,这里的读操作其实就是读队列头的数据。需要助于的是,读结点数据的操作和出队列操作不同。读结点数据的操作仅是显示队列顶结点数据的内容,而出队列操作则将队列顶数据弹出,该数据不再存在。
示例代码如下:
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空队列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
该函数返回值同样是一个DATA类型的指针数据,返回值是指向数据元素的指针。
计算队列长度
计算队列长度就是统计该队列中数据结点的个数。计算队列长度的方法比较简单,直接队尾序号减去队首序号即可。
示例代码如下:
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
队列结构操作实例代码:
完整的代码会比较长,不过函数部分和上面介绍的基本一致,主要是看main函数中这些函数的用法:
#include<iostream>
#include<string>
using namespace std;
#define QUEUELEN 10
struct DATA{
string name;
int age;
};
struct SQType
{
DATA data[QUEUELEN]; //队列数组
int head; //队头
int tail; //队尾
};
/*******************队列的初始化*************************/
SQType *SQTypeInit()
{
SQType * q;
if(q=new SQType) //申请队列的内存空间
{
q->head=0; //设置队首
q->tail=0; //设置队尾
return q;
}
else
{
return NULL; //返回空
}
}
/*******************判断空队列*************************/
int SQTypeIsEmpty(SQType *q)
{
return(q->head==q->tail);
}
/*******************判断满队列*************************/
int SQTypeIsFull(SQType *q)
{
return(q->tail==QUEUELEN);
}
/*******************清空队列*************************/
void SQTypeClear(SQType *q)
{
q->head=0;
q->tail=0;
}
/*******************释放空间*************************/
void SQTypeFree(SQType *q)
{
if(q!=NULL) delete q;
}
/*******************入队列操作*************************/
int InSQType(SQType *q,DATA data)
{
if(q->tail==QUEUELEN)
{
cout<<"队列已满!操作失败!"<<endl;
return 0;
}else
{
q->data[q->tail++]=data; //将元素入队列
return 1;
}
}
/*******************出队列操作*************************/
DATA *OutSQType(SQType *q)
{
if(q->tail==q->head)
{
return NULL;
}else
{
return &(q->data[q->head++]);
}
}
/*******************读结点数据*************************/
DATA * PeekSQType(SQType *q)
{
if(SQTypeIsEmpty(q))
{
cout<<"空队列"<<endl;
return NULL;
}else
{
return &(q->data[q->head]);
}
}
/*******************计算队列长度*************************/
int SQTypeLen(SQType *q)
{
return(q->tail-q->head);
}
/*********************主函数******************************/
int main()
{
SQType *stack;
DATA data,*p;
stack=SQTypeInit(); //执行初始化操作
cout<<"执行入队列操作:"<<endl;
cout<<"输入姓名,年龄进行入队操作:"<<endl;
while(1)
{
cin>>data.name>>data.age;
if(data.age==0)
{
break; //若输入为0,则退出
}
else
{
InSQType(stack,data);
}
}
cout<<"进行出栈操作:"<<endl;
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"读取首结点数据:"<<endl;
p=PeekSQType(stack);
cout<<p->name<<","<<p->age<<endl;
cout<<"执行出栈操作:"<<endl;
while(1)
{
if(SQTypeIsEmpty(stack))
{
cout<<"所有数据出栈完毕,栈为空!"<<endl;
break;
}else
{
p=OutSQType(stack);
cout<<p->name<<","<<p->age<<endl;
}
}
SQTypeFree(stack);
return 0;
}
程序运行界面:
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C++ string常用截取字符串方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 本篇文章主要介绍了C++中四种加密算法之AES源代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。...2020-04-25
- 整数拆分,指把一个整数分解成若干个整数的和。本文重点给大家介绍C++ 整数拆分方法详解,非常不错,感兴趣的朋友一起学习吧...2020-04-25
- 这篇文章主要介绍了C++中Sort函数详细解析,sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变...2022-08-18
- 队列的特性很简答,就是先进先出,一般利用数组来实现,本文就介绍了C#队列的简单使用,文中根据实例编码详细介绍的十分详尽,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-17
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了SpringBoot集成Redis实现消息队列的方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-10
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要为大家详细介绍了C++ Eigen库计算矩阵特征值及特征向量,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要介绍了C++ pair的用法实例详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了VSCode C++多文件编译的简单使用方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-03-29
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要给大家介绍了关于C++随机点名生成器的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- map容器是C++ STL中的重要一员,删除map容器中value为指定元素的问题是我们经常与遇到的一个问题,下面这篇文章主要给大家介绍了关于利用C++如何删除map容器中指定值的元素的相关资料,需要的朋友可以参考借鉴,下面来一起看看吧。...2020-04-25
- 这篇文章主要介绍了C++ 约瑟夫环问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-08-15
- 这篇文章主要介绍了C++中cin的用法详细,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25