C语言队列的实现

c语言队列

//表示队列
typedef struct queue{
    int* arr;//存储区的首地址
    int in;  //存数据的下标
    int out; //取数据的下标
    int cap; //存储区的容量
    int size;//记录队列当中已存入的数据的个数,入队+1，出队-1
}queue_t;

思路：

入队操作：

出队操作:

为什么in和out要置0？

数组的下标范围是 0 ~ cap-1（比如 cap=6 时，下标只能是 0、1、2、3、4、5）。
当不断入队 / 出队时，in 和 out 会不断递增：

• 当 in 增长到 cap 时（比如 cap=6，in 变成 6），已经超出了数组的最大下标（5），此时如果不处理，下次存数据会导致数组越界错误。
• 同理，当 out 增长到 cap 时，也会超出数组下标范围。

因此，当 in == cap 或 out == cap 时，将它们置为 0，相当于让指针 “绕回数组的起始位置”，继续使用前面已经空闲的空间（比如前面的元素已经出队，下标 0、1 等位置空出来了）。

入队置0：

出队置0：

具体代码实现：

1. 队列的头文件

//queue.h文件
//队列的头文件，谁包含我的这个头文件，谁就可以用我这个类型的声明和函数的声明
//头文件卫士，避免头文件被重复包含
#ifndef __QUEUE_H__
#define __QUEUE_H__

//一.类型的声明
//用结构体表示队列
typedef struct queue{
    int* arr;  //存储区的首地址
    int in;    //存数据的下标
    int out;   //取数据的下标
    int cap;   //存储区的容量
    int size;  //记录队列当中已存入的数据的个数，入队+1，出队-1
}queue_t;
//定义队列类型的变量 queue_t queue;
//定义变量的同时得初始化，我们可以将这个初始化操作封装到函数void queueInit(queue_t* p,int cap);里面

//二.函数的声明
//队列的初始化
//参数：指向要初始化的队列的指针；队列的容量
//对指针p所指向的队列进行初始化，容量为cap
void queueInit(queue_t* p,int cap);

//队列的释放
//参数：指向要释放的队列的指针
//对指针p所指向的队列进行释放
void queueDeinit(queue_t* p);

//队列的判空
//参数：指向要判断的队列的指针
//如果指针p所指向的队列为空，返回1；非空则返回0（队列空的判定：size=0）
int queueEmpty(queue_t* p);

//队列的判满
//参数：指向要判断的队列的指针
//如果指针p所指向的队列为满，返回1；非满则返回0（队列满的判定：size=cap）
int queueFull(queue_t* p);

//入队
//参数：指向目标队列的指针；要入队的数据
//将数据存入指针p所指向的队列中
void queuePush(queue_t* p,int data);

//出队
//参数：指向目标队列的指针
//从指针p所指向的队列中取出数据，返回取出的int类型数据
int queuePop(queue_t* p);
#endif

2. 队列的实现

//queue.c文件
#include<stdlib.h> // malloc() free()
#include"queue.h"

//队列的初始化
//参数：指向要初始化的队列的指针；队列的容量
//对指针p所指向的队列进行初始化，分配容量为cap的存储区，初始化in、out为0，size为0
void queueInit(queue_t* p,int cap){
    p->arr = malloc(sizeof(int) * cap);
    p->in = 0;
    p->out = 0;
    p->cap = cap;
    p->size = 0;//初始状态无数据
}

//队列的释放
//参数：指向要释放的队列的指针
//释放指针p所指向的队列的存储区，重置所有成员变量
void queueDeinit(queue_t* p){
    free(p->arr);
    p->arr = NULL;
    p->in = 0;
    p->out = 0;
    p->cap = 0;
    p->size = 0;
}

//队列的判空
//参数：指向要判断的队列的指针
//如果指针p所指向的队列为空（size=0），返回1；非空则返回0
int queueEmpty(queue_t* p){
    return p->size == 0 ? 1 : 0;
}

//队列的判满
//参数：指向要判断的队列的指针
//如果指针p所指向的队列为满（size=cap），返回1；非满则返回0
int queueFull(queue_t* p){
    return p->size == p->cap ? 1 : 0; 
}

//入队
//参数：指向目标队列的指针；要入队的数据
//将data存入指针p所指向的队列中，存储位置为arr[in]，存入后in递增（达到cap时归零），size递增
void queuePush(queue_t* p,int data){
    p->arr[p->in] = data;
    p->in++;
    p->size++;
    //in达到存储极限时归零，实现循环存储
    if(p->in == p->cap){
        p->in = 0;
    }
}

//出队
//参数：指向目标队列的指针
//从指针p所指向的队列中取出数据，取出位置为arr[out]，取出后out递增（达到cap时归零），size递减，返回取出的数据
int queuePop(queue_t* p){
    int data = p->arr[p->out];
    p->out++;
    p->size--;
    //out达到获取极限时归零，实现循环取数
    if(p->out == p->cap){
        p->out = 0;
    }
    return data;
}

3. 队列的使用示例

//main.c文件
#include<stdio.h>
#include"queue.h"

int main(void){

    //定义队列
    queue_t queue;
    //队列的初始化：容量为6
    queueInit(&queue,6);
    int data = 1;
    
    //循环入队，直到队列存满
    //依次存入数据：1 2 3 4 5 6
    //循环结束条件：队列满时停止存入（queueFull返回1）
    while(queueFull(&queue) == 0){
        queuePush(&queue,data);
        data++;
    }

    //循环出队，直到队列为空
    //依次取出并打印数据：1 2 3 4 5 6
    //循环结束条件：队列为空时停止取出（queueEmpty返回1）
    while(queueEmpty(&queue) != 1){
        printf("%d ",queuePop(&queue));
    }
    printf("\n");
    
    //队列的释放
    queueDeinit(&queue);

    return 0;
}

4. linux关于这个的使用步骤

4.1 创建一个文件夹

mkdir queue

4.2 创建三个文件

touch queue.h
touch queue.c
touch main.c

4.3 queue.c和queue.h写完之后验证一下有没有语法错误，看我的queue.o的文件能不能成功生成

gcc -c queue.c

4.4 生成最终的可执行文件

gcc main.c queue.c -o queue

4.5 运行程序

./queue

4.6 运行之后的结果:

1 2 3 4 5 6