栈和队列-介绍与实现（超级详解-C语言）

栈

栈的介绍

        栈的概念

        栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

        压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

        出栈：栈的删除操作叫做出栈。出数据也在栈顶。

        栈的结构

栈的实现

        初始化栈 StackInit

        需要用结构体创建一个栈，这个结构体需要包括栈的基本内容（栈，栈顶，栈的容量）。

typedef int STDataType;//栈中存储的元素类型（这里用整型举例）

typedef struct Stack
{
	STDataType* a;//栈
	int top;//栈顶
	int capacity;//容量，方便增容
}Stack;

        然后需要一个初始化函数，对刚创建的栈进行初始化。 

//初始化栈
void StackInit(Stack* pst)
{
	// 使用断言检查输入指针是否有效，确保不为空
    assert(pst);

    // 动态分配内存，为栈分配空间，初始可存储4个STDataType类型的元素
    pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);

    // 初始化栈顶指针为0，表示栈当前为空，没有元素
    pst->top = 0;

    // 设置栈的初始容量为4，即栈目前最多可以容纳4个元素
    pst->capacity = 4;
}

        销毁栈 StackDestroy

        因为栈的内存空间是动态开辟出来的，当我们使用完后必须释放其内存空间，避免内存泄漏。

void StackDestroy(Stack* pst) 
{
    // 断言检查传入的栈结构体指针是否有效，确保它是指向一个已初始化的栈
    assert(pst != NULL);

    // 使用 free 函数释放栈中存储元素的数组所占用的内存防止内存泄漏
    free(pst->a);

    // 将栈的元素数组指针置为 NULL，这是一种安全措施，避免栈被释放后仍被当作有效指针使用
    pst->a = NULL;

    // 将栈顶指针 top 置为 0，这表示栈内已无任何元素，栈处于空状态
    pst->top = 0;

    // 将栈的容量 capacity 置为 0，代表栈当前没有存储能力，明确表示栈已经被销毁
    pst->capacity = 0;
}

        入栈 StackPush

        进行入栈操作前，我们需要检测栈的当前状态，若已满，则需要先对其进行增容，然后才能进行入栈操作。

void StackPush(Stack* pst, STDataType x) 
{

    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 判断栈是否已满（栈顶索引等于栈的当前容量）
    if (pst->top == pst->capacity) 
    {
        // 如果栈满，则尝试重新分配内存，使栈容量翻倍
        STDataType* tmp =(STDataType*)realloc(pst->a,sizeof(STDataType)*pst->capacity * 2);

        // 检查重新分配内存是否成功
        if (tmp == NULL) 
        {
            // 若失败，输出错误信息，并调用 exit 函数结束程序运行
            printf("realloc fail\n");
            exit(-1);
        }

        // 若重新分配内存成功，更新栈的元素数组指针和容量
        pst->a = tmp;
        pst->capacity *= 2;
    }

    // 将新元素存入栈顶位置
    pst->a[pst->top] = x;

    // 更新栈顶索引，表示栈顶已移动至新的元素处
    pst->top++;
}

        出栈 StackPop

        出栈操作比较简单，即让栈顶的位置向下移动一位即可。但需检测栈是否为空，若为空，则不能进行出栈操作。

void StackPop(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 断言检查栈是否为空，若为空则无法弹出元素
    assert(!StackEmpty(pst));

    // 栈顶指针向下移一位，相当于删除栈顶元素
    // 注意：这里假设移除元素后不需要返回其值，且不涉及内存释放
    pst->top--;

    // 注：在实际应用中，若栈顶元素包含动态分配的内存，此处还需要额外处理释放该内存
}

        获取栈顶元素 StackTop

        获取栈顶元素，即获取栈的最上方的元素。若栈为空，则不能获取。

STDataType StackTop(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 断言检查栈是否为空，若为空则无法获取栈顶元素
    assert(!StackEmpty(pst));

    // 返回栈顶元素的值，栈顶元素的位置是栈顶指针减1
    // 注意：此处只读取栈顶元素而不改变栈的状态
    return pst->a[pst->top - 1];
}

        检查栈是否为空 StackEmpty

        检测栈是否为空，即判断栈顶的位置是否是0即可。若栈顶是0，则栈为空。

bool StackEmpty(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 根据栈顶指针 top 的值判断栈是否为空
    // 当栈顶指针为 0 时，表示栈中没有元素，即栈为空
    return pst->top == 0;
}

        获取栈中有效元素个数 StackSize

        因为top记录的是栈顶，使用top的值便代表栈中有效元素的个数。

int StackSize(Stack* pst) 
{
    // 断言检查栈结构体指针是否有效
    assert(pst);

    // 栈顶指针 top 的值直接表示栈中有效元素的个数
    // 因为每当有元素入栈时，top加1；元素出栈时，top减1
    // 所以，top的值就反映了当前栈内实际存储了多少个元素
    return pst->top;
}

队列

队列的介绍

        队列的概念

        队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。队列遵守先进先出 FIFO（First In First Out）的原则。

        入队列：队列的插入操作叫做入队列，进行插入操作的一端称为队尾。

        出队列：队列的删除操作叫做出队列，进行删除操作的一端称为队头。

        队列的结构

​

        队列的应用

        队列在生活中的运用非常广泛。很大一部分医院、营业厅以及餐厅等场所都存在队列的应用。
        例如，医院的采血环节的流程就运用了队列。在医院，如果我们要去抽血，我们首先要在旁边的抽号机抽取自己的编号，当某一个抽血窗口叫到你时，你便可以去抽血了。
        在这个过程中，当你在抽号机抽取到某一个编号，那么这个编号这时就从队尾入队列，当某一窗口抽血结束后，会在该队列中拿走一个编号并叫该编号的人到这个窗口接受抽血，那么这时这个编号就从队头出队列。

​

队列的实现

        首先我们需要创建一个结点类型，类型包含了该结点的数据和指向下一结点的指针。

typedef int QDataType;

typedef struct QListNode
{
    // 指向下一个节点的指针
    struct QListNode* next;
    
    // 节点所存储的数据
    QDataType data;
} QListNode;

        队列与普通链表又有所不同，普通链表只需要知道链表的头指针，而队列的信息包括了队头和队尾，所以我们需要再创建一个结构体用于存放队列的队头和队尾。 

typedef struct Queue
{
    // 队列头指针
    // 指向队列的第一个节点，当队列为空时，head 和 tail 都指向 NULL
    QListNode* head;

    // 队列尾指针
    // 指向队列的最后一个节点，每次有新元素入队时，都会更新 tail 指针
    QListNode* tail;
} Queue;

        初始化队列 QueueInit

         然后需要一个初始化函数，对刚创建的队列进行初始化。

void QueueInit(Queue* pq) 
{
    // 断言检查传入的队列结构体指针是否有效
    assert(pq);

    // 将队列的头指针 head 初始化为 NULL，表示队列当前为空，无元素
    pq->head = NULL;

    // 将队列的尾指针 tail 也初始化为 NULL，与 head 一致，表示队列为空
    // 这样设计的原因是，在队列为空时，头尾指针均指向 NULL；而在有元素入队时，tail 指针将指向最后一个元素
    pq->tail = NULL;
}

        销毁队列 QueueDestroy

        队列中的每一个结点所占用的内存空间都是动态开辟的，当我们使用完队列后需要及时释放队列中的每一个结点。

void QueueDestroy(Queue* pq) 
{
    // 断言检查传入的队列结构体指针是否有效
    assert(pq);

    // 创建一个临时指针 cur，初始化为队列的头节点
    QListNode* cur = pq->head;

    // 循环遍历队列中的每一个节点
    while (cur) 
    {
        // 将 cur 的下一个节点赋值给临时指针 next，保存下一个节点的地址
        QListNode* next = cur->next;

        // 释放当前节点 cur 的内存
        free(cur);

        // 移动 cur 指针至下一个节点
        cur = next;
    }

    // 清空队列的头指针和尾指针，将它们都设置为 NULL
    pq->head = NULL;
    pq->tail = NULL;
}

        队尾入队列 QueuePush

        入队列，即申请一个新结点并将其链接到队尾，然后改变队尾的指针指向即可。需要注意的是：若队列中原本无数据，那么我们只需让队头和队尾均指向这个新申请的结点即可。

void QueuePush(Queue* pq, QDataType x) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 分配内存创建一个新的节点
    QListNode* newnode = (QListNode*)malloc(sizeof(QListNode));
   
    // 检查内存分配是否成功
    if (newnode == NULL) 
    {
        // 若内存分配失败，输出错误信息并退出程序
        printf("malloc fail\n");
        exit(-1);
    }

    // 将新节点的数据域设置为要插入的元素值 x
    newnode->data = x;

    // 新节点的下一节点指针初始化为 NULL
    newnode->next = NULL;

    // 判断队列是否为空
    if (pq->head == NULL) 
    {
        // 若队列为空，则新节点既是头节点也是尾节点
        pq->head = pq->tail = newnode;
    } 
    else 
    {
        // 若队列非空，将现有尾节点的下一节点指向新节点
        pq->tail->next = newnode;
        
        // 更新队列尾指针，使之指向新插入的节点
        pq->tail = newnode;
    }
}

        队头出队列 QueuePop

        出队列，即释放队头指针指向的结点并改变队头指针的指向即可。若队列中只有一个结点，那么直接将该结点释放，然后将队头和队尾置空即可。

void QueuePop(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则不能进行出队操作
    assert(!QueueEmpty(pq));

    // 判断队列中剩余元素数量
    if (pq->head->next == NULL) 
    {
        // 如果队列只剩一个元素，则释放该元素，并将头尾指针都设为 NULL
        free(pq->head);
        pq->head = NULL;
        pq->tail = NULL;
    } 
    else 
    {
        // 如果队列中还有多个元素，则释放头节点，然后将头指针指向下一个节点
        QListNode* next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

        获取队列头部元素 QueueFront

        获取队列头部元素，即返回队头指针指向的数据即可。

QDataType QueueFront(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则无法获取队头元素
    assert(!QueueEmpty(pq));

    // 返回队列头部节点（即队首元素）的数据域值
    return pq->head->data;
}

        获取队尾尾部元素

        获取队列尾部元素，即返回队尾指针指向的数据即可。

QDataType QueueBack(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 断言检查队列是否为空，若为空则无法获取队尾元素
    assert(!QueueEmpty(pq));

    // 返回队列尾部节点（即队尾元素）的数据域值
    return pq->tail->data;
}

        检查队列是否为空 QueueEmpty

        检测队列是否为空，即判断队头指针指向的内容是否为空。

bool QueueEmpty(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 判断队列是否为空的条件是：头指针（pq->head）是否为 NULL
    // 如果头指针为 NULL，则队列为空，返回 true
    // 否则，队列非空，返回 false
    return pq->head == NULL;
}

        获取队列中有效元素个数 QueueSize

        队列中有效元素个数，即队列中的结点个数。我们只需遍历队列，统计队列中的结点数并返回即可。

int QueueSize(Queue* pq) 
{
    // 断言检查队列结构体指针是否有效
    assert(pq);

    // 初始化计数器 count 为 0
    int count = 0;

    // 创建一个临时指针 cur，初始化为队列的头节点
    QListNode* cur = pq->head;

    // 遍历队列，直到 cur 为空（即遍历完队列）
    while (cur) 
    {
        // 计数器加一，表示找到了一个有效节点
        count++;

        // 将 cur 指针移向下一个节点
        cur = cur->next;
    }

    // 返回计数器 count 的值，即队列中有效元素的个数
    return count;
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Mac中隐私安全性设置-打开任何来源

Mac中隐私安全性设置-打开任何来源

文章目录 **Mac中隐私安全性设置-打开任何来源**一、目的二、打开方式 Mac中隐私安全性设置-打开任何来源 一、目的 从外部下载的软件频繁打不开，需要从隐私安全性中重新选择一下；默认Mac隐藏了任何来源 二、打开方式 打开终端，输入一下命…
阅读更多...
配置BFD

配置BFD

目录 原理概述 实验目的 实验内容 实验拓扑 1.基本配置 2.配置OSPF路由协议 3.配置VRRP协议 4.配置BFD 原理概述 为了减小设备故障对网络业务造成的影响，提高网络的可用性，网络设备需要能够尽快检测到与相邻设备之间的通信故障，以便及…
阅读更多...
详解运算符重载——探索运算符重载的应用

详解运算符重载——探索运算符重载的应用

前言:运算符重载是面向对象的一个重要的知识点。我们都知道内置类型可以进行一般的运算符的运算。但是如果是一个自定义类型， 这些运算符就无法使用了。那么为了解决这个问题， 我们的祖师爷就在c中添加了运算符重载的概念。 本篇主要通过实例的实现来讲述…
阅读更多...
短视频批量采集提取软件|视频下载工具

短视频批量采集提取软件|视频下载工具

短视频批量采集提取软件：高效获取视频资源 一、开发背景 在日常业务中，我们经常需要获取大量的短视频资源，以支持各种需求，但传统的获取方式过于繁琐，一一复制链接下载效率低下。基于此需求，我们开发了一…
阅读更多...
rocketmq-dashboard打包测试报错

rocketmq-dashboard打包测试报错

rocketmq-dashboard运行的时候没问题，但是打包执行测试的时候就是报错 这时候跳过测试就可以成功 报错为 There are test failures. Please refer to D:\CodeEn\rocketmq-dashboard\target\surefire-reports for the individual test results. 你只需要跳过测试就…
阅读更多...
Wpf 使用 Prism 实战开发Day20

Wpf 使用 Prism 实战开发Day20

备忘录功能页面完善以及优化 备忘录功能基本跟前一章节的待办事项差不多一至&#xff0c;就不再做过多的笔述了 一.备忘录功能完整页面源码 MemoView.xaml <UserControl x:Class"MyToDo.Views.MemoView"xmlns"http://schemas.microsoft.com/winfx/2006/xam…
阅读更多...
用html写一个搜索页面

用html写一个搜索页面

<!DOCTYPE html> <html lang"en" > <head><meta charset"UTF-8"><title>搜索框设计</title><link rel"stylesheet" href"./style.css"> </head> <body> <div class"se…
阅读更多...
TypeScript基础入门（一、常用类型）

TypeScript基础入门（一、常用类型）

目录 第一章 前言 1.1 介绍TypeScript 1.2 TypeScript相比Js的优势 1.3 使用TypeScript的准备工作 第二章 TypeScript的数据类型 2.1 TypeScript的常用类型 2.1.1 概述 2.1.2 TS使用JS基本数据类型 2.1.2.1 number 2.1.2.2 string 2.1.3.3 boolean 2.1.2.4 null 2…
阅读更多...
Pytorch DistributedDataParallel（DDP）教程一：快速入门理论篇

Pytorch DistributedDataParallel（DDP）教程一：快速入门理论篇

Pytorch DistributedDataParallel&#xff08;DDP&#xff09;教程一&#xff1a;快速入门理论篇 目录 一、 写在前面二、什么是分布式并行训练1. 并行训练2. 数据并行 三、DDP的基本原理1. DDP的训练过程2. Ring-All-Reduce算法 四、如何搭建一个Pytorch DDP代码框架1. 与DDP有…
阅读更多...
二次元AI绘画生成器免费：教你生成精美图片

二次元AI绘画生成器免费：教你生成精美图片

二次元AI绘画生成器&#xff0c;无疑是现代技术与艺术完美结合的典范。这些工具不仅将复杂的绘画过程简化&#xff0c;更让每一个艺术爱好者的创意得以充分展现。这些生成器能够精准捕捉大家的创意精髓&#xff0c;将其转化为细腻、独特的二次元画作。无论是角色设计、场景描绘…
阅读更多...
OpenHarmony UI动画-box2d

OpenHarmony UI动画-box2d

简介 用于游戏开发&#xff0c;使物体的运动更加真实&#xff0c;让游戏场景看起来更具交互性&#xff0c;比如愤怒的小鸟 效果展示 下载安装 ohpm install ohos/box2dOpenHarmony ohpm环境配置等更多内容&#xff0c;请参考 如何安装OpenHarmony ohpm包 使用说明 import * …
阅读更多...
OCR图片转化为Excel文件功能在哪些平台和设备上能实现？

OCR图片转化为Excel文件功能在哪些平台和设备上能实现？

在现今数字化时代&#xff0c;将图片转化为Excel文件已成为许多工作者和研究者的重要需求。这种转换功能在多个平台和设备上均能实现&#xff0c;为用户提供了极大的便利。 首先&#xff0c;我们来看看在线平台方面。目前&#xff0c;市面上有许多在线工具可以将图片转换为Exc…
阅读更多...
MoJoCo 入门教程（七）XML 参考

MoJoCo 入门教程（七）XML 参考

系列文章目录 前言 表格第二列中的符号含义如下&#xff1a; ! 必填元素&#xff0c;只能出现一次 ? 可选元素&#xff0c;只能出现一次 * 可选元素&#xff0c;可多次出现 R 可选元素&#xff0c;可递归出现多次 一、简介 本章是 MuJoCo 中使用的 MJCF 建模语言的参考手册。…
阅读更多...
【云计算】安全组和网络ACL的区别

【云计算】安全组和网络ACL的区别

安全组和网络ACL的区别 ACL&#xff08;Access Control List&#xff09;和 安全组&#xff08;Security Group&#xff09;是两种不同的网络安全控制机制&#xff0c;通常用于管理云计算平台中的网络访问权限。它们在功能和实现上有一些显著的区别&#xff1a; 辨析 范围不同&…
阅读更多...
如何把网易云ncm转换为mp3格式

如何把网易云ncm转换为mp3格式

大家在网易云下载音乐的时候会发现下载的音乐格式是ncm&#xff0c;这个格式只能在网易云播放器才能播放&#xff0c;无法在别的播放器上播放。今天教大家把ncm转换为更加通用的格式 打开智游剪辑&#xff08;官网: zyjj.cc&#xff09;&#xff0c;搜索ncm转mp3 这里就只需要上…
阅读更多...
DC电源模块的未来发展方向和创新应用领域

DC电源模块的未来发展方向和创新应用领域

BOSHIDA DC电源模块的未来发展方向和创新应用领域 随着科技的快速发展&#xff0c;直流&#xff08;DC&#xff09;电源模块的应用领域也在不断扩大。从传统的电子产品到新兴的清洁能源领域&#xff0c;DC电源模块正发挥着越来越重要的作用。未来&#xff0c;DC电源模块将继续…
阅读更多...
windows docker desktop==spark环境搭建

windows docker desktop==spark环境搭建

编写文件docker-compose.yml version: 3services:spark-master:image: bde2020/spark-master:3.1.1-hadoop3.2container_name: spark-masterports:- "8080:8080"- "7077:7077"- "2220:22"volumes:- F:\spark-data\m1:/dataenvironment:- INIT_D…
阅读更多...
android studio gradle 下载不下来的问题

android studio gradle 下载不下来的问题

有时候由于网络问题&#xff0c;会发现 android-studio 或 idea 下载不懂 gradle&#xff0c;可以修改 gradle-wrapper.properties 配置文件中的 distributionUrl 选项来解决这个问题。 distributionUrlhttps\://mirrors.cloud.tencent.com/gradle/gradle-5.1.1-all.zip 这个选…
阅读更多...
【七 （2）FineBI FCP模拟试卷-平台新增用户留存分析】

【七 （2）FineBI FCP模拟试卷-平台新增用户留存分析】

目录 文章导航一、字段解释1、用户平台登录信息表格2、用户平台激活信息表格 二、需求三、操作步骤1、建立用户平台登录信息表格和用户平台激活信息表格的关联关系2、将用户平台激活信息表格的激活日期添加到用户平台登录信息表格3、新增公式列&#xff0c;计算激活时间和登录时…
阅读更多...
【ACM列表推荐会议 | EI稳定检索】2024年第四届人工智能、自动化与高性能计算国际会议（AIAHPC 2024）

【ACM列表推荐会议 | EI稳定检索】2024年第四届人工智能、自动化与高性能计算国际会议（AIAHPC 2024）

2024年第四届人工智能、自动化与高性能计算国际会议&#xff08;AIAHPC 2024&#xff09; 2024 4th International Conference on Artificial Intelligence, Automation and High Performance Computing 2024第四届人工智能、自动化与高性能计算国际会议(AIAHPC 2024)将于20…
阅读更多...
最新文章

Copyright @ 2022~2023