C++数据结构：队列
和栈一样，是特一种特殊的线性表（限制版本 的线性表），先进新出的数据结构。普通队列中的数据从队头离开之后，那么队头离开后的内存空间就被剩下了，导致内存利用率降低。环形队列就可以解决这个问题。
队列和栈一样是一种线性结构，其底层基础都是线性数组和链表，基于数组队列的缺点是由于一端插入一端删除，当不断从头部删除数据，头部会大量留有空闲内存，无法插入，造成空间流失，如果将队头指针在每次删除之后往前移动一个位置，这是一个时间复杂度为O(n)的操作.为解决这个要么空间浪费要么时间浪费的问题，使用循环队列，所谓循环队列，是将一个数组看出首尾相连的圆环，删除元素时将队首标志往后移动，添加元素时若数组尾部已经没有空间，则考虑数组头部的空间是否空闲，如果是，则在数组头部插入
环形队列在头部删除，在尾部插入，删除和插入方向都是顺时针的。
抽象数据类型 queue
{
实例
元素的有序表，一端称为队首，另一端称为队尾
操作
empty():
size():
front();//返回队首元素
back();//返回队尾元素
pop();//删除队首元素
push(x);//把元素x假如到队尾
}；
1、主要操作
2、分类
（1）数组描述：
（2）链表描述：
3、主要的问题
（1）如何判断队列空、满
队空：begin == end=0；
队满：begin == (end+1)%length;
（2）队头、队尾的位置
队头：begin = begin % length;
队尾：end = end % length;
总结队列中要解决的问题：
1）求元素的个数：(end-begin+length) % length
2）begin /end 指向逻辑的下一个空间 begin =（begin +1)%length，end = (end +1)%length
3）判空：begin == end =0；
4）判满：(end +1)%length== begin
4、C++实现队列（数组队列）
#include <iostream>
#include <string>
using namespace std;
template<class T>
class LoopQueue
{
private:
T* queue;
int length;
int begin;
int end;
public:
LoopQueue(int c = 10);
~LoopQueue();
bool isEmpty();
int size();
bool push(T t);//在队首入队
bool pop();//队尾元素出队
T front();//队首元素
T back();//队尾元素
bool fullqueque();//判断是否队满
};
template<class T>
LoopQueue<T>::LoopQueue(int c = 10)
{
length = c;
begin = 0;
end = 0;
queue = new T[length];
}
template<class T>
LoopQueue<T>::~LoopQueue()
{
delete[] queue;
}
template<class T>
bool LoopQueue<T>::isEmpty()
{
if (begin == end)
return true;
return false;
}
template<class T>
int LoopQueue<T>::size()
{
return (end - begin + length) % length;
}
template<class T>
T LoopQueue<T>::front()
{
if (begin == end)
return false;
return queue[begin];
}
template<class T>
T LoopQueue<T>::back()
{
if (end == begin)
return false;
return queue[end];
}
template<class T>
bool LoopQueue<T>::fullqueque()
{
if ((end + 1) % length == begin)
return true;
else
return false;
}
template<class T>
bool LoopQueue<T>::push(T t)
{
if (fullqueque())
{
//有必要的话加上增加数组容量的代码
}
else
{
queue[end] = t;
end = (end + 1) % length;
return true;
}
}
template<class T>
bool LoopQueue<T>::pop()
{
if (!isEmpty())
{
begin = (begin + 1) % length;
//queue[begin].~T();
return true;
}
return false;
}
int main()
{
LoopQueue<string> queue(20);
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();
}
queue.push("shishi");
cout << endl << queue.front() << endl;
//getchar();
//system("pause");
return 0;
}
队列的链表描述：
从头至尾的链接方式有利于删除操作。
