当前位置: 首页 > news >正文

数据结构【链栈】

基于 C++ 实现链表栈:原理、代码与应用

一、引言

栈就是一个容器,可以当场一个盒子,只能一个一个拿,一个一个放,而且是从上面放入。
有序顺序栈操作比较容易【会了链栈之后顺序栈自然明白】,所以我们这里只对链表进行详细解释。

二、栈的链表实现原理

链表是一种动态数据结构,由一系列节点组成,每个节点包含数据和指向下一个节点的指针。利用链表实现栈,就是将链表的头部作为栈顶,通过对链表头部的操作来模拟栈的入栈和出栈操作。这种实现方式的优点在于不需要预先分配固定大小的内存空间,能够根据实际需求动态调整栈的大小。

三、代码实现

1. 栈节点的定义

#include<iostream>
using namespace std;typedef struct stacknode {int date; // 存放数据struct stacknode* next; // 指针域
} lststack;lststack *S;

这里定义了一个名为 stacknode 的结构体,并重命名为 lststack。每个节点包含一个整数 date 用于存储数据,以及一个指向下一个节点的指针 next。同时,声明了一个全局的栈顶指针 S

2. 栈的初始化

lststack *initstack()
{ // 初始化lststack* S = NULL;return S;
}

initstack 函数用于初始化栈,将栈顶指针置为 NULL,表示栈为空。

3. 判断栈是否为空

int empty(lststack* S)
{if (S == NULL) return 1;else return 0;
}

empty 函数用于判断栈是否为空。如果栈顶指针为 NULL,则返回 1,表示栈为空;否则返回 0。

4. 入栈操作

lststack *push(lststack* s, int x)
{lststack* p = (lststack*)malloc(sizeof(lststack));p->date = x;p->next = s;s = p;return s;
}

push 函数用于将元素 x 压入栈中。具体步骤如下:

  • 使用 malloc 函数为新节点分配内存空间。
  • 将元素 x 赋值给新节点的 date 成员。
  • 让新节点的 next 指针指向原来的栈顶节点。
  • 更新栈顶指针为新节点。
  • 返回更新后的栈顶指针。

5. 出栈操作

lststack* pop(lststack* s, int *x)
{lststack* p = (lststack*)malloc(sizeof(lststack));if (empty(s)) {cout << "栈空了" << endl;return NULL;}*x = s->date;p = s;s = s->next;free(p);return s;
}

pop 函数用于将栈顶元素弹出栈。具体步骤如下:

  • 首先检查栈是否为空,如果为空则输出提示信息并返回 NULL
  • 将栈顶元素的值赋给指针 x 所指向的变量。
  • 用临时指针 p 指向栈顶节点。
  • 更新栈顶指针为原栈顶节点的下一个节点。
  • 释放原栈顶节点的内存空间。
  • 返回更新后的栈顶指针。

6. 查看栈顶元素

int top(lststack* s, int* x)
{lststack* p = (lststack*)malloc(sizeof(lststack));if (empty(s)) {cout << "栈空了" << endl;return 0;}*x = s->date;return 1;
}

top 函数用于查看栈顶元素的值。如果栈为空,则输出提示信息并返回 0;否则将栈顶元素的值赋给指针 x 所指向的变量,并返回 1。

7. 打印栈元素

void print(lststack* s)
{lststack* p = (lststack*)malloc(sizeof(lststack));p = s;if (empty(s)) {cout << "栈空了" << endl;return;}while (p){cout << p->date;p = p->next;}return;
}

print 函数用于遍历栈并打印每个元素的值。如果栈为空,则输出提示信息;否则从栈顶开始依次打印每个元素的值。

8. 主函数测试

在这里插入图片描述
结果如下:在这里插入图片描述

在主函数中,首先调用 initstack 函数初始化栈,然后使用 push 函数将元素 1、2、3、5 依次压入栈中,接着使用 print 函数打印栈中的元素,再使用 pop 函数弹出一个元素并打印弹出的元素的值,最后再次使用 print 函数打印栈中的元素。
`

五、总结

通过本文的介绍,我们学习了如何使用 C++ 语言,利用链表实现一个栈。这种实现方式具有动态调整大小的优点,适用于需要灵活管理内存的场景。同时,我们也对代码中存在的问题进行了分析,并给出了优化建议。在实际应用中,我们可以根据具体需求对代码进行进一步的扩展和优化。

相关文章:

数据结构【链栈】

基于 C 实现链表栈&#xff1a;原理、代码与应用 一、引言 栈就是一个容器&#xff0c;可以当场一个盒子&#xff0c;只能一个一个拿&#xff0c;一个一个放&#xff0c;而且是从上面放入。 有序顺序栈操作比较容易【会了链栈之后顺序栈自然明白】&#xff0c;所以我们这里只…...

软件测试02----用例设计方法

今天目标 1.能对穷举场景设计测试点 2.能对限定边界规则设计测试点 3.能对多条件依赖关系进行设计测试点 4.能对项目业务进行设计测试点 一、解决穷举场景 重点&#xff1a;使用等价类划分法 1.1等价类划分法 重点&#xff1a;有效等价和单个无效等价各取1个即可。 步骤&#…...

编程AI深度实战:给vim装上AI

系列文章&#xff1a; 编程AI深度实战&#xff1a;私有模型deep seek r1&#xff0c;必会ollama-CSDN博客 编程AI深度实战&#xff1a;自己的AI&#xff0c;必会LangChain-CSDN博客 编程AI深度实战&#xff1a;给vim装上AI-CSDN博客 编程AI深度实战&#xff1a;火的编程AI&…...

《DeepSeek R1:大模型最简安装秘籍》

DeepSeek R1&#xff1a;AI 大模型界的新起之秀 在人工智能的璀璨星空中&#xff0c;大模型如繁星般闪耀&#xff0c;而 DeepSeek R1 无疑是其中一颗冉冉升起的新星&#xff0c;自问世以来便吸引了全球的目光&#xff0c;在人工智能领域占据了重要的一席之地。 从性能表现上看…...

物业管理平台系统为社区管理带来数字化转型与服务创新新机遇

内容概要 物业管理平台系统是数字化转型的利器&#xff0c;为社区管理带来了许多新机遇。想象一下&#xff0c;传统社区物业管理中繁琐的流程和低效的沟通如何被这种智能系统所替代。通过集成在线收费功能&#xff0c;我们不仅提高了费用收取的准确性&#xff0c;还减少了业主…...

红黑树的封装

一、封装思路 在 STL 中 map set 的底层就是封装了一棵红黑树。 其中连接红黑树和容器的是迭代器&#xff0c;map set 暴露出的接口都不是自己写的&#xff0c;而是红黑树写的&#xff0c;外部接口封装红黑树接口。 所以写出红黑树为 map set 写的接口&#xff0c;再在上层的…...

25.2.3 【洛谷】作为栈的复习不错(学习记录)

今天学习的东西不算多&#xff0c;放了一个星期假&#xff0c;感觉不少东西都没那么清楚&#xff0c;得复习一下才行。今天搞个栈题写&#xff0c;把栈复习一下&#xff0c;明天进入正轨&#xff0c;边复习边学习新东西&#xff0c;应该会有二叉树的学习等等... 【洛谷】P1449 …...

MFC程序设计(七)运行时类信息机制

运行时类信息机制的作用 我们在创建对象时&#xff0c;自己是清楚对象属于哪个类&#xff0c;但是计算机却不清楚。而MFC运行时类信息机制就是解决这个问题而存在的 运行时类信息机制的使用 我们在创建一个类时&#xff0c;只有满足以上三个条件&#xff0c;该类才能支持运行时…...

fflush的概念和使用案例

fflush() 是C语言标准库中用于控制输入/输出缓冲区的函数&#xff0c;其主要功能是强制刷新缓冲区&#xff0c;确保数据及时写入目标设备&#xff08;如屏幕、文件&#xff09;。以下是其概念和典型使用场景&#xff1a; 概念 功能&#xff1a; 刷新指定流的缓冲区。对于输出流…...

嵌入式知识点总结 操作系统 专题提升(四)-上下文

针对于嵌入式软件杂乱的知识点总结起来&#xff0c;提供给读者学习复习对下述内容的强化。 目录 1.上下文有哪些?怎么理解? 2.为什么会有上下文这种概念? 3.什么情况下进行用户态到内核态的切换? 4.中断上下文代码中有哪些注意事项&#xff1f; 5.请问线程需要保存哪些…...

React 封装高阶组件 做路由权限控制

React 高阶组件是什么 官方解释∶ 高阶组件&#xff08;HOC&#xff09;是 React 中用于复用组件逻辑的一种高级技巧。HOC 自身不是 React API 的一部分&#xff0c;它是一种基于 React 的组合特性而形成的设计模式。 高阶组件&#xff08;HOC&#xff09;就是一个函数&…...

【实践案例】基于大语言模型的海龟汤游戏

文章目录 项目背景提示词构建海龟汤主持人真相判断专家 具体实现流程文心一言大语言模型“海龟汤”插件参考 项目背景 “海龟汤”作为一种聚会类桌游&#xff0c;又称情境推理游戏&#xff0c;是一种猜测情境还原事件真相的智力游戏。其玩法是由出题者提出一个难以理解的事件&…...

NeetCode刷题第20天(2025.2.1)

文章目录 106 Best Time to Buy and Sell Stock with Cooldown 使用 Cooldown 买卖股票的最佳时间107 Coin Change II 换币 II108 Target Sum 目标总和109 Interleaving String 交错字符串110 Edit Distance 编辑距离111 Maximum Subarray 最大子数组112 Jump Game 跳跃游戏113…...

DeepSeek:人工智能领域的革新者与未来展望

在当今这个数据驱动的时代&#xff0c;人工智能&#xff08;AI&#xff09;正以前所未有的速度发展&#xff0c;而DeepSeek作为这一领域的先锋&#xff0c;正引领着AI技术的创新与突破。作为一家致力于推动人工智能技术创新与应用的前沿企业&#xff0c;DeepSeek不仅在多语言编…...

Spring Bean 容器

技术成长&#xff0c;是对场景设计细节不断的雕刻&#xff01; 你觉得自己的技术什么时候得到了快速的提高&#xff0c;是CRUD写的多了以后吗&#xff1f;想都不要想&#xff0c;绝对不可能&#xff01;CRUD写的再多也只是能满足你作为一个搬砖工具人&#xff0c;敲击少逻辑流…...

Flask代码审计实战

文章目录 Flask代码审计SQL注入命令/代码执行反序列化文件操作XXESSRFXSS其他 审计实战后记reference Flask代码审计 SQL注入 1、正确的使用直白一点就是&#xff1a;使用”逗号”&#xff0c;而不是”百分号” stmt "SELECT * FROM table WHERE id?" connectio…...

springboot启动配置文件-bootstrap.yml常用基本配置

在Spring Boot应用程序中&#xff0c;bootstrap.yml文件通常用于配置应用程序的启动阶段。在这个文件中&#xff0c;你可以配置一些在应用程序启动之前需要加载的属性&#xff0c;例如外部配置源、加密属性等。以下是一些常用的基本配置项&#xff1a; 1. 外部配置源 1.1 配置…...

2月3日星期一今日早报简报微语报早读

2月3日星期一&#xff0c;农历正月初六&#xff0c;早报#微语早读。 1、多个景区发布公告&#xff1a;售票数量已达上限&#xff0c;请游客合理安排行程&#xff1b; 2、2025春节档总票房破70亿&#xff0c;《哪吒之魔童闹海》破31亿&#xff1b; 3、美宣布对中国商品加征10…...

如何确认Linux嵌入式系统的触摸屏对应的是哪个设备文件(/dev/input/event1)?如何查看系统中所有的输入设备?输入设备的设备文件有什么特点?

Linux嵌入式系统的输入设备的设备文件有什么特点&#xff1f; 在 Linux 中&#xff0c;所有的输入设备&#xff08;如键盘、鼠标、触摸屏等&#xff09;都会被内核识别为 输入事件设备&#xff0c;并在 /dev/input/ 目录下创建相应的 设备文件&#xff0c;通常是&#xff1a; …...

FFmpeg:多媒体处理的瑞士军刀

FFmpeg&#xff1a;多媒体处理的瑞士军刀 前言 FFmpeg 是一个功能强大且跨平台的开源多媒体框架&#xff0c;广泛应用于音视频处理领域。 它由多个库和工具组成&#xff0c;能够处理各种音视频格式&#xff0c;涵盖编码、解码、转码、流处理等多种操作。 无论是专业视频编辑…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...