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

本文主要是介绍[数据结构]队列之顺序队列的类模板实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

队列是一种限定存取位置的线性表，允许插入的一端叫做队尾（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=4
elements: 1 2 3 4
front=2 rear=4
elements: 3 4
getSize(): 2
IsEmpty(): false
IsFull(): false
getFront(): 3
front=2 rear=4
elements: 3 4
front=2 rear=4
elements: 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

这篇关于[数据结构]队列之顺序队列的类模板实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---