首页 > 其他分享 >数据结构day04（队列 Queue 循环队列、链式队列）

数据结构day04（队列 Queue 循环队列、链式队列）

时间：2024-08-23 21:21:51浏览次数：13  
标签：return 队列 day04 Queue int front rear 指针

目录

【1】队列 Queue

1》 队列的定义

 2》循环队列

3》链式队列 

【1】队列 Queue

1》 队列的定义

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。


队头（Front）：允许删除的一端，又称队首。
队尾（Rear）：允许插入的一端。
空队列：不包含任何元素的空表。

队列包括顺序队列(循环队列)、链式队列。

结构：先进先出FIFO

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

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

 2》循环队列

解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。当队首指针Q->front = MAXSIZE-1后，再前进一个位置就自动到0，这可以利用除法取余运算（%）来实现。

初始时：Q->front = Q->rear=0。
队首指针进1：Q->front = (Q->front + 1) % MAXSIZE。
队尾指针进1：Q->rear = (Q->rear + 1) % MAXSIZE。
队列长度：(Q->rear - Q->front + MAXSIZE) % MAXSIZE。

出队入队时，指针都按照顺时针方向前进1，如下图所示：

 代码展示：

#include <stdio.h>
#include <stdlib.h>
#define N 10

typedef int data_t; // 重定义int类型
typedef struct queue
{
    data_t data[N]; //循环队列存数据的数组
    int front;      // 队头元素的下标
    int rear;       // 队尾元素的下标
} Que_t, *Que_p;    // 重定义队列结构体类型

/*创建空队列*/
Que_p Create()
{
    Que_p p = (Que_p)malloc(sizeof(Que_t));//开辟循环队列结构体大小空间
    if (NULL == p)//容错判断
    {
        perror("malloc lost\n");
    }
    //结构体初始化
    p->front = 0;//队头下标置0
    p->rear = 0;//队尾下标置0
    return p;//返回队列指针
}

/*判满*/
//思想上，舍去数组上的最后一个存储位置,用于判断队列是否为满，即这个位置不存数据
int Full(Que_p p)
{
    return (p->rear + 1) % N == p->front;//通过取余法，让p_rear在0-N 之间循环起来，当p_rear再次等于p_front时就是队列满的时候
}

/*入队列*/
int Push(Que_p p, int data)
{
    if (Full(p))//判满，容错判断
    {
        printf("Queue is Full\n");
        return -1;
    }
    p->data[p->rear] = data;//在队尾下标的数组位置插入要插入的数据
    p->rear = (p->rear + 1) % N;//让队尾下标再0-N 之间进行循环加一
}

/*判空*/
int Empty(Que_p p)
{
    return p->rear == p->front;//当队尾下标等于队头下标时，就像刚开辟空队列时一样，队列为空
} 

/*出队列*/
int Pop(Que_p p)
{
    if (Empty(p))//判空，容错判断
    {
        printf("Queue is Empty\n");
        return -1;
    }
    while (p->front < p->rear)
    {
        printf("%d ", p->data[p->front]);//打印队头下标的数组元素数据
        p->front = (p->front + 1) % N;//让队头下标在0-N 之间循环加一
    }
    printf("\n");
}

/*求长度*/
int Length(Que_p p)
{
    return (p->rear - p->front + N) % N;//两种情况 1.rear在front后面 长度就是rear - front
                                                 //        2.rear在front的前面  长度就是rear - front + N 
                                                 //这两种情况最终可以用(p-rear - p->front + N)% N来表示（取余法）
}

int main(int argc, char const *argv[])
{
    Que_p H = Create();//创空循环队列

    for (int i = 0; i < 9; i++)//循环调用入队列函数，入队列
    {
        Push(H, i);
    }

    printf("队列的长度： %d\n",Length(H));//调用求队列的长度函数
    printf("出队列：");
    Pop(H);//调用出队列函数 先进先出 

    return 0;
}

代码展示：

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

为什么？

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

3》链式队列 

逻辑结构：线性结构

存储结构：链式存储

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

创建空队列：

 入队：

出队：

 

 代码展示：

#include <stdio.h>
#include <stdlib.h>

typedef struct node // 定义一个结构体，存放的是节点的数据域和指针域
{
    int data;          // 数据域
    struct node *next; // 指针域
} Node_t, *Node_p;     // 重定义结构体数据类型和指针

typedef struct link // 定义一个结构体，存放的是指向队头和队尾的node结构体指针
{
    Node_p front;  // 队头指针
    Node_p rear;   // 队尾指针
} Link_t, *Link_p; // 重定义

/*创建空的队列，并创建一个指针结构体指向队列的头*/
Link_p Create()
{
    Link_p p = (Link_p)malloc(sizeof(Link_t)); // 开辟堆区空间存放一个存放指针的结构体，让该指针类型的指针接受该内存空间
    if (NULL == p)                             // 容错判断
    {
        printf("malloc lost\n");
        return NULL;
    }
    p->front = p->rear = (Node_p)malloc(sizeof(Node_t)); // 让上一个结构体内的两个指针都指向开辟的一个存放节点的堆区空间
    if (NULL == p->front)                                // 容错判断
    {
        printf("malloc lost\n");
        return NULL;
    }
    p->front->next = NULL; // 通过存放指针的结构体找到节点的指针域next，并初始化为NULL
    return p;
}

/*入队列*/
int Push(Link_p p, int data)
{
    Node_p p_new = (Node_p)malloc(sizeof(Node_t)); // 让一个新的node类型的指针指向开辟的新的节点堆区空间
    if (NULL == p_new)                             // 容错判断
    {
        printf("malloc lost\n");
        return -1;
    }
    p_new->data = data; // 新节点数据域初始化
    p_new->next = NULL; // 新节点指针域初始化

    p->rear->next = p_new; // 将新节点链接到队列中
    p->rear = p_new;       // 让队尾移动到新节点位置
}

/*判空*/
int Empty(Link_p p)
{
    return p->front == p->rear; // 当队头和队尾重合时 说明队列是空的
}

/*出队列*/
int Pop(Link_p p)
{
    if (Empty(p)) // 判空
    {
        printf("queue is Empty\n");
        return -1;
    }
    while (p->front < p->rear) // 当队头没到达队尾的位置，就进入循环
    {
        Node_p p_del = NULL;           // 定义一个指针p_del,初始化为NULL
        p_del = p->front;              // 让该指针指向队头
        p->front = p->front->next;     // 队头往后移动
        printf("%d ", p->front->data); // 打印当前队头的数据
        free(p_del);                   // 释放掉怕p_del所指的节点
        p_del = NULL;                  // 置空，以防野指针
    }
}

/*队列的长度*/
int Length(Link_p p)
{
    int len = 0;//定义一个变量保存队列长度
    Node_p q = p->front->next;//定义一个结构体指针，指向头节点的下一个节点
    while (q != NULL)//当q不为NULL，进入循环
    {
        len++;//队列长度加一
        q = q->next;//q指针指向下一个节点
    }
    return len;//返回队列长度
}
int main(int argc, char const *argv[])
{
    Link_p H = Create();        // 创建一个空结构体
    for (int i = 0; i < 6; i++) // 循环调用入队列函数
        Push(H, i);
    printf("队列的长度： %d\n", Length(H));
    printf("出队列： ");
    Pop(H); // 调用出队列函数  队列：先入先出
    printf("\n");
    return 0;
}

运行结果：

 今天的分享就到这里结束啦，如果有哪里写的不好的地方，请指正。
如果觉得不错并且对你有帮助的话请给个三连支持一下吧！

标签：return,队列,day04,Queue,int,front,rear,指针
From： https://blog.csdn.net/dghbs/article/details/141403320

相关文章

  • 洛谷P10878 [JRKSJ R9] 在相思树下 III && 单调队列
    传送门：P10878[JRKSJR9]在相思树下III将军啊，早卸甲，他还在廿二，等你回家……一道练习单调队列的好题qwq题目意思：很明白了，不再复述。（注意$\foralli$表示对于任意的i，可理解为所有）思路：贪心是很明显的，因为我们要让最后的值最大，首先要把小的值删掉。最后的答案就是进......
  • OceanBase-clog、日志-队列积压-dump tenant info
    dumptenantinfo日志中搜索dumptenantinfo关键字，可看到租户的规格，线程，队列，请求统计等信息。这条日志每个租户每10s打印一次。查询办法：  grep'dumptenantinfo.*observer.log日志：tenant={id:1002'log/observer.log.*[2021-05-1016:56:22.564978]INFO [SERVER.OMT]......
  • 消息队列作用（解耦、异步、削峰）
    原文：消息队列作用（解耦、异步、削峰）图详解一、消息队列简介简单来说，“消息队列”是在消息的传输过程中保存消息的容器。MQ全称为MessageQueue，消息队列（MQ）是一种应用程序对应用程序的通信方法。应用程序通过读写出入队列的消息（针对应用程序的数据）来通信。消息传递指的是程......
  • Little Bird（单调队列优化的DP）
    题目描述有一排\(n\)棵树，第\(i\)棵树的高度是\(d_i\)。有一只鸟要从第\(1\)棵树飞到第\(n\)棵树。如果鸟降落在第\(i\)棵树，那么它下一步可以降落到第\(i+1,i+2,\dots,i+k\)棵树之中的一棵。如果鸟降落到一棵不矮于当前树的树，那么它的劳累值会\(+1\)，否则不会。求劳累值的最小值......
  • Sound（单调队列）
    题目描述第一行有三个整数\(n,m,c(1\leqn\leq10^6,1\leqm\leq10^4,0\leqc\leq10^4)\)。第二行\(n\)个非负整数\(a_1,a_2,\dots,a_n(1\leqa_i\leq10^6)\)。求有多少个i满足[i...i+m-1]区间的极差<=c输出从小到大输出所有满足条件的\(i\)，一行一个。如果没有\(i\)满足条......
  • 队列
    队列1.基本概念及描述队列也是一种特殊的线性表，队列的插入和删除在表的两端进行，插入的那端称为队尾，删除的那端叫做队首，插入和删除操作分别叫做进队和出队。生活中的排队购票现象就是队列的例子，先到先享受，队列具有“先进先出”（FirstInFirstOut）的特点.2.顺序队列及其实现C语......
  • 队列操作（深入理解FreeRTOS队列之队列实战）
    文章目录一、队列的操作二、学习总结在FreeRTOS中，队列的本质是环形缓冲区。一、队列的操作1、创建队列2、写队列3、读队列详细可看此篇博客：FreeRTOS——队列（基于百问网DshanMCU-F103实现挡球板游戏改造）-CSDN博客基于链表解析队列的使用：代码示例：#include"......
  • 单调栈和单调队列优化DP
    单调栈和单调队列优化DPluoguP1725琪露诺一道比较板的题明显是一个DP，则有\[{dp}_i=\max_{j=i-r}^{i-l}dp_j+a_i\]如果暴力则为\(O(n^2)\)但是发现\(\max_{j=i-r}^{i-l}dp_j\)就是单调队列所解决的问题，所以直接单调队列维护即可#include<bits/stdc++.h>#defineFAS......
  • Linux系统中利用消息队列实现两个进程的通信
    在Linux系统中进程间的通信有很多的方法，这次利用消息队列实现进程的通信进程一的代码实现#include<sys/types.h>#include<sys/ipc.h>#include<stdio.h>#include<sys/msg.h>#include<sys/types.h>#include<sys/ipc.h>#include<string.h>structmsgbuf{ ......
  • PriorityQueue源码解析
    PriorityQueue优先级队列：默认每次取出权值最小的元素，元素的大小评判可以通过元素自身的自然顺序，也可以在构造时传入比较器进行定义顺序规则。用法//不传比较器PriorityQueue<Integer>pq=newPriorityQueue<>();pq.add(3);pq.add(4);pq.add(1);pq.add(2);//输出顺序1......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99