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

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。

相关文章

如何通过Python实现一个消息队列

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque
阅读更多...
Python中顺序结构和循环结构示例代码

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》：本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句（1）条件语句的定义（2）条件语句的语法（a）单分支 if（b）双分支 if-else（
阅读更多...
解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列？消费者组的工作方式每
阅读更多...
Python判断for循环最后一次的6种方法

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for
阅读更多...
Java循环创建对象内存溢出的解决方法

Java循环创建对象内存溢出的解决方法

《Java循环创建对象内存溢出的解决方法》在Java中,如果在循环中不当地创建大量对象而不及时释放内存,很容易导致内存溢出（OutOfMemoryError）,所以本文给大家介绍了Java循环创建对象... 目录问题1. 解决方案2. 示例代码2.1 原始版本（可能导致内存溢出）2.2 修改后的版本问题在
阅读更多...
Redis延迟队列的实现示例

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi
阅读更多...
JAVA中while循环的使用与注意事项

JAVA中while循环的使用与注意事项

《JAVA中while循环的使用与注意事项》：本文主要介绍while循环在编程中的应用,包括其基本结构、语句示例、适用场景以及注意事项,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录while循环1. 什么是while循环2. while循环的语句3.while循环的适用场景以及优势4. 注意
阅读更多...
Python中的异步:async 和 await以及操作中的事件循环、回调和异常

Python中的异步:async 和 await以及操作中的事件循环、回调和异常

《Python中的异步:async和await以及操作中的事件循环、回调和异常》在现代编程中,异步操作在处理I/O密集型任务时,可以显著提高程序的性能和响应速度,Python提供了asyn... 目录引言什么是异步操作？python 中的异步编程基础async 和 await 关键字asyncio 模块理论
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2