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;//队列的初始化：容量为6queueInit(&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