Linux C语言实现-------队列

71 阅读 0 评论 47 点赞

我是靠谱客的博主温暖白猫，最近开发中收集的这篇文章主要介绍Linux C语言实现-------队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1 什么是队列:

老规矩，先上一张数据结构的图(1):

图1

希望同学们对这张图加以深刻的理解，对于以后数据结构会有很大的帮助的

图中说明了队列(FIFO)是和栈(STACK) ，线性表(LIST)(链表，数组），同属于是线性结构，线性结构存储方式分为顺序存储方式和链式存储方式，上一章的栈已经分别实现了，小伙伴可以看下源码自行体验下，带的有注释的

队列和栈一样，也是属于一种受限的线性表，其特性为跟栈是相反的，为先进先出

其只能在其中一端进行插入，叫做队尾(rear), 另一端进行删除，叫做队头(front)，在队列中入队n个元素话，队列中的元素如下(a1, a2...an)，当前a1为队头，an为队尾, 因为先进先出的关系，出队也只能从a1,a2...依次到an的方式出队，如下图2:

图2

继续用车来做个比喻吧，一个火车通过山洞(队列),从第一节(队头)车厢(数据)先进去，到山洞的另一头，同样也是第一节车厢先出去，依次才到后面的2...n节车厢

2 队列的实现:

因为是线性表，同样是顺序的方式和链式两种实现

首先是顺序队列:

建立顺序队列，首先要为其静态(数组)或者动态申请(malloc)开辟一块空间,这块空间的大小取决于队列里数据的总大小，队尾(rear)指针始终指向队列的最后一个元素,每次入队操作rear+1, 队头始终指向队列第一次元素,每次出队操作front+1, 因为考虑到内存的合理利用，每次入队或者出队的长度超过队列的总长度的时候，就让它指向队列的第一个元素位置, 即 rear = (rear + 1) % max，front = (front + 1) % max，此时的队列就形成了一个可以循环利用的环形，我们称之为循环队列。

在循环队列中，判断队列是否为空front == rear , 而是否为满也是front == read，于是乎聪明的先烈们想了个办法，放弃队列中的一个节点，用来判断是否队满，即 (read + 1) % N == front ? 1 : 0。

理一下思路吧

1，队头始终指向出队的元素的位置

2，队尾始终指向入队的元素的位置

1，创建一个空队列，此时的rear = front = 0;

2, 判断是否空队， rear == front ? 1 : 0

2, 判断是否满队， front == (rear + 1) % max ? 1 : 0

3，如果不是满队，入队 data[rear] = data ; read = (rear + 1) % max;

4, 如果不是空队，出队 data = data[front]; front = (front + 1) % max;

代码如下:

//queue.h

#ifndef __FIFO_H__
#define __FIFO_H__
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
#define N 16 //定义队列最大存储元素数量-1
typedef struct {
data_t data[N];
int front;
int rear;
}Queue;
Queue *queue_create(void );
int is_queue_empty(Queue *handle);
int is_queue_full(Queue *handle);
int en_queue(Queue *handle, data_t data);
int de_queue(Queue *handle, data_t *data);
int destroy_queue(Queue *handle);
#endif //__FIFO_H__

//queue.c

#include "queue.h"
Queue *queue_create(void) //init 一个空队列
{
Queue *handle = (Queue *)malloc(sizeof(Queue));
if (NULL == handle) {
printf("malloc handle fail ! n");
return NULL;
}
handle->front = handle->rear = 0; //队首和队尾同时指向队列第一个元素
return handle;
}
int is_queue_empty(Queue *handle)
{
if (NULL == handle) {
return -1;
}
return (handle->front == handle->rear ? 1 : 0); //空为1，否则为0
}
int is_queue_full(Queue *handle)
{
if (NULL == handle) {
return -1;
}
return ((handle->rear + 1) % N == handle->front ? 1 : 0); //满为1，否则为0
}
int en_queue(Queue *handle, data_t data)
{
if (handle == NULL) {
return -1;
}
if (is_queue_full(handle) == 1) { //满对不能入队
return -1;
}
handle->data[handle->rear] = data; //添加元素到对尾指向的位置
handle->rear = (handle->rear + 1) % N; //++队尾 % N
return 0;
}
int de_queue(Queue *handle, data_t *data)
{
if (NULL == handle) {
return -1;
}
if (is_queue_empty(handle) == 1) { //空队不能出队
return -1;
}
if (data != NULL) {
*data = handle->data[handle->front]; //传队首元素的值出去
}
handle->front = (handle->front + 1) % N; //++队首 % N
return 0;
}
int destroy_queue(Queue *handle)
//销毁
{
if (NULL != handle) {
free(handle);
}
return 0;
}

//test.c

#include "queue.h"
int main(void)
{
int i, num = 0, ret;
Queue *handle = queue_create(); //1,Init 空队列
for (i = 0; i < N+4; i++) {//N+4
num = i + 1;
en_queue(handle, num); //2,故意入队超过N(16)的长度
}
while (ret = de_queue(handle, &num) != -1) { //3, 出队,测试入队数据是否正常
printf("%d ", num);
}
printf("n");
destroy_queue(handle); //4, 销毁队列
return 0;
}

运行结果:

经测试入队出队正常，超过定长 16-1 个数据即不会入队

//链式队列如图2:

图2

跟顺序队列一样，队头始终指向第一个入队的元素，队尾始终指向最后入队的元素，只是数据存储的物理地址不是连续开辟的，需要我们用节点的方式，通过next指针链接起来，代码如下

//queue.h

#ifndef __FIFO_H__
#define __FIFO_H__
#include <stdio.h>
#include <stdlib.h>
typedef int data_t;
#define MAX 16
typedef struct node_t {
data_t data;
struct node_t *next;
}Queue_node, *Queue;
typedef struct list_queue_head{
Queue rear, front;
}*list_queue_t;
list_queue_t queue_create(void);
int is_queue_empty(list_queue_t handle);
int is_queue_full(list_queue_t handle);
int en_queue(list_queue_t handle, data_t data);
int de_queue(list_queue_t handle, data_t *data);
int destroy_queue(list_queue_t handle);
void queue_clear(list_queue_t handle);
#endif //__FIFO_H__

//queue.c

#include "queue.h"
list_queue_t queue_create(void) //初始化一个空队列
{
list_queue_t handle = (list_queue_t)malloc(sizeof(struct list_queue_head)); //初始化一个队列的head, 只有rear和front指针,没有数据域
if (NULL == handle) return NULL;
handle->rear = handle->front = (Queue )malloc(sizeof(struct node_t)); //给队首和队尾指针申请空间
if (handle->rear == NULL) return NULL;
handle->front->next = NULL; //此时队列为空
return handle;
}
int is_queue_empty(list_queue_t handle) //判断是否空队列
{
if (NULL == handle) return -1;
return (NULL == handle->front->next ? 1 : 0); //如果为空返回1，否则返回0
}
int de_queue(list_queue_t handle, data_t *data) //出队
{
if (NULL == handle || is_queue_empty(handle))
return -1;
//判断是否空队
Queue remove = handle->front->next; //保存当前队首节点
handle->front->next = remove->next; //队首节点指向它的下一个节点
if (NULL != data) {
*data = remove->data; //当前队首节点的数据传出去
}
free(remove); //数据已经传出去了 ， free当前队首节点
return 0;
}
int en_queue(list_queue_t handle, data_t data)//入队
{
if (NULL == handle || NULL == handle->rear) return -1;
Queue node_t = (Queue )malloc(sizeof(struct node_t)); //新节点申请空间
if (NULL == node_t) return -1;
node_t->data = data; //新节点赋值
node_t->next = NULL; //新节点的next指针始终指向NULL
if (handle->rear == handle->front) { //如果是队列里第一个数据元素节点
handle->rear = node_t; //队尾指向新节点，下次添加数据队尾的next指针才能正确指向node_t
handle->front->next = handle->rear; //队首的第一个数据指向当前新节点
} else {
handle->rear->next = node_t; //新节点链接到队尾
handle->rear = node_t; //队尾指向新节点，下次添加数据队尾的next指针才能正确指向node_t
}
return 0;
}
void queue_clear(list_queue_t handle)
{
if (NULL == handle) return;
Queue remove; //临时保存数据节点
while (handle->front->next) {
remove = handle->front->next; //保存队首有数据的节点
handle->front->next = handle->front->next->next; //当前队首指向下一个节点
free(remove); //当前队首已经指向下一个节点，free掉当前队首节点
}
handle->rear = handle->front; //队尾指针指向数据已经free，重新指向队首
}
int destroy_queue(list_queue_t handle)
//销毁队列
{
if (NULL != handle) {
queue_clear(handle);
free(handle->front); //clear只是free了所有的next指针, 初始化时申请的front指针这里还需要free掉
free(handle);
}
return 0;
}

//test.c

#include "queue.h"
int main(void)
{
int i, num, ret;
list_queue_t handle = queue_create(); //1,Init 一个空队列
for (i = 0; i < MAX; i++) {
num = i + 1;
en_queue(handle, num);
//2,入队操作
}
printf("出队: n");
while (ret = de_queue(handle, &num) != -1) { //3, 出队,测试入队数据是否正常
printf("%d ", num);
}
printf("n");
queue_clear(handle); //4, 清空队列， 继续测试出队
printf("清空之后出队: n");
while (ret = de_queue(handle, &num) != -1) { //5, 出队, 测试清空函数是否正确
printf("%d ", num);
}
printf("n");
destroy_queue(handle); //6 销毁队列
return 0;
}

运行结果: