数据结构学习系列之循环队列

• 队列的基本概念：
• 队列（Queue）：一种先进先出（FIFO）的线性表；
• 队尾（rear）：允许插入的一端；
• 队头（front）：允许删除的一端；
• 入队列：队列的插入元素的操作；
• 出队列：队列的删除元素的操作；
• 循环队列：
• 即：队列的头尾相接的顺序存储结构；
• 入队列：rear = (rear + 1) % Queue_size；
• 出队列：front = (front + 1) % Queue_size；
• 队空：rear == front；
• 队满：(rear + 1) % Queue_size == front；
• 队列的长度：(rear - front + Queue_size) % Queue_size；
• 入队列：

int push_loop_queue(queue_t *loop_queue,int data)
{

    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_full(loop_queue))
    {
        printf("此时队列已满，入队失败\n");
        return -1;
    }

    loop_queue->a[loop_queue->rear] = data;
    loop_queue->rear = (loop_queue->rear + 1) % N;
    return 0;

}

• 出队列：

int pop_loop_queue(queue_t *loop_queue,int *data)
{
    if(NULL == loop_queue || NULL == data)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_empty(loop_queue))
    {
        printf("此时队列为空，出队失败\n");
        return -1;
    }

    *data = loop_queue->a[loop_queue->front];
    loop_queue->front = (loop_queue->front + 1) % N;
    return 0;

}

• 示例代码：
• loop_queue.h:

#ifndef __LOOP_QUEUE_H__
#define __LOOP_QUEUE_H__

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N 6

typedef struct Loop_Queue{

    int a[N];
    int front;
    int rear;
   
}queue_t;

int create_loop_queue(queue_t **p);
int queue_is_full(queue_t *loop_queue);
int push_loop_queue(queue_t *loop_queue,int data);
int queue_is_empty(queue_t *loop_queue);
int pop_loop_queue(queue_t *loop_queue,int *data);
int clean_loop_queue(queue_t *loop_queue);
int destroy_loop_queue(queue_t **loop_queue);
int print_loop_queue(queue_t *loop_queue);


#endif

• loop_queue.c:

#include "loop_queue.h"

//创建队列
int create_loop_queue(queue_t **p)
{

    if(NULL == p)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    *p = (queue_t *)malloc(sizeof(queue_t));

    if(NULL == *p)
    {
        printf("内存分配失败\n");
        return -1;
    }

    memset(*p,0,sizeof(queue_t));

    return 0;

    
}

//判断队列是否为满
int queue_is_full(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    return (loop_queue->rear + 1) % N == loop_queue->front ? 1 : 0;

}

//入队列
int push_loop_queue(queue_t *loop_queue,int data)
{

    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_full(loop_queue))
    {
        printf("此时队列已满，入队失败\n");
        return -1;
    }

    loop_queue->a[loop_queue->rear] = data;
    loop_queue->rear = (loop_queue->rear + 1) % N;
    return 0;

}

//判断队列是否为空
int queue_is_empty(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    return loop_queue->rear == loop_queue->front ? 1 : 0;

}

//出队列
int pop_loop_queue(queue_t *loop_queue,int *data)
{
    if(NULL == loop_queue || NULL == data)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    if(queue_is_empty(loop_queue))
    {
        printf("此时队列为空，出队失败\n");
        return -1;
    }

    *data = loop_queue->a[loop_queue->front];
    loop_queue->front = (loop_queue->front + 1) % N;
    return 0;

}

//清空队列
int clean_loop_queue(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    loop_queue->front = 0;
    loop_queue->rear = 0;
    return 0;

}

//销毁队列
int destroy_loop_queue(queue_t **loop_queue)
{
    if(NULL == loop_queue || NULL == *loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    free(*loop_queue);
    *loop_queue = NULL;
    return 0;

}

//遍历队列的元素
int print_loop_queue(queue_t *loop_queue)
{
    if(NULL == loop_queue)
    {
        printf("入参合理性检查\n");
        return -1;
    }

    int i = loop_queue->front;
    while(i != loop_queue->rear)
    {

        printf("%d ",loop_queue->a[i]);

        i = (i + 1) % N;
    }
    puts("");
    return 0;

}

• main.c:

#include "loop_queue.h"

int main(int argc, char const *argv[])
{
    queue_t *loop_queue = NULL;
    create_loop_queue(&loop_queue);
    printf("loop_queue = %p\n",loop_queue);


    //入队
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,33);
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,66);
    push_loop_queue(loop_queue,11);
    push_loop_queue(loop_queue,99);
    


    print_loop_queue(loop_queue);

    //出队
    int data;
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    pop_loop_queue(loop_queue,&data);
    printf("%d ", data);
    puts("");
    pop_loop_queue(loop_queue,&data);
   


    clean_loop_queue(loop_queue);
    print_loop_queue(loop_queue);

    destroy_loop_queue(&loop_queue);
    printf("loop_queue = %p\n",loop_queue);

    return 0;
}

• 运行结果：

loop_queue = 0x562e9a67b260
此时队列已满，入队失败
11 33 11 66 11 
11 33 11 66 11 
此时队列为空，出队失败

loop_queue = (nil)

• 注意：
• 本示例代码的存储空间预设可以存储6个元素，但是实际上只能存储5个元素；
• 虽然浪费了1个存储空间，却给判断队列是否为满提供了便利；
• 本示例代码，仅供参考；