[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（rear），，允许删除的一端叫做队首（front）。

队列具有FIFO的性质

队列的存储表示也有两种方式：基于数组的，基于列表的。基于数组的叫做顺序队列，基于列表的叫做链式队列。

一下是基于动态数组的顺序队列的模板类的实现。

顺序队列的抽象基类如下所示：只提供了接口和显式的默认构造函数和析构函数，在派生类中调用。

#ifndef QUEUE#define QUEUE//队列的抽象基类template<class T>class Queue{public:Queue(){}~Queue(){}virtual bool EnQueue(const T& x)=0;virtual bool DeQueue(T& x)=0;virtual bool getFront(T& x)const=0;virtual bool IsEmpty()const=0;virtual bool IsFull()const=0;virtual int getSize()const=0;};#endif

顺序队列的具体实现如下：（覆盖所有纯虚函数的接口，并提供自己的接口和数据成员）

/////////////////////////#include"Stack.h"#include <iostream>//#include <cstdlib>#include <cassert>using namespace std;template<class T>class SeqQueue:public Queue<T>{public:SeqQueue(int sz=10):front(0),rear(0),maxSize(sz),elements(new T[sz]){assert(elements!=NULL);}~SeqQueue(){delete []elements;}SeqQueue(const SeqQueue<T>& rhs);SeqQueue<T>& operator=(const SeqQueue<T>& rhs);bool EnQueue(const T& x);bool DeQueue(T& x);bool getFront(T& x)const;bool IsEmpty()const{return (rear==front)?true:false;} //判断空bool IsFull()const{return ((rear+1)%maxSize==front)?true:false;} //判断满int getSize()const{return (rear-front+maxSize)%maxSize;} //检测大小，+maxSize表示非负void makeEmpty(){front=rear=0;}friend ostream& operator<< <T>(ostream& os,const SeqQueue<T>& rhs);//注意<T>protected:int front,rear;T* elements;int maxSize;};template<class T>bool SeqQueue<T>::EnQueue(const T& x){if(IsFull())return false;elements[rear]=x;rear=(rear+1)%maxSize;//注意不是++rearreturn true;}template<class T>bool SeqQueue<T>::DeQueue(T& x){if(IsEmpty())return false;x=elements[front];front=(front+1)%maxSize;return true;}template<class T>bool SeqQueue<T>::getFront(T& x)const{if(IsEmpty())return false;x=elements[front];return true;}template<class T>ostream& operator<<(ostream& os,const SeqQueue<T>& rhs){os<<"front="<<rhs.front<<" "<<"rear="<<rhs.rear<<endl;os<<"elements: ";for(int i=0;i<rhs.getSize();++i){os<<rhs.elements[(rhs.front+i)%rhs.maxSize]<<" "; //注意遍历方法}os<<endl;return os;}template<class T>SeqQueue<T>::SeqQueue(const SeqQueue<T>& rhs){front=rhs.front;rear=rhs.rear;maxSize=rhs.maxSize;T* dest=new T[maxSize];T* src=rhs.elements;elements=dest;for(int i=0;i<rhs.getSize();++i){dest[(front+i)%maxSize]=src[(front+i)%maxSize];}}template<class T>SeqQueue<T>& SeqQueue<T>::operator=(const SeqQueue<T>& rhs){delete[] elements;makeEmpty();front=rhs.front;rear=rhs.rear;maxSize=rhs.maxSize;T* dest=new T[maxSize];T* src=rhs.elements;elements=dest;for(int i=0;i<rhs.getSize();++i){dest[(front+i)%maxSize]=src[(front+i)%maxSize];}return *this;}测试代码如下：

int main(int argc, char* argv[]){SeqQueue<int> s(5);int a=1,b=2,c=3,d=4,e=0;s.EnQueue(a);s.EnQueue(b);s.EnQueue(c);s.EnQueue(d);cout<<s;s.DeQueue(e);s.DeQueue(e);cout<<s;cout<<"getSize(): "<<s.getSize()<<endl;cout<<boolalpha;cout<<"IsEmpty(): "<<s.IsEmpty()<<endl;cout<<"IsFull(): "<<s.IsFull()<<endl;cout<<noboolalpha;s.getFront(e);cout<<"getFront(): "<<e<<endl;SeqQueue<int> s1(s),s2;cout<<s1;s2=s;cout<<s2;system("pause");return 0;}

测试结果如下：

front=0 rear=4elements: 1 2 3 4front=2 rear=4elements: 3 4getSize(): 2IsEmpty(): falseIsFull(): falsegetFront(): 3front=2 rear=4elements: 3 4front=2 rear=4elements: 3 4请按任意键继续. . .

注意事项：

1.该实现是正对动态数组存储的循环队列，在逻辑上构成了一个环。

2.rear指向实际队尾位置的下一个位置，front指向的是真正的对头元素所在的位置。

3.初始化时rear=front=0

4.判断空对：front=rear

5.判断满：（rear+1）%maxSize=front。让rear指向front的前一个位置就认为队列已满，所以最多只能存储maxSize-1个元素。这是为了和队列空的判断相区别。

6.对头指正进1：front=（front+1）%maxSize

7.队尾指针进1：rear=（rear+1）% maxSize

打掉的应是脆弱的铁屑，锻成的将是锋利的钢刀。