队列（循环队列、链式队列）

2024-08-21 23:36
文章标签 队列 循环 链式

本文主要是介绍队列（循环队列、链式队列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

队列 queue

1.1 特性

队列是只允许再两端进行插入和删除操作的线性表，在队尾插入，在队头删除，插入的一段被称为“队尾”，删除的一端被称为“队头”。队列包括顺序队列(循环队列)、链式队列。

结构：先进先出FIFO

操作：创建、入列、出列、判空和判满。

注意：为了避免假溢出问题，即队列前面还有空闲，但是队尾已经出现越界，所以在实际使用队列时，为了使队列空间能重复使用，往往对队列的使用方法稍加改进，需要引入循环队列。

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

1.2 循环队列

逻辑结构：线性结构

存储结构：顺序存储

操作：创建、入列、出列、判空和判满。

入列：

出队：

求长度：

#include <stdio.h>
#include <stdlib.h>
#define N 5
typedef int datatype;
typedef struct sequeue //循环队列结构体
{
    datatype data[N]; //循环队列存数据的数组int front;        //队头元素下标int rear;         //队尾元素下标
} sequeue_t;//创建一个空的队列
sequeue_t *createEmptySequeue()
{//开辟循环队列结构体大小空间sequeue_t *p = (sequeue_t *)malloc(sizeof(sequeue_t));if (NULL == p){perror("p mallo err");return NULL;}//初始化结构体空间
    p->front = 0; //队头和队尾初始化为0
    p->rear = 0;return p;
}//判断队列是否为满
int isFullSequeue(sequeue_t *p)
{//思想上，舍去数组上的一个存储位置,用于判断队列是否为满//先判断rear的下一个位置是否等于frontreturn (p->rear + 1) % N == p->front;
}//入列 data代表入列的数据
int inSequeue(sequeue_t *p, datatype data)
{//1.容错判断，入列前需要判断队列是否为满if (isFullSequeue(p)){printf("isFullSequeue !!\n");return -1;}//2. 将数据入列
    p->data[p->rear] = data;//3.队尾向后移动一个单位 (不能单纯的++，要利用取余法让下标循环)
    p->rear = (p->rear + 1) % N;return 0;
}
//判断队列是否为空
int isEmptySequeue(sequeue_t *p)
{return p->rear == p->front;
}
//出列
datatype outSequeue(sequeue_t *p)
{
    datatype temp; //临时保存下即将出列的数据//1.容错判断: 判空if (isEmptySequeue(p)){printf("isEmptySequeue !!\n");return -1;}//2. 将数据取出
    temp = p->data[p->front];//3. 将头向后移动一个单位
    p->front = (p->front + 1) % N;//4. 返回出队数据return temp;
}//求队列的长度
int lengthSequeue(sequeue_t *p)
{//长度情况分为 rear >= front  和 rear < fron  //rear == front 就是空队列长度为0// if (p->rear >= p->front)//     return p->rear - p->front;// else //p->rear < p->front//     return p->rear - p->front + N;return (p->rear - p->front + N) % N;
}int main(int argc, char const *argv[])
{sequeue_t *p = createEmptySequeue();for (int i = 0; i < 5; i++)inSequeue(p, i); //最后一次循环回报： isFullSequeue !!printf("len = %d\n", lengthSequeue(p)); //len=4while (!isEmptySequeue(p))printf("%d\n", outSequeue(p)); //0 1 2 3先进先出return 0;
}

循环队列，如果数组的元素个数为N，那么队列中最多能够存储的数据数的多少？ N-1个  

为什么？

答：rear 后面 队尾，在插入的时候，插入之前需要先判断 rear+1，也就是他的下一个为位置是否 等于 front 来判断队列是否为满，会造成浪费一个存储位置。

1.3 链式队列

逻辑结构：线性结构

存储结构：链式存储

操作：创空、入列、出列、判空

创建空队列：

入队：

出队：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{
    datatype data;struct node *next;
} node_t, *node_p;typedef struct linkqueue //将队列的头尾指针封装成一个结构体
{
    node_p front; //相当于队列的头指针
    node_p rear;  //相当于队列的尾指针
} linkqueue_t, *linkqueue_p;//创建一个空的队列，用有头链表。
linkqueue_p createEmptyLinkQueue()
{//1. 开辟队列结构体大小空间
    linkqueue_p p = (linkqueue_p)malloc(sizeof(linkqueue_t));if (NULL == p){perror("p malloc er");return NULL;}//2. 初始化队列结构体, 让头尾指针都指向开辟的头节点
    p->front = p->rear = (node_p)malloc(sizeof(node_t));if (NULL == p->front){perror("p->front malloc err");return NULL;}//3. 初始化头节点
    p->front->next = NULL;return p;
}//入列 data代表入列的数据
int inLinkQueue(linkqueue_t *p, datatype data)
{// 新建节点，保存入队数据
    node_p pnew = (node_p)malloc(sizeof(node_t));if (NULL == pnew){perror("pnew malloc err");return -1;}
    pnew->data = data;
    pnew->next = NULL;// 将新节点尾插到链表
    p->rear->next = pnew;// 移动尾指针到新节点
    p->rear = pnew;return 0;
}//判断队列是否为空
int isEmptyLinkQueue(linkqueue_p p)
{return p->front == p->rear;
}//出列
datatype outLinkQueue(linkqueue_p p)
{//判空if (isEmptyLinkQueue(p)){printf("outLinkQueue err\n");return -1;}//定义pdel保存当前头节点
    node_p pdel = p->front;//将头指针向后移动
    p->front = p->front->next;//释放pdelfree(pdel);//将要出队数据返回return p->front->data;
}//求队列长度
int lengthLinkQueue(linkqueue_p p)
{int len = 0;
    node_p h = p->front;//求长度，相当于遍历有头链表while (h->next != NULL){
        h = h->next;
        len++;}return len;
}int main(int argc, char const *argv[])
{
    linkqueue_p p = createEmptyLinkQueue();inLinkQueue(p, 1);inLinkQueue(p, 2);inLinkQueue(p, 3);inLinkQueue(p, 4);inLinkQueue(p, 5);// node_p p1 = p->front;// while (p1->next != NULL)// {//     p1 = p1->next;//     printf("%d ", p1->data);// }printf("len = %d\n", lengthLinkQueue(p));while (!isEmptyLinkQueue(p)){printf("%d\n", outLinkQueue(p)); //1 2 3 4 5}return 0;
}

这篇关于队列（循环队列、链式队列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1094602。

相关文章

C++ RabbitMq消息队列组件详解

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》：本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A
阅读更多...
golang实现延迟队列(delay queue)的两种实现

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列：邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版：go自带的time
阅读更多...
Nginx部署React项目时重定向循环问题的解决方案

Nginx部署React项目时重定向循环问题的解决方案

《Nginx部署React项目时重定向循环问题的解决方案》Nginx在处理React项目请求时出现重定向循环,通常是由于`try_files`配置错误或`root`路径配置不当导致的,本文给大家详细介... 目录问题原因1. try_files 配置错误2. root 路径错误解决方法1. 检查 try_f
阅读更多...
Spring三级缓存解决循环依赖的解析过程

Spring三级缓存解决循环依赖的解析过程

《Spring三级缓存解决循环依赖的解析过程》：本文主要介绍Spring三级缓存解决循环依赖的解析过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、循环依赖场景二、三级缓存定义三、解决流程（以ServiceA和ServiceB为例）四、关键机制详解五、设计约
阅读更多...
Spring 中的循环引用问题解决方法

Spring 中的循环引用问题解决方法

《Spring中的循环引用问题解决方法》：本文主要介绍Spring中的循环引用问题解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录什么是循环引用？循环依赖三级缓存解决循环依赖二级缓存三级缓存本章来聊聊Spring 中的循环引用问题该如何解决。这里聊
阅读更多...
Java的栈与队列实现代码解析

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组
阅读更多...
C# foreach 循环中获取索引的实现方式

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》：本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代
阅读更多...
Redis消息队列实现异步秒杀功能

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结
阅读更多...
Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

Spring Boot循环依赖原理、解决方案与最佳实践(全解析)

《SpringBoot循环依赖原理、解决方案与最佳实践(全解析)》循环依赖指两个或多个Bean相互直接或间接引用,形成闭环依赖关系,：本文主要介绍SpringBoot循环依赖原理、解决方案与最... 目录一、循环依赖的本质与危害1.1 什么是循环依赖？1.2 核心危害二、Spring的三级缓存机制2.1 三
阅读更多...
SpringKafka错误处理(重试机制与死信队列)

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2