C语言实现循环队列（基本操作及图示）

————————————————————————————————————————————

如果使用顺序表作为队列的话，当处于右图状态则不能继续插入新的队尾元素，否则会因为数组越界而导致程序代码被破坏。

由此产生了由链表实现的循环队列，只有队列未满时才可以插入新的队尾元素。

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

基本操作：

/* 定义链表队列 */

定义结构体中front指示队头位置，rear指示队尾位置，base指针用于申请空间并存放数据。

/* 初始化队列 */

使用指针*base申请100个内存空间，front和rear分别为0，此时队列为空

/* 判断空或满 */

• 初始化时， front = rear = 0 时为空， Q->rear = （ 0+1 ） %100 = 1 ，队列未满可以插入队列

  

• 入队 3 个元素时， rear = 3 ， Q->rear = （ 3+1 ） %100 = 4 ，队列未满

  

• 入队 99 个元素时， rear = 99 ， Q->rear = （ 99+1 ） %100 = 0 ，队列满，不可入队

  

• 出队 2 个元素时， front = 2

  出队后，执行两次 Q->front = (Q->front + 1) % MAXQSIZE ，得到 Q->front = 2

  

• 再次入队 1 个元素时， rear = 0 ， Q->rear = （ 99+1 ） %100=0 ，队列未满，可以入队

  

实现代码：

             1 #include <stdio.h>
 2 #include <stdlib.h>
 3#define OK 1
 4#define ERROR 0
 5#define OVERFLOW -2
 6#define MAXQSIZE 100
 7 typedef int Status;
 8 typedef int QElemType;
 9 typedef struct Node
10{
11     QElemType *base; //初始化动态分配存储空间12int front;
13int rear;
14} SqQueue;
15 Status InitQueue(SqQueue *Q)
16{
17     Q->base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
18if (!Q->base)
19        exit(OVERFLOW);
20     Q->front = Q->rear = 0;
21return OK;
22}
23 Status EnQueue(SqQueue *Q, QElemType elem)
24{
25//队列为空时 1%100==1,队列满时(99+1)%100==0,最多容纳99个元素26if ((Q->rear + 1) % MAXQSIZE == (Q->front))
27return ERROR;
28     Q->base[Q->rear] = elem;
29     Q->rear = (Q->rear + 1) % MAXQSIZE; //rear始终在0-100中循环30return OK;
31}
32 Status OutQueue(SqQueue *Q, QElemType *e)
33{
34if (Q->front == Q->rear)
35return ERROR;
36     *e = Q->base[Q->front];
37     Q->front = (Q->front + 1) % MAXQSIZE;
38return OK;
39}
40Status PrintQueue(SqQueue Q)
41{
42     printf("the queue is:");
43for (int i = Q.front; i < Q.rear; ++i)
44         printf("%d ", Q.base[i]);
45return OK;
46}
47int main()
48{
49    SqQueue queue;
50    QElemType elem;
51int i;
52     InitQueue(&queue);
53     printf("input:");
54while(scanf("%d", &elem) != EOF)
55         EnQueue(&queue, elem);
56    PrintQueue(queue);
57/* 输入要出队列的个数 */58     printf("\noutput:");
59     scanf("%d", &i);
60while(i != 0)
61    {
62         OutQueue(&queue, &elem);
63         i--;
64    }
65    PrintQueue(queue);
66return OK;
67 }

原文：http://www.cnblogs.com/hughdong/p/6841970.html