在网上看到一篇比较好的介绍队列的文章，地址为：http://www.cnblogs.com/kubixuesheng/p/4104802.html

特此感谢原创作者，以下均为摘抄。

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

1、顺序队列

 限制仅在表头删除和表尾插入的顺序表，利用一组地址连续的存储单元依次存放队列中的数据元素。因为队头和队尾的位置是变化的，所以也要设头、尾指针。  

 

初始化时的头尾指针，初始值均应置为 0。 入队尾指针增 1 ，出队头指针增 1 。头尾指针相等时队列为空，在非空队列里，头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。

初始为空队列，那么头尾指针相等。

入队，那么尾指针加1，头指针不变。先进先出，J1先进队，则 rear+1，尾指针始终指向队尾元素的下一位！如，J2进队，rear 继续+1，J3进队，尾指针继续加1，如图

 

出队，则尾指针不变，头指针加1，注意这里都是加1，先进先出原则，J1先删除，front+1，指向了 J2，J2删除，front+1指向了 J3，如图

 

最后，J3删除，则头指针再次和尾指针相等，说明队列空了。如图

在顺序队列中，当尾指针已经指向了队列的最后一个位置的下一位置时，若再有元素入队，就会发生“溢出”。如图位置，再次入队，就会溢出。

 

2、循环队列的诞生

顺序队列的 “假溢出” 问题：队列的存储空间未满，却发生了溢出。很好理解，比如 rear 现在虽然指向了最后一个位置的下一位置，但是之前队头也删除了一些元素，那么队头指针经历若干次的 +1 之后，遗留下了很多空位置，但是顺序队列还在傻乎乎的以为再有元素入队，就溢出呢！肯定不合理。故循环队列诞生！

解决“假溢出”的问题有两种可行的方法：

(1)、平移元素：把元素平移到队列的首部。效率低。否决了。

(2)、将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。操作效率高、空间利用率高。

      

虽然使用循环队列，解决了假溢出问题，但是又有新问题发生——判空的问题，因为仅凭 front = rear 不能判定循环队列是空还是满。比如如图：

这是空循环队列的样子

这是满循环队列的样子

解决办法：

(1)、另设一个布尔变量以区别队列的空和满；

(2)、少用一个元素的空间，约定入队前测试尾指针在循环下加 1 后是否等于头指针，若相等则认为队满；（最常用）

(3)、使用一个计数器记录队列中元素的总数。

对于第2个方案，必须牺牲一个元素的空间，那么入队的时候需要测试，循环意义下的加 1 操作可以描述为：

1     if (rear + 1 = MAXQSIZE)2 3            rear = 0;4 5      else6 7           rear ++;

 

利用模运算可简化为：

 

1 rear = (rear + 1)% MAXQSIZE

基本操作

1 #ifndef ___queue_Header_h 2 #define ___queue_Header_h 3 #include 
     
       4 #include 
      
        5 #define MAX_SIZE 5 6  7 typedef struct{ 8     int *base; 9     int rear;//如果队列不空，指向队尾元素的下一个位置10     int front;//初始的时候指向表头11 } CirularQueue;12 13 //初始化14 void initQueue(CirularQueue *queue)15 {16     queue->base = (int *)malloc(MAX_SIZE*sizeof(int));17     18     if (NULL == queue->base) {19         exit(0);20     }21     22     queue->front = queue->rear = 0;23 }
      
     

求长度

//求长度int getLength(CirularQueue queue){    //这样把所以的情况都考虑到了    return (queue.rear - queue.front + MAX_SIZE) % MAX_SIZE;}

第一种情况，长度的求法

第二种情况，长度的求法，利用模运算，两个情况合二为一！

//入队，先判满void insertQueue(CirularQueue *queue, int e){    if ((queue->rear + 1) % MAX_SIZE == queue->front) {        puts("循环队列是满的！");    }    else    {        queue->base[queue->rear] = e;        queue->rear = (queue->rear + 1) % MAX_SIZE;    }}

如下时为满，损失一个空间，不存储元素。方便判满

1 //出队 2 void deleteQueue(CirularQueue *queue) 3 { 4     if (queue->front == queue->rear) { 5         puts("队列是空的！"); 6     } 7     else 8     { 9         queue->front = (queue->front + 1) % MAX_SIZE;10     }11 }12 13 //遍历14 void traversal(CirularQueue queue)15 {16     int q = queue.front;17     18     for (int i = 0; i < getLength(queue); i++) {19         printf("循环队列的第%d个元素为%d\n", i + 1, queue.base[q]);20         q ++; 21     } 22 } 23 24 #endif

为了尊重原创我将原作者的代码贴上来了，但对最后一个遍历持保留意见，我觉得后面直接q++不会有问题吗？

我个人觉得应该改成：

//遍历void traversal(CirularQueue queue){    int q = queue.front;        for (int i = 0; i < getLength(queue); i++) {        printf("循环队列的第%d个元素为%d\n", i + 1, queue.base[q]);        q = (q + 1)%MAX_SIZE;     } }