1，综述
队列（queue）是一种受限制的线性表，其属性与看电影排队类似，新加入的必须排在队尾(enqueue,入队)，先离开的必须从队首开始（dequeue，出队）。因此，队列是按照到达的顺序来删除元素的，即先进先出（First In First Out）.队列的ADT：(Queue.h)
/********************************************************/
// 用模板实现队列（Queue）的基类定义
// 队列，先进先出（FIFO）的线性表
/********************************************************/
#pragma once
#include "Public.h"
template<class E>
class Queue
{
public:
Queue() {}
virtual ~Queue() {}
virtual void clear() = 0;
// 入队，只能从队尾插入
virtual void enqueue(const E& it) = 0;
// 出队，只能从队首删除，返回类型不能是引用，因为返回的队首值已经不存在了
virtual E dequeue() = 0;
// 返回队首的值，返回类型是const引用，所以你能获取值，但不能改变它
virtual const E& frontValue()const = 0;
// 返回栈中当前存储的元素个数
virtual int length() const = 0;
};
队列的实现方式有两种：顺序队列（用数组实现）和链式队列（用单向链表实现）。
2，顺序队列（array based queue）
用数组模拟队列，首先想到的，就是把队首放在a[0]位置，剩下的依次排放，新元素入队就放在后面排队，出队的时候，就必须后面所有的元素都往前移一位，就好像我们排队的时候，最前面的人走了，后面所有人必须都往前走一步，队伍才能前进一样。但是这样会耗费态度的资源。所以将其改进为不强制要求队首必须在a[0]，只要能知道队首所在的数组下标即可。但是这样一来，一旦发生出队，a[0]和队首之间的内存就被浪费了，永远都没办法利用。改进的方案是，当如队到达数组的最后一个位置a[len-1]后，开始向a[0]填充元素，但不能越过队首。这样一来，直线的排列方式实际上已经变成圆环形了。
代码实现： ArrayQueue.h:
/********************************************************/
// 用数组实现顺序队列（array based queue）的定义
// 继承基类栈 Queue<E>
/********************************************************/
#pragma once
#include "Queue.h"
const size_t defaultQSize = 5;//Queue数据的默认长度
template<class E>
class AQueue : public Queue<E>
{
private:
E* data; //存储Queue数据的数组
int front; //队首的数组下标
int rear; //队尾的数组下标+1
int maxSize;//简单实现，只开辟一次空间，所以有最大大小
int iNr; //队列中的元素个数，队列长度
public:
AQueue(size_t size = defaultQSize);
~AQueue();
void clear();
// 入队，只能从队尾插入
void enqueue(const E& it);
// 出队，只能从队首删除，返回类型不能是引用，因为返回的队首值已经不存在了
E dequeue();
// 返回类型是const引用，所以你能获取栈顶的值，但不能改变它
const E& frontValue()const;
// 返回栈中当前存储的元素个数
int length() const;
};
ArrayQueue_Def.h:
/********************************************************/
// 用数组实现顺序队列（array based queue）的定义
// 继承基类栈 Queue<E>
// 此处实现AQueue<E>的成员函数
/********************************************************/
#pragma once
#include "ArrayQueue.h"
// 定义构造函数，开辟空间
template<class E>
AQueue<E>::AQueue(size_t size = defaultSize) : front(0), rear(0),iNr(0),maxSize(size)
{
data = new E[size];
}
template<class E>
AQueue<E>::~AQueue()
{
delete[] data;
}
// 清空栈，只是修改top下标，不收回内存
template<class E>
void AQueue<E>::clear()
{
front = rear = iNr = 0;
}
// 入队，只能从队尾插入
template<class E>
void AQueue<E> ::enqueue(const E& it)
{
Assert(iNr < maxSize, "队列已满");
// 小于maxSize时就是rear，等于maxSize时变成0
rear %= maxSize;
data[rear++] = it;
iNr++;
}
// 弹出栈顶元素
template<class E>
E AQueue<E> ::dequeue()
{
Assert(iNr > 0, "空队列");
E it = data[front++]; //front下移一位
front %= maxSize; // 小于maxSize时就是front，等于maxSize时变成0
iNr--;
return it;
}
// 获取栈顶元素
template<class E>
const E& AQueue<E> ::frontValue() const
{
Assert(iNr > 0, "空栈");
return data[front];
}
// 返回栈中元素个数
template<class E>
int AQueue<E>::length() const
{
return iNr;
}
3，链式队列
链式队列是对单向链表的简化。需要注意的是，这里front不再是指向队首，front里面不存储队列中任意一个元素的数值，front->next存储的才是队首元素。LinkedQueue.h:
/********************************************************/
// 用模板实现链式队列（Linked Queue）的定义
// 是单向链表的简化
// 继承基类 Queue<E>
/********************************************************/
#pragma once
#include "Queue.h"
// 1,定义节点类模板
template<class E>
class QNode
{
public:
E element; //本结点存储的元素值
QNode* next;//指向下一结点的指针
QNode(const E& elemval, QNode* nextval = NULL) :element(elemval), next(nextval) {}
QNode(QNode* nextval = NULL) :next(nextval) {}
};
// 2,定义链表类模板
template<class E>
class LQueue : public Queue<E>
{
private:
QNode<E>* front; //队首
QNode<E>* rear; //队尾
int cnt; //链表中当前存储的元素个数
void init(); //初始化
public:
LQueue();
~LQueue();
void print() const;
void clear();
// 入队，只能从队尾插入
void enqueue(const E& it);
// 出队，只能从队首删除，返回类型不能是引用，因为返回的队首值已经不存在了
E dequeue();
// 返回栈中当前存储的元素个数
int length() const;
// 返回队首的值，返回类型是const引用，所以你能获取值，但不能改变它
const E& frontValue()const;
};
LinkedQueue_Def.h:
/********************************************************/
// 用模板实现链式队列（Linked Queue）的定义
// 是单向链表的简化
// 继承基类 Queue<E>
// 本文件实现成员函数的定义
/********************************************************/
#pragma once
#include "LinkedQueue.h"
template<class E>
void LQueue<E>::init()
{
//所有指针指向新开的空间
front = rear = new QNode<E>();
cnt = 0;
}
//构造函数
template<class E>
LQueue<E>::LQueue()
{
//构造时只开辟一个节点的空间
init();
}
//析构函数
template<class E>
LQueue<E>::~LQueue()
{
clear();
delete front; //空的首节点也不能留
}
//打印所有元素
template<class E>
void LQueue<E>::print() const
{
Node<E>* temp = front->next; //head中不存储数据，head->next中才有数据
while (NULL != temp)
{
//此处暗示类型E必须定义了“<<”操作，否则报错
cout << temp->element << endl;
temp = temp->next;
}
}
//清空链表
template<class E>
void LQueue<E>::clear()
{
QNode<E>* temp = front->next;
//删除除front之外的所有节点
while(NULL != temp)
{
front->next = temp->next;
delete temp;
temp = front->next;
}
rear = front;
cnt = 0;
}
//入队
template<class E>
void LQueue<E>::enqueue(const E& it)
{
rear = rear->next = new QNode<E>(it);
cnt++;
}
//出队
template<class E>
E LQueue<E>::dequeue()
{
// 由于front节点不存储真实的内容，要删除的不是front，而是front->next
Assert(cnt != 0, "队列为空");
QNode<E>* temp = front->next;
E it = front->next->element;
// front节点的位置不变，但是front->next指向下一个
front->next = temp->next;
// 要删除的是最后一个元素
if (temp == rear)
{
rear = front;
}
delete temp;
cnt--;
return it;
}
// 返回个数
template<class E>
int LQueue<E>::length() const
{
return cnt;
}
template<class E>
const E& LQueue<E>::frontValue()const
{
return front->next->element;
}