何为队列？
队列(Queue)也是一种线性存储结构，它具有如下特点：
队列中的数据元素遵守“先进先出”(First In First Out)的原则，简称FIFO结构。
在队尾添加元素，在对首删除元素。
队列的相关概念与操作
1.对头与队尾：允许元素插入的一端称为队尾，允许删除元素的一端称为对首。
2.入队：队列的插入操作。
3.出队：队列的删除操作。
4.求队列的大小
5.求对首元素的值
6.判断队列是否为空
栈是一种线性结构，能以数组或链表作为底层数据结构来实现。
基于数组的队列实现
以数组做为底层数据结构时，一般将队列实现为循环队列。这是因为：
1.如果采用顺序存储，每次从数组头部删除元素后，其后的元素都要依次往前移一个位置，时间复杂度为O(n);
2.对于上述问题，有人提议将对首标志往后移就不用移动元素了，可是这回造成空间的浪费。
所以为了实现队列的插入删除都是O(1)的时间复杂度，同时不造成空间的流失，我们采用循环队列。
何为循环队列？
即把数组看成一个首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部进行插入。
如上图所示，我们以begin和end分别代表队首和队尾标志，end后面还有一个空位但是我们不存储元素，那么如何判断队满或者队空呢？
1.当begin==end时，表示队空。
2.当(end+1)%maxsize==begin时，表示队满。
/*队列的抽象数据类型*/
template <typename T>
class ArrayQueue
{
public:
//构造函数
ArrayQueue(int s): maxsize(s),begin(0),end(0),array(NULL) {
array = new T[maxsize];
}
//析构函数
~ArrayQueue()
{
delete []array;
}
T front(); //对首元素
bool pop(); //出对
bool push(T t); //入队
bool isEmpty(); //判空
int size(); //队列的大小
private:
int begin; //对首元素
int end; //对尾
T *array; //数组
int maxsize; //容量
};具体实现
template <typename T>
T ArrayQueue<T>::front()
{
if(begin != end)
return array[begin];
};
template <typename T>
bool ArrayQueue<T>::pop()
{
if(begin == end)
return false;
begin = (begin+1)%maxsize;
return true;
};
template <typename T>
bool ArrayQueue<T>::push(T t)
{
if((end+1)%maxsize == begin)
return false;
array[end] = t;
end = (end+1) % maxsize;
return true;
};
template <typename T>
bool ArrayQueue<T>::isEmpty()
{
if(begin == end)
return true;
else
return false;
};
template <typename T>
int ArrayQueue<T>::size()
{
return (end - begin + maxsize) % maxsize;
};主函数
int main()
{
ArrayQueue<string> queue(6);
queue.push("one");
queue.push("two");
queue.push("three");
queue.push("four");
queue.push("five");
cout << "队列长度：" << queue.size() << endl;
while(!queue.isEmpty())
{
cout << queue.front() << endl;
queue.pop();
}
return 0;
}输出结果：
基于链表的栈实现
基于链表的队列不存在上述问题，我们只需考虑哪头做队首，哪头做队尾。如下图所示，很清晰直观，不再啰嗦。
链表结点
/*链表结点，即队列中的元素*/
template <typename T>
struct Node
{
Node(T t):value(t),next(NULL) {}
Node() = default;
public:
T value; //队列中元素的值
Node<T>* next; //链表节点指针
};队列的抽象数据类型
/*基于链表的队列的ADT*/
template <typename T>
class LinkQueue
{
public:
LinkQueue(): phead(NULL),pend(NULL),count(0){
phead = new Node<T>();
pend = phead;
count = 0;
}
T front(); //对首元素
bool pop(); //出对
bool push(T t); //入队
bool isEmpty(); //判空
int size(); //队列的大小
private:
Node<T>* phead;
Node<T>* pend;
int count; //队列元素的数量
};具体实现
template <typename T>
T LinkQueue<T>::front()
{
if(count != 0)
return phead->next->value;
};
template <typename T>
bool LinkQueue<T>::pop()
{
if(count == 0)
return false;
Node<T>* pdel = phead-> next;
phead -> next = pdel -> next;
delete pdel;
count--;
return true;
};
template <typename T>
bool LinkQueue<T>::push(T t)
{
Node<T>* pnode = new Node<T>(t);
pend -> next = pnode;
pend = pnode;
count++;
return true;
};
template <typename T>
bool LinkQueue<T>::isEmpty()
{
if(count == 0)
return true;
else
return false;
};
template <typename T>
int LinkQueue<T>::size()
{
return count;
};
主函数实例
int main()
{
LinkQueue<string> lqueue;
lqueue.push("one");
lqueue.push("two");
lqueue.push("three");
lqueue.push("four");
lqueue.push("five");
cout << "队列长度：" << lqueue.size() << endl;
while(!lqueue.isEmpty())
{
cout << lqueue.front() << endl;
lqueue.pop();
}
return 0;
}输出结果：
用C++模板实现基于数组和链表的队列，和上节实现栈相似，希望对大家有所帮助。