顺序队列的C++实现

队列同栈类似,它也是一种具有局限性的线性表.

我们在以前讲过,栈是一个后进先出结构,因为我们只能从一个方向(头或者尾)上添加(压栈)或删除(出栈)元素的操作.而队列却与此不同,该结构的最大特点就是只能从一头出,另一头进,那么会导致先添加进去的元素会先读出来,所以该结构是一个先进先出的结构.在这里我们分析由顺序表构成的队列结构,为了最大承度的应用顺序表空间以及对队列的插入和删除操作为一个常量时间,所以我们要定义两个索引:first和last,用于表示数据的插入以及删除位置(注意first位置中有数据,但是last位置中始终指向一个空元素的位置).为了方便区分队列空以及满时的情况以及可以实现循环队列,我们要进行对first和last进行运算以实现一些功能,而队列中最多可以容纳的元素个数则由size指定,还有一个域count用于表示当前任何时刻有多少个元素.那么:使first以及last加一的操作由下面的两个表达式完成:
(first+1)%size
(last+1)%size
上面的式子用于插入以及删除元素的成员函数中.
而队列是否满则用下面的表达式的逻辑值来决定:
count==size
上面的式子表示当前元素个数与队列内存大小相同时,表示队列已满.
那么当前元素个数则用count值得到.
上面的几个表达式一定要记住.实现这个数据结构我们使用了三个文件,Queue.h文件用于定义一个纯虚类Queue,它封装了队列的典型功能;而AQueue.h文件用于定义AQueue类,它实现了队列数据结构的功能;AQueue.cpp文件却实现了AQueue类的成员函数以及对该类的测试;下面是三个文件的源代码:
Queue.h文件:
////////////////////////////////////////////////////////////////////
//Queue.h文件:一个纯虚类,用于定义队列可以执行的典型操作.
////////////////////////////////////////////////////////////////////
template <class type>
class Queue
{
public:
virtual void Clear() =0;   //清空队列中的所有数值.
virtual bool AddValue(const type&) =0; //从队列尾中添加数值.
virtual bool DelValue(type&) =0;  //从队列头中删除数值.
virtual bool GetValue(type&) =0;  //得到队列头的值.
virtual int Length() =0;   //得到队列中有多少个元素.
};

AQueue.h文件:
////////////////////////////////////////////////////////////////////
//AQueue.h文件:用于定义一个AQueue类,它实现了队列数据结构.队列同样是
//一个具有局限的线性表,这一点与栈类似.但是与栈不同的是一队像人们排的
//队一样,要一边进,一边出.即队列是一个先进先出的结构.这个类是用于实现
//顺序表类型的队列.
////////////////////////////////////////////////////////////////////
#include "Queue.h"
template <class type>
class AQueue :public Queue<type>
{
public:
AQueue(int =50);
~AQueue();
void Clear();
bool AddValue(const type &);
bool DelValue(type &);
bool GetValue(type &);
int Length();
private:
int count;    //队列中有多少个元素.
int size;    //队列中最多可容邪纳的元素个数.
int first;    //队列头,删除数值以这个值作为索引.
int last;    //队列尾,插入数值以为个值作为索引.
type *listArray;   //队列的内存块.
};

AQueue.cpp文件:
////////////////////////////////////////////////////////////////////
// AQueue.cpp 文件:用于实现AQueue类的成员函数以及对该类的测试.
////////////////////////////////////////////////////////////////////
#include <iostream>
#include "AQueue.h"
using namespace std;
////////////////////////////////////////////////////////////////////
//实现对AQueue类的成员函数的定义.
////////////////////////////////////////////////////////////////////
template <class type>
AQueue<type>::AQueue(int n)
{
size=n;
first=last=count=0;  //创建一个空队列.
listArray = new type[size]; //空间的分配.
}
template <class type>
AQueue<type>::~AQueue()
{
delete [] listArray;  //删除空间.
}
template <class type>
void AQueue<type>::Clear()
{
first=last=count=0;  //空队列创建.
}
template <class type>
bool AQueue<type>::AddValue(const type &val)
{
if(count==size)
  return false;  //队列已满,不能再添加.
listArray[last]=val;  //将新值添加进队列尾部.
last=(last+1)%size;  //将尾索引加一.用以空出一个位置保存新值.
count++;
return true;
}
template <class type>
bool AQueue<type>::DelValue(type &val)
{
if(count==0)
  return false;  //如果队列已空,那么不能再删除了.
val=listArray[first];  //得到头元素的值,并返回.
first=(first+1)%size;  //使first加一.
count--;
return true;
}
template <class type>
bool AQueue<type>::GetValue(type &val)
{
if(count==0)
  return false;  //如果队列已空,那么不能得到值了.
val=listArray[first];  //否则返回头节点索引的值.
return true;
}
template <class type>
int AQueue<type>::Length()
{
return count;
}
////////////////////////////////////////////////////////////////////
//下面是一个测试程序,用于测试队列数据结构的工作情况.
////////////////////////////////////////////////////////////////////
int _tmain(int argc, _TCHAR* argv[])
{
int len,num;
AQueue<int> value(20);
value.Clear();   //清空队列,用于清除队列中的所有元素值.
value.AddValue(1);
value.AddValue(2);
value.AddValue(3);  //插入三个数值.
len=value.Length();  //得到队列中元素的总数.
for(int i=0;i<len;i++)
{
  value.DelValue(num);
  cout<<num<<"  ";
}
cout<<endl;
value.Clear();   //清空队列.
value.AddValue(1);
value.AddValue(2);
value.AddValue(3);
value.AddValue(4);

len=value.Length();
for(int i=0;i<len;i++)
{
  value.GetValue(num);
  cout<<num<<"  ";
  value.DelValue(num);
  cout<<num<<"  ";
}
cout<<endl;
return 0;
}

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1744.html 转载请保留链接。