队列的数组和链式实现

#include "stdafx.h"
#include
#include
using namespace std;

/****************
*(1)队列的数组实现
****************/
template
class queueType
{
public:
 const queueType& operator=(const queueType&);
 bool isEmptyQueue();
 bool isFullQueue();
 void initializeQueue();
 void destroyQueue();
 Type front();
 Type back();
 void addQueue(const Type& queueElement);
 void deleteQueue();
 queueType(int queueSize=100);
 queueType(const queueType& otherQueue);
 ~queueType();

private:
 int maxQueueSize;
 int count;
 int queueFront;
 int queueRear;
 Type *list;
};
//初始化队列
template
void queueType::initializeQueue ()
{
 queueFront=0;
 queueRear=maxQueueSize-1;
 count=0;
}
//队列判满和判空
template
bool queueType::isEmptyQueue ()
{
 return (0==count);
}
template
bool queueType::isFullQueue ()
{
 return (maxQueueSize==count);
}
//销毁队列
template
void queueType::destroyQueue ()
{
 initializeQueue();
}
//front
template
Type queueType::front ()
{
 assert(!isEmptyQueue());
 return list[queueFront];
}
//back
template
Type queueType::back ()
{
 assert(!isFullQueue());
 return list[queueRear];
}
//添加元素至队尾
template
void queueType::addQueue (const Type& queueEle)
{
 if(!isFullQueue())
 {
  queueRear=(queueRear+1)%maxQueueSize;
  //实现循环队列

  count++;
  list[queueRear]=queueEle;
 }
 else
  cout<<"Cannot add element to full queue!"<}
//删除队列中的头元素
template
void queueType::deleteQueue ()
{
 if(!isEmptyQueue())
 {
  queueFront=(queueFront+1)%maxQueueSize;
  count--;
 }
 else
  cout<<"Cannot remove from an empty queue!"<}
//构造函数与析构函数
template
queueType::queueType(int queueSz)
{
 if(queueSz<=0)
 {
  maxQueueSize=100;
 }
 else
  maxQueueSize=queueSz;

 queueFront=0;
 queueRear=maxQueueSize-1;
 count=0;
 list=new Type[maxQueueSize];
 assert(list!=NULL);
}
template
queueType::~queueType()
{
 delete [] list;
}
//复制构造函数和重载赋值操作符参考链表和堆栈实现

/********************
*(2)队列的链式实现
******************/
template
struct nodeType
{
 Type info;
 nodeType *link;
};

template
class linkedQueueType
{
public:
 const linkedQueueType& operator=(const linkedQueueType&);
 bool isEmptyQueue();
 bool isFullQueue();
 void destroyQueue();
 void initializeQueue();
 Type front();
 Type back();
 void addQueue(const Type& queueEle);
 void deleteQueue();
 
 linkedQueueType();
 linkedQueueType(const linkedQueueType& otherQueue);
 ~linkedQueueType();
private:
 nodeType *queueFront;
 nodeType *queueRear;
};
//is the queue empty?
template
bool linkedQueueType::isEmptyQueue ()
{
 return (NULL==queueFront);
}
template
bool linkedQueueType::isFullQueue ()
{
 return false;
}
//destroy the queue
template
void linkedQueueType::destroyQueue ()
{
 nodeType *temp;
 while(queueFront!=NULL)
 {
  temp=queueFront;
  queueFront=queueFront->link ;
  delete temp;
 }
 queueRear=NULL;
}
//将队列初始化为空状态
template
void linkedQueueType::initializeQueue ()
{
 destroyQueue();
}
template
linkedQueueType::linkedQueueType ()
{
 queueFront=NULL;
 queueRear=NULL;
}
template
linkedQueueType::~linkedQueueType ()
{
 destroyQueue();
}
//往队列添加元素
template
void linkedQueueType::addQueue (const Type& queueEle)
{
 //封装结点
 nodeType *newNode;
 newNode=new nodeType;
 assert(newNode!=NULL);
 newNode->info=queueEle;
 newNode->link=NULL;

 //添加结点
 if(queueFront==NULL)//队列为空时
 {
  queueFront=newNode;
  queueRear=newNode;
 }
 else   //队列不空时
 {
  queueRear->link =newNode;
  queueRear=newNode;
 }
}
//front
template
Type linkedQueueType::front ()
{
 assert(queueFront!=NULL);
 return queueFront->info ;
}
//back
template
Type linkedQueueType::back ()
{
 assert(queueRear!=NULL);
 return queueRear->info ;
}
//从队列中删除元素
template
void linkedQueueType::deleteQueue ()
{
 nodeType *temp;
 if(!isEmptyQueue())
 {
  temp=queueFront;
  queueFront=queueFront->link ;
  delete temp;
  if(queueFront==NULL)
   queueRear=NULL;
 }
 else
  cerr<<"Cannot remove from an empty queue!"<}
//其他成员函数实现从略

#include
using namespace std;
int main()
{
 //数组队列测试
 queueType intQueue;
 intQueue.addQueue (12);
 intQueue.addQueue (23);
 intQueue.addQueue (34);
 intQueue.addQueue (45);
 cout< intQueue.deleteQueue ();
 cout<

 //链式队列测试
 linkedQueueType lq;
 lq.addQueue (12);
 lq.addQueue (23);
 lq.addQueue (34);
 lq.addQueue (45);
 cout< lq.deleteQueue ();
 cout<

 //STL类queue使用
 queue iq;
 iq.push(26);
 iq.push(18);
 iq.push(50);
 iq.push(33);
 cout<<"STL queue Test:"< cout< cout<<"Size:"<

 iq.pop ();
 cout< iq.push (90);
 cout<<"The elements in the queue:"< while(!iq.empty ())
 {
  cout<  iq.pop ();
 }
 cout< return 0;

}