数据结构严薇敏——循环队列的顺序存储（C语言）

落日映苍穹つ 2022-05-18 01:54 211阅读 0赞

**循环队列和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放数据元素外，还需要定义两个指针分别指向队头和队尾。**

**它的数据结构定义为：**

typedef int ElemType;
    typedef struct SqCQueue
    {
        ElemType *base;
        int front;
        int rear;
        int size;   //用来计数当前队列中元素的个数
    }SqCQueue;

**在非空队列中，头指针始终指向队头元素，尾指针始终指向队尾元素的下一个位置。**

![20150909084659_0685.jpg][]

**关于循环队列计算元素的个数：**

队列头指针为front，队列尾指针为rear，队列容量为MAX_SIZE

队空：front == rear
    队满：(rear+1) % MAX_SIZE == front
    队中元素个数：（rear-front+maxsize ) % MAX_SIZE 
    入队：rear=(rear+1) % MAX_SIZE ;
    出队：front=(front+1) % MAX_SIZE;

## 代码 ##

** 头文件\#include"SqCQueue.h"**

#ifndef SQCQUEUE_H_INCLUDED
    #define SQCQUEUE_H_INCLUDED
    
    #include<stdio.h>
    #include<stdlib.h>
    
    #define MAX_SIZE 20
    #define TRUE 1
    #define FALSE 0
    
    typedef int ElemType;
    typedef struct SqCQueue
    {
        ElemType *base;
        int front;
        int rear;
        int size;   //用来计数当前队列中元素的个数
    }SqCQueue;
    
    //初始化一个空队
    SqCQueue *Init_CQueue();
    //销毁
    void Destory_CQueue(SqCQueue *S);
    //清空队列
    void Clear_CQueue(SqCQueue *S);
    //是否为空
    int IsEmpty_CQueue(SqCQueue *S);
    //队列的长度
    int Length_CQueue(SqCQueue *S);
    //返回队头元素
    ElemType GetHead_CQueue(SqCQueue *S);
    //进队
    void Enter_CQueue(SqCQueue *S,ElemType e);
    //出队
    ElemType Delete_CQueue(SqCQueue *S);
    //遍历
    void Traverse_CQueue(SqCQueue *S);
    
    #endif // SQCQUEUE_H_INCLUDED

**头文件函数实现SqCQueue.c：**

#include"SqCQueue.h"
    
    //初始化一个空队
    SqCQueue *Init_CQueue()
    {
        SqCQueue *S = (SqCQueue*)malloc(sizeof(SqCQueue));
        S->base = (ElemType *)malloc(MAX_SIZE * sizeof(ElemType));
        S->front = S->rear = 0;
        S->size = 0;
        printf("循环队列创建成功！\n");
        return S;
    }
    //销毁
    void Destory_CQueue(SqCQueue *S)
    {
        free(S);
        printf("循环队列销毁成功\n");
    }
    //清空队列
    void Clear_CQueue(SqCQueue *S)
    {
        if(IsEmpty_CQueue(S))
        {
            printf("队列为空，无需清空！\n");
            return;
        }
        S->front = S->rear = 0;
        S->size = 0;
        printf("循环队列清空成功\n");
    }
    //是否为空
    int IsEmpty_CQueue(SqCQueue *S)
    {
        if(S->size == 0)
            return TRUE;
        else return FALSE;
    
    }
    //队列的长度
    int Length_CQueue(SqCQueue *S)
    {
        return S->size;
    }
    //返回队头元素
    ElemType GetHead_CQueue(SqCQueue *S)
    {
        if(IsEmpty_CQueue(S))
        {
            printf("队列为空！\n");
            return -1;
        }
    
        return S->base[S->front];
    }
    //进队
    void Enter_CQueue(SqCQueue *S,ElemType e)
    {
        if((S->rear + 1) % MAX_SIZE == S->front)
        {
            printf("队列已满！");
            return;
        }
        S->base[S->rear] = e;
        S->rear = (S->rear + 1) % MAX_SIZE;
        S->size++;
    }
    //出队
    ElemType Delete_CQueue(SqCQueue *S)
    {
        ElemType e;
        if(IsEmpty_CQueue(S))
        {
            printf("队列为空！");
            return;
        }
        e = S->base[S->front];
        S->front = (S->front + 1) %MAX_SIZE;
        S->size--;
        return e;
    }
    //遍历
    void Traverse_CQueue(SqCQueue *S)
    {
        if(IsEmpty_CQueue(S))
        {
            printf("队列为空！\n");
            return;
        }
        int i;
        ElemType f = S->front;
        for(i = 0; i < S->size; i++)
        {
            printf("%d\t",S->base[f]);
            f++;
        }
        printf("\n队列遍历成功！\n");
    
    }

**主函数main.c**

#include<stdio.h>
    #include<stdlib.h>
    
    #include"SqCQueue.h"
    
    
    void testC()            //测试循环队列
    {
        SqCQueue *S = Init_CQueue();
    
        int i;
        for(i = 0;i < 5;i++)
        {
            Enter_CQueue(S,i);
        }
        Traverse_CQueue(S);
        printf("队列当前的长度为：%d\n",Length_CQueue(S));
    
        printf("删除当前的队头元素为：%d\n\n",Delete_CQueue(S));
        Traverse_CQueue(S);
        printf("队列当前的长度为：%d\n\n",Length_CQueue(S));
        printf("当前的队头元素是：%d\n",GetHead_CQueue(S));
        Clear_CQueue(S);
        printf("队列当前的长度为：%d\n\n",Length_CQueue(S));
        Destory_CQueue(S);
    
    }
    int main()
    {
        testC();
        system("pause");
        return 0;
    }

[20150909084659_0685.jpg]: http://image.codes51.com/Article/image/20150909/20150909084659_0685.jpg