循环队列（线性）

队列遵循先进先出的原则，一般从队尾插入，从队头删除。指向队头的指针称为front，队尾指针为rear。（目的是为了方便插入和删除元素）

循环队列（线性）-LMLPHP

假设队列一共有五个元素，当没有元素的时候，front和rear指针都指向下标为0的位置。当有元素的时候，front指向队头，rear指向队尾元素的下一个位置。

循环队列（线性）-LMLPHP

顺序表的队列，当删除和插入几个元素后，就会出现假溢出的情况。

假溢出：数组还有空闲的位置，但是数组末尾数组已经占用，再往后加，就会产生数组越界的错误。

循环队列（线性）-LMLPHP

所以提出了循环队列的概念。

循环队列（线性）-LMLPHP

当rear指针指向第五个下标的时候，在插入一个数据，rear指针加加，就到了0下标的位置。

这时，判断队列满或者空的时候就不能单纯看rear和front指针的大小了。

循环队列（线性）-LMLPHP

判断方法：判空：front == rear 判满：front == （rear+1）%SIZE

SIZE是指数组的长度

代码如下：

头文件

#pragma once
#include <stdbool.h>
//顺序表实现环形队列
//环形的目的是为了提高出队的时间复杂度
//浪费一个单元不使用，是为了区分队满和队空

#define SIZE 10
typedef struct SQueue
{
    int elem[SIZE];
    int front;//队头指针，第一个元素的下标
    int rear;//队尾指针，最后一个元素的下一个下标,当前可以存放数据的下标
}SQueue,*PSQueue;

//初始化
void InitQueue(PSQueue ps);

//入队
bool Push(PSQueue ps,int val);

//获取队头的值，但不删除
bool GetTop(PSQueue ps,int *rtval);

//获取队头的值，且删除
bool Pop(PSQueue ps,int *rtval);

//判断队空
bool IsEmpty(PSQueue ps);

bool Clear(PSQueue ps);

bool Destroy(PSQueue ps);

cpp文件

#include <stdio.h>
#include <assert.h>
#include "squeue.h"
//顺序表实现环形队列
//环形的目的是为了提高出队的时间复杂度
//浪费一个单元不使用，是为了区分队满和队空

void InitQueue(PSQueue ps)
{
assert(ps != NULL);
if(ps == NULL)
{
return ;
}
ps->front = 0;
ps->rear = 0;
}

static bool IsFull(PSQueue ps)
{
return (ps->rear+1)%SIZE == ps->front;
}
//入队
bool Push(PSQueue ps,int val)
{
assert(PS != NULL);
if(IsFull(ps))
{
return false;
}
ps->elem[ps->rear] = val;
ps->rear = (ps->rear+1)%SIZE;

return true;
}

//获取队头的值，但不删除
bool GetTop(PSQueue ps,int *rtval)
{
   assert(ps!= NULL);
if(IsEmpty(ps))
{
   return false;
}
if(rtval != NULL)
{
   *rtval = ps->elem[ps->front];
}

return true;
}

//获取队头的值，且删除
bool Pop(PSQueue ps,int *rtval)
{
   GetTop(ps,rtval)；
   ps->front = (ps->front+1)%SIZE;
   return true;
}

//判断队空
bool IsEmpty(PSQueue ps)
{
return ps->front == ps->rear;
}

bool Clear(PSQueue ps)
{
ps->front = 0;
ps->rear = 0;
}

bool Destroy(PSQueue ps)
{
Cleaar(ps);
}

主函数

#include <stdio.h>
#include "squeue.h"

int main()
{
    SQueue ps;
    InitQueue(&ps);
    for(int i=0;i<15;i++)
    {
	Push(&ps,i);
    }
    int tmp;
    while(!IsEmpty(&ps))
    {
	Pop(&ps,&tmp);
	printf("%d\n",tmp);
    }
    return 0;
}

晨光微雨

循环队列（线性）