数据结构总结分享01——栈的实现-北京尧图网络

栈的介绍分类顺序存储方式顺序栈 — 用数组实现链式存储方式链式栈 — 用链表实现基本操作压入push弹出pop存取栈顶值peek清空clear判空isEmpty注此处的英文名称与 C 中的 STL 库中的对应操作名有些许不同比如此处的 peek 在 STL 中的 stack 使用 top 来实现的请大家仔细分辨。顺序栈#includeiostreamusingnamespacestd;// 定义泛型顺序栈顺序存储方式用数组来实现templatetypenameTclassAStack{private:T*data;// 指向动态数组的指针intMsize;// 栈的最大容量inttopIndex;// 栈顶指针这里用数组下标表示-1表示空栈public:// 构造函数AStack(intcap100){Msizecap;datanewT[Msize];// 向系统申请一块连续的内存存放数据topIndex-1;// 初始化栈顶指针-1表示目前没有数据}// 析构函数~AStack(){delete[]data;}// 入栈voidpush(T value){if(topIndexMsize-1){cout栈满无法入栈\n;return;// ** 为什么不需要返回值呢???}data[topIndex]value;// 栈顶指针先加1然后存入数据}// 出栈Tpop(){if(topIndex-1)// 用 isEmpty() 来判断也是可以的{cout栈空无法出栈\n;return;}returndata[topIndex--];// 直接将栈顶指针下移即可数据会被覆盖逻辑上算是删除了}// 获取栈顶元素Tpeek(){if(topIndex-1){throwout_of_range(栈为空);// 抛出异常???}returndata[topIndex];}// 判断栈是否为空boolisEmpty(){returntopIndex-1;}// 清空栈voidclear(){topIndex-1;// 顺序栈清空极其简单重置指针即可后续入栈会覆盖旧数据}};intmain(){// 测试泛型顺序栈 (指定存放 int 型)cout 测试顺序栈 (存放整数) endl;AStackintsStack(5);// 实例化一个容量为5的整数栈sStack.push(10);sStack.push(20);sStack.push(30);cout顺序栈栈顶: sStack.peek()endl;// 输出 30sStack.pop();cout出栈一次后栈顶: sStack.peek()endl;// 输出 20sStack.clear();cout清空后是否为空: (sStack.isEmpty()?是:否)endl;return0;}链式栈#includeiostream#includestringusingnamespacestd;// 定义泛型链式栈链式存储方式用链表来实现templatetypenameTclassLStack{private:// 定义一个内部的节点结构体structNode{T data;// 数据域Node*next;// 指针域};Node*topPtr;// 栈顶指针永远指向链表的第一个节点即头节点public:// 构造函数LStack(){topPtrnullptr;// 初始化时栈为空头指针置空}// 析构函数~LStack(){clear();// 直接复用清空函数把所有节点释放掉}// 入栈 (相当于链表的头插法)voidpush(T value){Node*newNodenewNode;// 动态创建一个新节点也可以 Node *newNode (Node*)malloc(sizeof(Node*)); 但是 C 推荐用 new 来分配内存newNode-datavalue;newNode-nexttopPtr;// 新节点的 next 指向原来的栈顶topPtrnewNode;// 更新栈顶指针为新节点}// 出栈 (相当于链表的头删法)Tpop(){if(topPtrnullptr)// 用 isEmpty() 来判断也是可以的{cout栈空无法出栈\n;returnT();// 返回默认值}Node*temptopPtr;// 暂存当前栈顶节点topPtrtopPtr-next;// 栈顶指针下移到第二个节点T valuetemp-data;// 保存要返回的值deletetemp;// 释放原栈顶节点的内存空间防止内存泄漏returnvalue;/* 也可以: T value topPtr-data; // 先保存栈顶数据 Node *temp topPtr-next; // 暂存当前栈顶节点的下一个节点 delete topPtr; // 释放原栈顶节点的内存空间防止内存泄漏 topPtr temp; // 更新栈顶指针为下一个节点 */}// 获取栈顶元素Tpeek(){if(topPtrnullptr){throwout_of_range(栈为空);}returntopPtr-data;}// 判断是否为空boolisEmpty(){returntopPtrnullptr;}// 清空栈循环出栈直到为空voidclear(){while(!isEmpty()){// 其实就是不带返回返回功能的 pop()Node*temptopPtr;// 暂存当前栈顶节点topPtrtopPtr-next;// 栈顶指针下移到第二个节点deletetemp;}}};intmain(){// 测试泛型链式栈 (指定存放 string 型)cout\n 测试链式栈 (存放字符串) endl;LStackstringlStack;// 实例化一个字符串栈lStack.push(Hello);lStack.push(C);lStack.push(OOP);cout链式栈栈顶: lStack.peek()endl;// 输出 OOPlStack.pop();cout出栈一次后栈顶: lStack.peek()endl;// 输出 Creturn0;}STL 实现介绍STL 专门为栈这个数据结构设计了一个标准容器std::stack它完美覆盖了顺序栈和链式栈所必需的功能因此我们不需要弄清楚这个容器是如何底层实现的只需掌握其函数就能使用栈的核心功能了使用前情提要头文件#include stack操作特点先进后出LIFO只能操作栈顶操作创建用 T 代表元素类型stackT s;默认构造空栈stackT s2(s1);拷贝构造stackT s3 s1;赋值构造注拷贝构造与赋值构造本质无区别因此s2 s1是成立的stackT vectorT s; / stackT listT s;指定底层容器构造struct Node {T val;}; stackNode s;自定义结构体栈入栈s.push(val);先创建 T 类型的对象 val再放入栈中s.emplace(参数)直接在栈中构造所填入的参数使用建议一般情况用push即可但遇到复杂对象比如结构体、自定义类等使用emplace会更高效出栈s.pop();弹出栈顶元素注此函数返回值为void且不能对空栈调用此函数访问栈顶s.top();: 返回栈顶元素但不会把栈顶元素弹出注不能对空栈调用此函数判空s.empty();返回bool类型值来判断栈是否为空获取元素个数s.size();返回size_t类型值表明当前栈中元素个数在实际运算中也是可以强制类型转换成int的交换s1.swap(s2); / s2.swap(s1);将 s1 与 s2 两个栈进行交换清空清空操作std::stack中没有对应函数但可以按如下操作来实现while(!s.empty()) s.pop();循环出栈s stackT();赋值出栈注std::stack不支持[]等操作来进行随机访问也无迭代器故无法遍历想要获取栈顶元素并弹出需要先用top来获取再用pop来弹出

数据结构总结分享01——栈的实现

相关推荐

Navicat密码解密工具：3分钟找回丢失数据库密码的完整指南

Windows下PCL快速配置：5分钟搞定Debug与Release双模式

UE5 Trace分析框架：从核心原理到实战性能优化指南

更多资讯

防抖节流不是万能膏药：原理、陷阱与正确用法

Windows PyTorch训练ResNet-50 ImageNet-1K避坑

工业机器人视觉抓取0.1mm精度：从YOLOv11到完整标定链路

嵌入式工程师的柯南式排查方法论：从玄学问题到可复现工程问题

Torque3D开发规范：C++注册、脚本作用域与资源路径硬约束

基于 Mosquitto 与 paho-mqtt 的 MQTT 客户端封装

今日更新

MATLAB+Yalmip+CPLEX实战：综合能源系统优化调度全流程解析

I3C比I2C快10倍？RK3576实战：速率、DTS配置与混合总线避坑指南

字符串转对象：JSON.parse、new Function与URLSearchParams

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？