一 队列的定义
队列（queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表
（1）允许删除的一端称为队头（front）。
（2）允许插入的一端称为队尾（rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（first in first out）的线性表，简称为fifo表。
二 顺序队列
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
基本操作：
入队时：将新元素插入rear所指的位置，然后将rear加1。
出队时：删去front所指的元素，然后将front加1并返回被删元素。
三 循环队列
为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（circular queue）。即：循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（queuesize-1）时，其加1操作的结果是指向向量的下界0。
（1）循环意义上的加1操作可以
① 方法一：
if(i+1==queuesize) //i表示front或rear
i=0;
else
i++;
② 方法二： 利用"模运算"
i=(i+1)%queuesize；
（2）循环队列的边界问题
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
① 另设一布尔变量以区别队列的空和满；
② 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。
（3）循环队列数据类型
#define queursize 100 //应根据具体情况定义该值
typedef char datatype; //datatype的类型依赖于具体的应用
typedef struct{
int front; //头指针，队非空时指向队头元素
int rear; //尾指针，队非空时指向队尾元素的下一位置
int count;//计数器，记录队中元素总数
datatype data[queuesize]
}cirqueue;
（4）循环队列的基本运算
① 置队空
void initqueue(cirqueue *q)
{
q->front=q->rear=0;
q->count=0; //计数器置0
}
② 判队空
int queueempty(cirqueue *q)
{
return q->count==0; //队列无元素为空
}
③ 判队满
int queuefull(cirqueue *q)
{
return q->count==queuesize; //队中元素个数等于queuesize时队满
}
④ 入队
void enqueue(cirqueuq *q,datatype x)
{
if(queuefull((q))
{
printf("queue overflow"); //队满上溢
exit(1);
}
q->count ++; //队列元素个数加1
q->data[q->rear]=x; //新元素插入队尾
q->rear=(q->rear+1)%queuesize; //循环意义下将尾指针加1
⑤ 出队
datatype dequeue(cirqueue *q)
{
datatype temp;
if(queueempty((q))
{
printf("queue underflow"); //队空下溢
}
temp=q->data[q->front];
q->count--; //队列元素个数减1
q->front=(q->front+1)%queuesize; //循环意义下的头指针加1
return temp;
}
⑥取队头元素
datatype queuefront(cirqueue *q)
if(queueempty(q))
{
printf("queue if empty.");
}
return q->data[q->front];
}
转载：http://blog.csdn.net/xsf50717/article/details/39937085