数据结构：队列
链队列的实现
链式存储结构
struct QNode
{
int data;
int* next;
}
struct LinkQueue;
{
QNode* front;
QNode* rear;
};操作函数
构造
void InitQueue (LinkQueue &Q)
{
Q.front = Q.rear = new QNode();
Q.front->next = NULL;
}销毁
void DestroyQueue (LinkQueue &Q)
{
while (Q.front)
{
Q.rear = Q.front->next;
delete Q.front;
Q.front = Q.rear;
}
}清空队列
void ClearQueue (LinkQueue &Q)
{
while (Q.front != Q.rear)//条件也可以是while (Q.front->next)
{
QNode* p = Q.front->next;
if (p == Q.rear)
{
Q.rear = Q.front;
}
Q.front->next = Q.front->next->next;
}
}注意上面while里面的if条件，当要删除的结点是Q.rear的时候，将Q.rear指向头指针指向的位置，不然它指向的位置就要被删除了，Q.rear就无效了。
判空
bool QueueEmpty (LinkQueue Q)
{
if (Q.front == Q.rear)
return true;
else
return false;
}表长
int QueueLength (LinkQueue Q)
{
QNode* p = Q.front;
int num = 0;
while (p != Q.rear)
{
p = p->next;
num++;
}
return num;
}可以在LinkQueue中增加一个int类型变量来储存表长
查询队首的值
bool GetHead (LinkQueue Q, int &e)
{
if (Q.front == Q.rear)
return false;
e = *(Q.front->next->data);
}在队尾插入元素
void EnQueue (LinkQueue &Q, int e)
{
QNode* p = new QNode();
p->next = NULL;
p->data = e;
Q.rear->next = p;
Q.rear = p;
}因为是链式结构，插入的时候不需要判断是不是满了，插入位置是不是合法等
在队首删除元素
bool DeQueue (LinkQueue &Q, int &e)
{
if (Q.front == Q.rear)
return false;
QNode* p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (p == Q.rear)
Q.rear = Q.front;
delete p;
return true;
}和清空队列一样，注意Q.rear指向结点是不是要被删除的结点
顺序存储结构
在队列的顺序存储结构中，需要用front和rear两个指针来只是队列的头元素和尾元素的位置。在初始化的时候令
front = rear = 0；每当插入一个元素，rear++；每当删除一个元素，front++；
以存储的最大空间为7的队列为例
可以看到，队列在插入元素上和栈相同，都是尾指针指向的位置上插入元素，然后rear在指向这个元素的下一个位置；但是在删除上有很大差别，栈的删除是尾指针向下移动，而队列是头指针向上移动。
这样会有一个问题，就是在溢出的时候，会分真溢出和假溢出两种情况。
- 真溢出
所谓真溢出就是front在0处，而rear指向上图中6的上面，即队列的空间被全部占用，此时rear的溢出就是真溢出。 - 假溢出
所谓假溢出就是front不在0处，而rear溢出，这里队列并没有完全被占满，因为还有0——（front-1）没有放置元素。
不论真溢出还是假溢出，都不能再向其中添加元素了，否则都会因为数组越界而遭至程序崩溃。但是对于假溢出这种情况，又不好像栈那样重新分配一个更大的空间来存储吧。毕竟，有很大一部分空间是还没有利用的，想想看，一个10000大小的数组，front = 9997，rear = 10000，这时再添加一个元素，就会越界，难道你还要去申请一个10010的空间来存这4个元素吗？
一个比较好的方法就是循环队列。
循环队列
所谓循环队列就是当front指向上图(c)中的a7的下一个位置的时候，将他赋值为a1所在的位置，也就是取模7的结果。这样就将这个表首尾相连，形成一个环，如下图所示，将一个存储N个元素的数组，想象成环。
移动rear和front时都会进行mod N的运算，即编程中的%N。
这样就万事大吉了吗？有没有什么问题呢？
我们来看一下下面的图片，不知道能不能找到什么问题呢？
我们发现队列为空的判断是front == rear，而队列满了条件竟然也是front == rear，那么当front == rear到底是空的还是满的？
针对这个问题有两种解决方案。
方案一，是设置一个标志，当队列没有元素为0，队列有元素为1，这样就可以区分开了。具体编程的时候就是在添加元素遇到front == rear 的时候，设置为1；删除元素遇到front == rear的时候，设置为0。查找的时候，遇到front == rear就看这个标志是0还是1喽。
方案二，我们可以空出最后一个存储单元，不用它来放值，注意，这里的最后一个存储单元是相对的，相对与front的位置的，也就是说这个最后一个存储单元是在front前面的那个存储单元。当rear指向这个单元的时候，表示队列满了，也就是当（ rear + 1）% N == front是队列满了的条件。当rear == front就是队列空的条件。