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

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

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

它的数据结构定义为：

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

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

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

队列头指针为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;
}