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

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。

相关文章

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

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

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

hdu1180（广搜+优先队列）

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

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
Java并发编程之——BlockingQueue（队列）

Java并发编程之——BlockingQueue（队列）

一、什么是BlockingQueue BlockingQueue即阻塞队列，从阻塞这个词可以看出，在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种： 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被阻塞，除非有另一个线程做了出队列操作；同样，当一个线程试图对一个空
阅读更多...
FreeRTOS学习笔记（六）队列

FreeRTOS学习笔记（六）队列

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档 文章目录 前言一、队列的基本内容1.1 队列的引入1.2 FreeRTOS 队列的功能与作用1.3 队列的结构体1.4 队列的使用流程 二、相关API详解2.1 xQueueCreate2.2 xQueueSend2.3 xQueueReceive2.4 xQueueSendFromISR2.5 xQueueRecei
阅读更多...
校验码：奇偶校验，CRC循环冗余校验，海明校验码

校验码：奇偶校验，CRC循环冗余校验，海明校验码

文章目录 奇偶校验码CRC循环冗余校验码海明校验码 奇偶校验码 码距：任何一种编码都由许多码字构成，任意两个码字之间最少变化的二进制位数就称为数据检验码的码距。 奇偶校验码的编码方法是：由若干位有效信息(如一个字节)，再加上一个二进制位(校验位)组成校验码。 奇校验：整个校验码中1的个数为奇数 偶校验：整个校验码中1的个数为偶数 奇偶校验，可检测1位（奇数位）的错误，不可纠错。
阅读更多...
多线程篇（阻塞队列- LinkedBlockingDeque）（持续更新迭代）

多线程篇（阻塞队列- LinkedBlockingDeque）（持续更新迭代）

目录 一、LinkedBlockingDeque是什么 二、核心属性详解 三、核心方法详解 addFirst(E e) offerFirst(E e) putFirst(E e) removeFirst() pollFirst() takeFirst() 其他 四、总结 一、LinkedBlockingDeque是什么 首先queue是一种数据结构，一个集合中
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2