循环队列的操作

    队列和链表、堆栈一样都是一种线性结构。只不过队列的操作限定在两端,只能够在队头和队尾进行操作。它的特性是先进先出,在队尾进队头出。

队列的物理结构包括顺序存储结构和链式存储结构,也就是我们常说的顺序队列和链式队列。

    这里就说一下顺序队列,顺序存储结构要预先分配内存,最好能知道队列的最大长度,在顺序队列中当队头指针front和队尾指针rear指向同一位置的

时候,表示队列是空的如下图(a);当队尾指针指向末尾的时候,队列就满了如下图(d)。下面放一张图来说明顺序队列

     在图(a)中是顺序队列的初始状态,此时队头指针front和队尾指针rear指向同一位置;然后就可以直接向队中添加数据,入队后rear指向下一个位置,注意在添加

数据的时候front始终指向队头位置,添加后rear指向队尾元素的下一个位置,图(b)就是添加了数据后的队列;图(c)是出队后的状态,每次出队后,front就指向下一

个位置;在图(d)中,队尾指针rear已经指向了队列的末尾位置,没法再入队列了,如果再入队的话就会溢出,但实际上队头前面还有空的位置但又不能用,所以这样

就造成了空间的浪费,这是一种假溢出。为了解决这个问题,就引入了循环队列,循环队列,放上图片来说明

    第一个图是初始状态,然后开始入队,经过几次入队后,就到了第二个图,在此过程中队头指针front始终指向队头元素,队尾指针rear指向队尾元素的下一个位置,

这和上面的讲的一样。同样的,当队头指针front和队尾指针rear指向同一位置的时候,表示队列是空的,那在第三个图中就发现此时队列是满的,但是按照front=rear,

那么队列又是空的,这就矛盾了。所以这里就留一个位置不用,就是第二个图的样子,这时候通过 (Q->rear+1)%size==Q->front 这条语句来判断队列是否满了;假如

现在要用的队列长度是100,那就令size=101,多出来的一个不用,以便用 (Q->rear+1)%size==Q->front 这个条件来判断队列满了没有。

    讲的不太详细,多理解理解,拿笔去画画,试着演示一下,应该还是能明白的。下面就来展示一下循环队列的各种操作,包括初始化、入队、出队等,代码已经测

试过了,注释我写的也比较详细了。如有不对的地方,欢迎指出错误!

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<malloc.h>
  4 #include<stdlib.h>
  5 #define MAXSIZE 101
  6 using namespace std;
  7 typedef  struct
  8 {   int data[MAXSIZE];  //队列的大小
  9     int front;    //指向队头
 10     int rear;   //指向队尾元素的下一个位置,rear为非空
 11 }cQueue;    //循环队列
 12 
 13 cQueue* initQueue()   //初始化队列
 14 {
 15     cQueue* Q=(cQueue*)malloc(sizeof(cQueue));  //给队列开辟空间,成功返回首地址,失败返回NULL
 16     if(!Q )
 17     {
 18         printf("存储分配失败
");
 19         exit(-1);
 20     }
 21     Q->front=0;
 22     Q->rear=0;    //空队列的话队头和队尾指向同一位置
 23     return Q;
 24 }
 25 int push(cQueue *Q,int e)  //入队成功返回1,入队失败返回0
 26 {
 27     if((Q->rear+1)%MAXSIZE==Q->front)  //队列已满    
 28         return 0;
 29     Q->data[Q->rear]=e;   //当前rear指向队尾元素的下一个位置,是空的,可直接入队
 30     Q->rear=(Q->rear+1)%MAXSIZE; //入队后再让rear指向下一个位置,下一个位置是空的,方便下次直接入队
 31     return 1;
 32 }
 33 int pop(cQueue *Q,int *e) //出队成功返回1,出队失败返回0
 34 {
 35     if(Q->rear==Q->front)   //空队列 
 36     {
 37         printf("队列为空
");
 38         return 0;
 39     }
 40     *e=Q->data[Q->front];
 41     Q->front=(Q->front+1)%MAXSIZE;  //队头元素出队后,front指向下一个位置
 42     return 1;
 43 }
 44 int length(cQueue *Q)
 45 {
 46     return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
 47 }
 48 int isempty(cQueue *Q) //队列为空返回1,非空返回0
 49 {
 50     if(Q->front==Q->rear)
 51         return 1;
 52     else
 53         return 0;
 54 }
 55 void clear(cQueue *Q) //清空
 56 {
 57     Q->front=Q->rear;
 58 }
 59 void printQueue(cQueue *Q)
 60 {
 61     int i;
 62     i=Q->front;
 63     if(Q->front==Q->rear)
 64     {
 65         printf("队列是空的
");
 66         exit(-1);
 67     }
 68     while(i!=Q->rear)
 69     {
 70         printf("%d ",Q->data[i]);
 71         i++;
 72         i=i%MAXSIZE;
 73     }
 74     printf("
" );
 75 }
 76 int main()
 77 {
 78     int e;
 79     char ch=0;
 80     cQueue *Q;
 81     Q=initQueue();
 82     printf("输入待入队的元素:
");
 83     do{
 84         scanf("%d",&e);
 85         push(Q,e);
 86     }while((ch=getchar())!='
');
 87     printf("队中元素为:
");
 88     printQueue(Q);
 89     printf("队列的长度为:%d
",length(Q));
 90     for(int i=1;i<=5;i++)
 91     {
 92         pop(Q,&e);
 93         printf("第%d次出队的元素为:%d
",i,e);
 94     }
 95     printf("pop后队列中的元素为:");
 96     printQueue(Q);
 97     printf("pop后队列的长度为:%d
",length(Q));
 98     printf("结果为1表示队列为空,为0表示队列非空:%d
",isempty(Q));
 99     clear(Q);
100     printf("结果为1表示队列为空,为0表示队列非空:%d
",isempty(Q));
101     return 0;
102 }

结果如下:

2020-04-29      19:39:12

原文地址:https://www.cnblogs.com/buanxu/p/12803651.html