C语言实现循环队列

以你之姓@ 2022-06-17 04:16 283阅读 0赞

队列是一种先进先出的线性表，它只允许在表的一端进行插入，而在另外一端删除元素。简单的说这个就是我们生活中排队的模型。

简单的队列实现这里就不说了，简单地给出结构如下：

typedef struct{
        QElemType * base;
        int font;   //队列头游标
        int rear;   //队列尾游标
    }SqQueue;

![这里写图片描述][25E5_25BE_25AA_25E7_258E_25AF_25E9_25A1_25BA_25E5_25BA_258F_25E9_2598_259F_25E5_2588_2597_25E6_2593_258D_25E4_25BD_259C_25E7_25A4_25BA_25E6_2584_258F_25E5_259B_25BE_1.jpg]

以上是简单队列的示意图，图片来自百度，侵删。

考虑这样的情况：假设当前为队列分配的最大空间为10，队列的头游标在5，尾游标在9，那么如果再添加一个新的元素势必会因数组越界而导致程序错误。然而此时又不宜像顺序表那样扩大存粗空间，因为队列的实际的可用空间并未占满。

一个较为巧妙的方法是将顺序队列臆想成一个环状空间，称之为循环队列。

![这里写图片描述][u_4100521287_1077523307_fm_23_gp_0.jpg]

**判断队列是否满：**

**仅凭借Q.front == Q.rear是不足以判断队列是否满，可用的两种处理方法是：**

**1.另外设置一个标志位以区别队列是空还是满**

**2.牺牲一个存储空间，约定以队列头指针在队列尾指针的下一个位置（环状的下一个位置）上作为队列满的标志，即上图d2**

**循环队列有一个明显的问题，存储空间，即队列长度是不可变的，如果无法预知长度，建议使用链式队列**

实现代码：

#include <iostream>
    #include <stdio.h>
    #include <stdlib.h>
    using namespace std;
    
    #define MAXQSIZE 10
    typedef int QElemType;
    typedef struct{
        QElemType * base;
        int font;   //队列头游标
        int rear;   //队列尾游标
    }SqQueue;
    
    //初始化循环队列
    int InitSqQueue(SqQueue &Q){
        Q.base = (QElemType * )malloc(MAXQSIZE*sizeof(QElemType));
        if(!Q.base) return 0;
        Q.font = Q.rear = 0;
        return 1;
    }
    
    //添加元素
    int InsertQueue(SqQueue &Q ,QElemType e){
        if((Q.rear+1) % MAXQSIZE == Q.font) return 0;
        Q.base[Q.rear] = e;
        Q.rear = (Q.rear+1) % MAXQSIZE;
        return 1;
    }
    //删除元素
    int DeQueue(SqQueue &Q,QElemType &e){
        if(Q.font == Q.rear) return -1;
        e = Q.base[Q.font];
        Q.font = (Q.font+1) % MAXQSIZE;
        return 1;
    }
    int QueueLength(SqQueue &Q){
        return (Q.rear - Q.font + MAXQSIZE) % MAXQSIZE;
    }
    int main()
    {
        SqQueue Q;
        InitSqQueue(Q);
        for(int i=0;i<9;i++)
        {
            InsertQueue(Q,i);
        }
        printf("队列中的元素有%d个\n",QueueLength(Q));
        int e;
    
        for(int j=0;j<5;j++)
        {
            DeQueue(Q,e);
            printf("删除元素 e = %d \n",e);
        }
        printf("队列中的元素有%d个\n",QueueLength(Q));
    }

![这里写图片描述][SouthEast]

[25E5_25BE_25AA_25E7_258E_25AF_25E9_25A1_25BA_25E5_25BA_258F_25E9_2598_259F_25E5_2588_2597_25E6_2593_258D_25E4_25BD_259C_25E7_25A4_25BA_25E6_2584_258F_25E5_259B_25BE_1.jpg]: https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1492943261&di=135ea911625589b7fff866b4f5a7afdc&imgtype=jpg&er=1&src=http://images.cnblogs.com/cnblogs_com/dupeng0811/WindowsLiveWriter/5_D050/%25E5%25BE%25AA%25E7%258E%25AF%25E9%25A1%25BA%25E5%25BA%258F%25E9%2598%259F%25E5%2588%2597%25E6%2593%258D%25E4%25BD%259C%25E7%25A4%25BA%25E6%2584%258F%25E5%259B%25BE_1.jpg
[u_4100521287_1077523307_fm_23_gp_0.jpg]: /images/20220617/944de7bd0ff94a678a1a8946f1588067.png
[SouthEast]: /images/20220617/b28183298d6744fa98d7c4d2d643b203.png