当前位置：首页 > 资讯 > 技术文档

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

时间：2022-06-11 05:49 编辑：来源：阅读：
扫一扫，手机访问

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

[b]什么是队列结构[/b] 队列结构是从数据运算来分类的，也就是说队列结构具有特殊的运算规则。而从数据的逻辑结构来看，队列结构其实就是一种线性结构。如果从数据的存储结构来进一步划分，队列结构可以分成两类。 [b]顺序队列结构：[/b]即使用一组地址连续的内存单元依次保存队列中的数据。在程序中，可以定义一个指定大小的结构数组来作为队列。 [b]链式队列结构：[/b]即使用链表形式保存队列中各元素的值。在队列结构中允许对两端进行操作，但是两端的操作不同。在表的一端只能进行删除操作，称为队头；在表的另一端只能进行插入操作，称为队尾。如果队列中没有数据元素，则称之为空队列。从数据的运算角度分析，队列是按照“先进先出”的原则处理结点的。可以将队列结构理解成是：超市排队结账的人群，排在队首的人先结账，然后不断会有人排在队尾等待结账，这就是一个先来先服务的队列的现实中的例子。 [b]一般队列结构的基本操作只有两个：[/b] [b]入队列：[/b]将一个元素添加到队尾（相当于到队列最后排队等待） [b]出队列：[/b]将对头的元素取出，同时删除该元素，使后一个元素成为队头。初次之外，还有初始化队列、获取队列长度的简单运算。下面，我们就是用C++建立顺序队列结构，并完成顺序队列结构的基本运算。准备数据准备数据就是定义在队列操作中需要用到的变量及数据结构等。

[u]复制代码[/u] 代码如下:

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时表示队列满。 [b]初始化队列数据[/b] 顺序队列的初始化操作步骤如下：（1）按符号常量QUEUELEN指定的大小申请一段内存空间，用来保存队列中的数据。（2）设置head=0和tail=0，表示一个空栈。示例代码如下：

[u]复制代码[/u] 代码如下:

SQType *SQTypeInit()
{
 SQType * q;
 if(q=new SQType)    //申请队列的内存空间
 {
  q->head=0;     //设置队首 
  q->tail=0;     //设置队尾
  return q;
 }
 else
 {
  return NULL;    //返回空
 }
}

首先使用new申请内存，申请成功以后设置队头和队尾，然后返回申请内存的首地址，如果申请失败则返回NULL。 [b]判断空队列[/b] 判断空队列是判断一个队列结构是否为空。如果是空队列，则表示该队列结构中国没有数据。此时可以进入如队列操作，不可以进行出队列操作。示例代码如下：

[u]复制代码[/u] 代码如下:

int SQTypeIsEmpty(SQType *q)
{
 return(q->head==q->tail);
}

输入参数q为一个指向操作的队列的指针。程序中，根据队列head是否等于tail判断队列是否为空。 [b]判断满队列[/b] 判断满队列就是判断一个队列结构是否为满。如果是满队列，则表示该队列中没有多余的空间来保存额外数据。测试不可以进行入队列操作，可以进行出队列操作。示例代码如下：

[u]复制代码[/u] 代码如下:

int SQTypeIsFull(SQType *q)
{
 return(q->tail==QUEUELEN)
}

输入参数q为一个指向操作的队列的指针。程序中，根据队列tail是否等于队列的最大值QUEUELEN判断队列是否是满的。 [b]清空队列[/b] 清空队列就是清楚一个队列中的所有的数据。示例代码如下：

[u]复制代码[/u] 代码如下:

void SQTypeClear(SQType *q)
{
 q->head=0;
 q->tail=0;
}

将队列顶指针head和尾指针tail设置为0，表示执行清空操作。 [b]释放空间[/b] 释放空间是释放队列结构所占用的内存单元。由前面可知，在初始化队列结构时，使用了new关键字分配内存单元。虽然可以使用清空队列操作，但是清空队列操作并没有释放内存空间，这就需要使用delete关键字释放所占的内存单元。示例代码如下：

[u]复制代码[/u] 代码如下:

void SQTypeFree(SQType *q)
{
 if(q!=NULL) delete q;
} 

程序中，调用了得delete释放new申请的内存空间。 [b]入队列[/b] 入队列是队列结构的基本操作，主要操作是将数据元素保存到队列结构。入队列操作的具体步骤如下：（1）首先判断队尾，如果tail等于QUEUELEN，则表示溢出，进行出错处理。否则执行以下操作。（2）设置tail=tail+1（队列顶指针加1，指向入队列地址）（3）就将入队列元素保存到tail指向的位置示例代码如下：

[u]复制代码[/u] 代码如下:

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++。 [b]出队列[/b] 出队列是队列结构的基本操作，主要操作与入队列相反，其实从队列顶弹出一个数据元素。出队列操作的具体步骤如下：（1）首先判断队首head，如果head等于tail，则表示为空队列，进行出错处理。否则，执行下面的步骤（2）从队列首部取出队头元素（实际返回队头元素的指针）（3）修改队首head的序号，使其指向后一个元素。示例代码如下：

[u]复制代码[/u] 代码如下:

DATA *OutSQType(SQType *q)
{
 if(q->tail==q->head)
 {
  cout<<"队列已空！操作失败！"<<endl;
  exit(0);  
 }else
 {
  return &(q->data[q->head++]);
 }
}

输入参数q为指向操作的队列的指针。该函数返回值是一个DATA类型的数据，返回值是指向该数据元素的指针。 [b]读结点数据[/b] 读结点数据也就是读取队列结构中结点的数据，这里的读操作其实就是读队列头的数据。需要助于的是，读结点数据的操作和出队列操作不同。读结点数据的操作仅是显示队列顶结点数据的内容，而出队列操作则将队列顶数据弹出，该数据不再存在。示例代码如下：

[u]复制代码[/u] 代码如下:

DATA * PeekSQType(SQType *q)
{
 if(SQTypeIsEmpty(q))
 {
  cout<<"空队列"<<endl;
  return NULL; 
 }else
 {
  return &(q->data[q->head]);
 }

}

该函数返回值同样是一个DATA类型的指针数据，返回值是指向数据元素的指针。 [b]计算队列长度[/b] 计算队列长度就是统计该队列中数据结点的个数。计算队列长度的方法比较简单，直接队尾序号减去队首序号即可。示例代码如下：

[u]复制代码[/u] 代码如下:

int SQTypeLen(SQType *q)
{
 return(q->tail-q->head); 
}

队列结构操作实例代码：完整的代码会比较长，不过函数部分和上面介绍的基本一致，主要是看main函数中这些函数的用法：

[u]复制代码[/u] 代码如下:

#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;
}

程序运行界面： [img]http://files.jb51.net/file_images/article/201310/20131001193310984.png[/img]

全部评论(0)

上一篇：div+CSS 兼容小摘
下一篇：用css实现隐藏文本框

资讯排行榜
更多>>