当前位置:  编程技术>c/c++/嵌入式

C++中队列的建立与操作详细解析

    来源: 互联网  发布时间:2014-10-22

    本文导语:  什么是队列结构 队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看,队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分,队列结构可以分成两类。 顺序队...

什么是队列结构

队列结构是从数据运算来分类的,也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看,队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分,队列结构可以分成两类。

顺序队列结构:即使用一组地址连续的内存单元依次保存队列中的数据。在程序中,可以定义一个指定大小的结构数组来作为队列。

链式队列结构:即使用链表形式保存队列中各元素的值。

在队列结构中允许对两端进行操作,但是两端的操作不同。在表的一端只能进行删除操作,称为队头;在表的另一端只能进行插入操作,称为队尾。如果队列中没有数据元素,则称之为空队列。从数据的运算角度分析,队列是按照“先进先出”的原则处理结点的。

可以将队列结构理解成是:超市排队结账的人群,排在队首的人先结账,然后不断会有人排在队尾等待结账,这就是一个先来先服务的队列的现实中的例子。

一般队列结构的基本操作只有两个:

入队列:将一个元素添加到队尾(相当于到队列最后排队等待)

出队列:将对头的元素取出,同时删除该元素,使后一个元素成为队头。

初次之外,还有初始化队列、获取队列长度的简单运算。下面,我们就是用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)
 {
  couthead)
 {
  couttail=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)
 {
  couthead)
 {
  return NULL;  
 }else
 {
  return &(q->data[q->head++]);
 }
}
/*******************读结点数据*************************/
DATA * PeekSQType(SQType *q)
{
 if(SQTypeIsEmpty(q))
 {
  couthead); 
}
/*********************主函数******************************/
int main()
{
 SQType *stack;
 DATA data,*p;
 stack=SQTypeInit();     //执行初始化操作
 cout

    
 
 

您可能感兴趣的文章:

  • C++ Queues(队列) 成员 size():返回队列中元素的个数
  • Linux下使用C++互斥访问文件+消息队列
  • C++ Double Ended Queues(双向队列) 成员 Operators:比较和赋值双向队列
  • 解析C++无锁队列的实现代码
  • C++ Double Ended Queues(双向队列) 成员 resize():改变双向队列的大小
  • C++中用两个标准容器stack,实现一个队列的方法详解
  • C++ Double Ended Queues(双向队列) 成员 swap():和另一个双向队列交换元素
  • 用C++实现队列的程序代码
  • C++ Queues(队列) 成员 empty():如果队列空则返回真
  • C++ Priority Queues(优先队列) 成员 size():返回优先队列中拥有的元素的个数
  • C++ Double Ended Queues(双向队列) 成员 size():返回双向队列中元素的个数
  • C++ Double Ended Queues(双向队列) 成员 assign():设置双向队列的值
  • C++ Double Ended Queues(双向队列) 成员 get_allocator():返回双向队列的配置器
  • C++ Priority Queues(优先队列) 成员 top():返回优先队列中有最高优先级的元素
  • C++ Double Ended Queues(双向队列) 成员 insert():插入一个元素到双向队列中
  • C++ Double Ended Queues(双向队列) 成员 max_size():返回双向队列能容纳的最大元素个数
  • C++ Double Ended Queues(双向队列) 成员 Constructors:创建一个新双向队列
  • C++ Priority Queues(优先队列) 成员 pop():删除第一个元素
  • C++ Queues(队列) 成员 push():在末尾加入一个元素
  • C++ Queues(队列) 成员 pop():删除第一个元素
  • C++ Queues(队列) 成员 back():返回最后一个元素
  • 解析如何用两个栈来实现队列的方法
  •  
    本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
    本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • C++ Double Ended Queues(双向队列) 成员 front():返回第一个元素
  • 线程对定长队列和不定长队列的操作
  • C++ Queues(队列) 成员 front():返回第一个元素
  • unix下一个关于消息队列的问题
  • C++ Double Ended Queues(双向队列) 成员 rend():返回指向头部的逆向迭代器
  • linux 消息队列长度的问题
  • C++ Double Ended Queues(双向队列) 成员 rbegin():返回指向尾部的逆向迭代器
  • liunx 消息队列的问题
  • C++ Double Ended Queues(双向队列) 成员 begin():返回指向第一个元素的迭代器
  • 如何得到网络接口的输出队列的长度?
  • NOSQL iis7站长之家
  • 优先级队列服务 httprique
  • C++ Double Ended Queues(双向队列) 成员 pop_front():删除头部的元素
  • 请教:写入队列消息的长度问题
  • C++ Double Ended Queues(双向队列) 成员 push_front():在头部加入一个元素
  • linux下消息队列不阻塞
  • C++ Double Ended Queues(双向队列) 成员 push_back():在尾部加入一个元素
  • 有关tasklet和工作队列的问题
  • C++ Double Ended Queues(双向队列) 成员 empty():返回真如果双向队列为空
  • 简单消息队列服务 HTTPSQS
  • C++ Double Ended Queues(双向队列) 成员 erase():删除一个元素
  • 关于后台服务进程不能读消息队列的问题?200分求答急急。。。




  • 特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3