数据结构——栈(C++实现)

数据结构——栈

  • 什么是栈
  • 栈的实现
    • 顺序栈的实现
    • 链栈的实现

今天我们来看一个新的数据结构——

什么是栈

栈是一种基础且重要的数据结构,它在计算机科学和编程中扮演着核心角色。栈的名称源于现实生活中的概念,如一叠书或一摞盘子,新添加的物品总是放在顶部,而取出物品时也总是从顶部开始。这种后进先出(Last In, First Out, LIFO)的特性决定了栈的行为。

以下是栈的核心特征和操作:

1. 结构与访问限制:
栈是一个线性数据结构,其中元素按照一定的顺序排列。然而,不同于数组或链表,栈只允许在一端(通常称为栈顶)进行数据的插入(也称为压入,push)和删除(也称为弹出,pop)操作。另一端(栈底)是固定的,不参与数据的直接增删。这意味着栈的元素访问受到严格的限制,用户只能与栈顶元素进行交互。
2. 后进先出(LIFO)原则:
栈遵循后进先出原则。这意味着最近添加到栈中的元素最先被移除。换句话说,最后压入栈的元素是离栈顶最近的,因此在弹出操作时会第一个被访问和移除。相反,最早压入栈的元素(即那些距离栈顶最远的元素)只有在所有后来压入的元素都被弹出后才能被访问。
3. 基本操作:

  • Push(压入): 将一个元素添加到栈顶。
  • Pop(弹出): 移除并返回栈顶元素。如果栈为空,尝试弹出操作通常会导致错误或异常。
  • Peek(查看)/Top: 返回栈顶元素的值,但不改变栈的状态(不移除元素)。
  • IsEmpty(是否为空)/Size(大小): 检查栈是否为空或获取栈中元素的数量。
    4. 应用场景:
    栈因其简单且高效的特性在许多编程任务中得到广泛应用,包括但不限于:
  • 函数调用栈: 在编程语言实现中,每当一个函数被调用时,其局部变量、返回地址等信息会被压入一个系统维护的栈中。函数执行完毕后,通过弹出操作清除这些信息,返回到调用函数的位置继续执行。
  • 表达式求值和符号解析: 在计算逆波兰表示法(RPN)表达式或处理编程语言的括号匹配时,栈用于临时存储操作数和运算符,确保正确的计算顺序。
  • 深度优先搜索(DFS)和回溯算法: 在遍历树形结构或解决涉及多种可能路径的问题时,栈用于存储待访问节点或中间状态,以便回溯到前一个状态。
  • 浏览器历史记录: 用户浏览网页时,后访问的页面压入历史记录栈,前进和后退操作对应于栈的弹出和压入。

总的来说,栈是一种高效、受限的线性数据结构,通过其特有的后进先出性质,为处理需要保持数据顺序、尤其是需要频繁撤销最近操作的场景提供了简洁而强大的工具。

通俗理解,栈的确可以看作是一种操作受限的线性表。线性表是一类数据结构,其中的元素按一定顺序排列,每个元素都有一个唯一的前驱和后继(除了首尾元素外)。栈继承了线性表的这一基本特征,即元素间的线性关系。但是,与常规线性表相比,栈对元素的插入和删除操作施加了严格限制:

操作限制:
常规线性表通常允许在任意位置插入和删除元素,而栈只允许在表的一端(栈顶)进行这两种操作。这意味着你不能随意地在栈的中间或底部插入或删除元素,只能对栈顶进行操作。
行为特点:
由于这种操作限制,栈体现出后进先出(LIFO)的特性。想象一下一个真实的堆栈,比如一叠书或者一叠盘子。当你把新的物品(书或盘子)放在堆栈顶部时,它们就成了最新的“后进”元素。当你需要取走一个物品时,你只能从最上面拿走,所以取出的是最晚放入的那个“先进”元素。这就是所谓的“后进先出”。这种特性使得栈非常适合处理那些需要按照“最后来,最先走”顺序处理数据的场景。
通俗比喻:
可以把栈比作一个只能从上面放东西和取东西的箱子。往箱子里放物品(压入)时,新物品总是在最上面;取出物品(弹出)时,也只能拿走最上面那个。这样,箱子里的物品就像排队一样,后放入的总是在前面,先放入的在后面,想要取走一个物品,必须先把所有后来放入的物品都拿出来。

总结来说,虽然栈具备线性表的基本结构特点,但它通过严格限制操作位置,使其成为一种具有特定行为(后进先出)的特殊线性表。这种操作上的约束赋予了栈独特的应用场景和价值。

栈的实现

我们可以用数组来模拟栈的行为:

template<class T>
class MyStack
{
public:MyStack() //无参构造:_capacity(10),_size(0){//开辟空间_data = new T(_capacity); //开辟这么大的空间}MyStack(const size_t& capacity) //带参构造:_capacity(capacity),_size(0){//开辟空间_data = new T(_capacity);}	private://动态数组T* _data;//最大容量size_t _capacity;//当前数量size_t _size;
};

我们这里开了一个动态数组:
在这里插入图片描述
我们一般想象的栈是竖着的,我们可以把这个数组倒一头:
在这里插入图片描述
然后我们可以用一个_size的下标,指向我们0号位置(这里的下标有妙用):

在这里插入图片描述
如果有元素入栈,我们先入栈:
在这里插入图片描述

_size加一:
在这里插入图片描述
模拟这样的行为,我们发现_size总是指向栈顶位置的下一个的位置,但是又因为数组的下标又是从0开始,_size也可以表示栈中有多少个元素。

我们可以用这样的特性,来实现push和top和pop:

    //pushvoid push(const T& data){assert(_size < _capacity);_data[_size++] = data; //在_data[_size]放入之后,_size+1,指向下一个位置}//popconst T& pop(){assert(_size != 0);return _data[--_size]; //因为_size指向栈顶元素的下一个位置,首先先减一取到栈顶}//topconst T& top(){assert(_size != 0);return _data[_size - 1];}

既然这里的_size是指向栈顶元素的下一个位置,我们也可以让_size指向栈顶元素,这样_size的初始位置就得从-1开始
在这里插入图片描述这样元素入栈,首先要加一(防止下标越界)
在这里插入图片描述然后再放入元素:
在这里插入图片描述

大家可以根据这个写一下这个版本的栈,这里不再赘述。

顺序栈的实现

下面是完整顺序栈的实现:

#pragma once
#include <cassert>
#include <iostream>template <class T>
class MyStack
{
public:// 无参构造函数,使用默认容量创建栈MyStack(): _capacity(10), _size(0){// 开辟空间,创建动态数组,初始容量为 _capacity_data = new T[_capacity];}// 带参构造函数,根据指定容量创建栈MyStack(const size_t& capacity): _capacity(capacity), _size(0){// 开辟空间,创建动态数组,容量为传入的 _capacity_data = new T[_capacity];}// 压栈操作,将新元素添加到栈顶void push(const T& data){// 断言检查当前栈是否已满,若已满则抛出断言失败assert(_size < _capacity);// 将新元素存入动态数组的当前位置,并递增栈大小_data[_size++] = data;}// 出栈操作,删除栈顶元素并返回其值const T& pop(){// 断言检查当前栈是否为空,若为空则抛出断言失败assert(_size != 0);// 返回栈顶元素的值,并递减栈大小return _data[--_size];}// 查看栈顶元素的值,不改变栈状态const T& top(){// 断言检查当前栈是否为空,若为空则抛出断言失败assert(_size != 0);// 返回栈顶元素的值(动态数组的最后一个元素)return _data[_size - 1];}// 判断栈是否为空bool empty(){// 返回当前栈大小是否为0,即栈是否为空return _size == 0;}// 返回栈中元素数量size_t size(){// 返回当前栈大小(元素数量)return _size;}private:// 动态数组,用于存储栈中的元素T* _data;// 最大容量,即动态数组的容量size_t _capacity;// 当前数量,即栈中元素的数量size_t _size;
};

我们可以测试一下:

#include"my_stack.h"int main()
{MyStack<int> mystack;mystack.push(23);mystack.push(2);mystack.push(20);mystack.push(11);mystack.push(20);std::cout<<"size of mystack: "<<mystack.size()<<std::endl;while(!mystack.empty()){std::cout<<mystack.pop()<<std::endl;}if(mystack.empty()==true){std::cout<<"stack is empty"<<std::endl;}return 0;
}

在这里插入图片描述

链栈的实现

上面我们使用的是数组来模拟实现的栈,我们也可以用链表来模拟栈(我这里用带尾指针双向链表来模拟):

我们还是定义一个结点类:
在这里插入图片描述

//结点类
template<class T>
struct Node
{Node():_data(T()),_next(nullptr),_prve(nullptr){}Node(const T& data):_data(data),_next(nullptr),_prve(nullptr){}//数据域T _data;//指针域Node<T>* _next;Node<T>* _prve;
};

这是单链表中的结构:
在这里插入图片描述
我们可以稍微改一下名字:
在这里插入图片描述
在这里我没有用带头结点的双向链表,所以一开始_top和_first会指向nullptr:
在这里插入图片描述
等要插入时,才插入第一个结点:
在这里插入图片描述在这里插入图片描述

void push(const T& data)
{// 当栈为空时,直接创建新的节点作为栈的第一个元素和栈顶元素if (_first == nullptr){_first = new _Node(data);_top = _first;}// 当栈非空时,创建新节点并插入到链表末尾,更新栈顶指针else{_Node* newnode = createNode(data); // 创建新节点// 更新链表结构:将新节点的 _prve 指针指向当前栈顶节点newnode->_prve = _top;// 将当前栈顶节点的 _next 指针指向新节点_top->_next = newnode;// 更新栈顶指针,使新节点成为新的栈顶元素_top = newnode;}// 增加栈大小_size++;
}

下面是完整代码:

#pragma once
#include<iostream>// 结点类
template<class T>
struct Node
{// 默认构造函数,初始化数据和指针为默认值Node(): _data(T()), _next(nullptr), _prve(nullptr){}// 带参构造函数,根据给定数据初始化结点Node(const T& data): _data(data), _next(nullptr), _prve(nullptr){}// 数据域,存储链栈中实际的元素值T _data;// 指针域,分别指向下一个结点和前一个结点Node<T>* _next;Node<T>* _prve;
};// 链栈类
template<class T>
class MyStack 
{// 内部类型定义,简化代码中的类型书写typedef Node<T> _Node;public:// 构造函数,初始化栈为空MyStack(): _first(nullptr){_top = _first;}// 创建结点_Node* createNode(const T& data){_Node* newnode = new _Node(data);if (newnode == nullptr){exit(EXIT_FAILURE); // 如果内存分配失败,直接终止程序}return newnode;}// 压栈操作,将新元素添加到栈顶void push(const T& data){if (_first == nullptr) // 当栈为空时{_first = new _Node(data); // 创建新节点作为栈的第一个元素和栈顶元素_top = _first;}else // 当栈非空时{_Node* newnode = createNode(data); // 创建新节点// 更新链表结构:将新节点的 _prve 指针指向当前栈顶节点newnode->_prve = _top;// 将当前栈顶节点的 _next 指针指向新节点_top->_next = newnode;// 更新栈顶指针,使新节点成为新的栈顶元素_top = newnode;}// 增加栈大小_size++;}// 出栈操作,删除栈顶元素并返回其值T pop(){T top = _top->_data; // 保存栈顶元素的值if (_top == _first) // 当栈只剩一个元素时{delete _top; // 删除栈顶元素_top = nullptr;_first = nullptr; // 清空栈}else // 当栈中有多个元素时{_Node* prve = _top->_prve; // 获取栈顶元素的前一个结点prve->_next = nullptr; // 断开与已删除节点的连接delete _top; // 删除栈顶元素_top = prve; // 更新栈顶指针}// 减小栈大小--_size;return top; // 返回栈顶元素的值}// 查看栈顶元素的值,不改变栈状态const T& top() const{return _top->_data;}// 判断栈是否为空bool empty() const{return _size == 0;}// 返回栈中元素数量size_t size() const{return _size;}private:// 第一个结点,用于初始化栈_Node* _first = nullptr;// 栈顶指针,始终指向栈顶元素_Node* _top;// 当前元素数量,表示栈大小size_t _size = 0;
};

测试一下:

//#include"my_stack_sequence.h"
#include"my_stack_link.h"int main()
{MyStack<int> mystack;mystack.push(23);mystack.push(2);mystack.push(20);mystack.push(11);mystack.push(20);std::cout<<"size of mystack: "<<mystack.size()<<std::endl;while(!mystack.empty()){std::cout<<mystack.pop()<<std::endl;}if(mystack.empty()==true){std::cout<<"stack is empty"<<std::endl;}return 0;
}

在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C++初阶】C++简单入门(长期维护)

本篇博客是对C的一些简单知识分享&#xff0c;有需要借鉴即可。 C简单入门目录 一、C前言1.C的概念&#xff1a;2.C发展历程3.C如何学&#xff1f; 二、C入门1.C关键字(C98标准)2.命名空间3.C输入&输出①概念说明②使用说明③特征说明④细节拓展⑤cout与cin的意义 4.缺省参…

处理json文件,并将数据汇总至Excel表格

从scores.jason文件中读取学生信息,输出学生的学号&#xff0c;姓名&#xff0c;各科成绩&#xff0c;平均分, 各科标准差 scores.jason {"学院": "计算机学院","班级": "2022级1班","成绩": [{"学号": 1001,&q…

【vue】绑定事件 v-on

v-on 简写&#xff1a; clickkeyupkeydownkeyup.wkeyup.ctrl.a <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><…

BK9534 博通BEKEN 无线麦克风芯片 提供配置工具软件

BK9534 芯片是在 BK9532 芯片基础上增加了一个内置MCU 来实现单芯片简单工作模式&#xff0c;内置己经固化了如开关机&#xff0c;对码&#xff0c;低电侦测&#xff0c;自动频率跟随等基本功能。另外还可以借助工具修改如频率&#xff0c;ID等相关配置信息. 1. 升级了接收芯片…

SpringBoot修改菜品模块开发

需求分析与设计 一&#xff1a;产品原型 在菜品管理列表页面点击修改按钮&#xff0c;跳转到修改菜品页面&#xff0c;在修改页面回显菜品相关信息并进行修改&#xff0c;最后点击保存按钮完成修改操作。 修改菜品原型&#xff1a; 二&#xff1a;接口设计 通过对上述原型图…

Midjourney常见玩法及prompt关键词技巧

今天系统给大家讲讲Midjourney的常见玩法和prompt关键词的一些注意事项&#xff0c;带大家入门&#xff5e;&#xff08;多图预警&#xff0c;建议收藏&#xff5e;&#xff09; 一、入门及常见玩法 1、注册并添加服务器&#xff08;会的童鞋可跳过&#xff5e;&#xff09; …

SpringBoot与MyBatisPlus的依赖版本冲突问题

记录使用SpringBoot和MyBatisPlus时遇到的版本冲突问题解决。 java版本&#xff1a;jdk17 废话&#xff1a;&#xff09;目前在IDEA中使用Spring官方的脚手架最低jdk版本竟然是jdk17了。 当使用SpringBoot3.0版本(3.2.4)&#xff0c;配合使用MP3.5.2版本时报错&#xff1a; Er…

H5代码video标签引入视频在浏览器的兼容性问题解决办法

H5标签video引入视频&#xff0c;在谷歌浏览器正常但是在火狐浏览器和版本较低的浏览器或者IE浏览器却无法观看视频&#xff0c;只能看到音频&#xff0c;是什么原因&#xff1f; 代码如下 <video class"video" muted loop"loop" style"display…

前端三剑客 —— JavaScript (第九节)

目录 内容回顾&#xff1a; 1.事件解除 2. Ajax jQuery选择器 回顾CSS选择器 CSS选择 1.基本选择器 2.包含选择器 3.伪类选择器 4.伪元素选择器 5.属性选择器 jQuery 库 jQuery 动画 系统动画 自定义动画 常见API操作 内容回顾&#xff1a; 1.事件解除 如果是使…

《由浅入深学习SAP财务》:第2章 总账模块 - 2.6 定期处理 - 2.6.3 月末操作:外币评估

2.6.3 月末操作&#xff1a;外币评估 企业的外币业务在记账时一般使用期初的汇率或者即时汇率&#xff0c;但在月末&#xff0c;需要按照月末汇率对外币的余额或者未清项进行重估&#xff08;revaluation&#xff09;。 企业在资产负债表日&#xff0c;应当按照下列规…

微信小程序全局配置

全局配置文件及常用的配置项 小程序根目录下的 app.json 文件是小程序的全局配置文件。常用的配置项如下&#xff1a; ① pages 记录当前小程序所有页面的存放路径 ② window 全局设置小程序窗口的外观 ③ tabBar 设置小程序底部的 tabBar 效果 ④ style 是否启用新版的组件样…

SpringBoot菜品分页查询模块开发(多表连接查询)

需要注意的地方 为什么创建VO类怎么进行多表连接查询分页查询的统一返回结果类PageResult分页查询Mapper的返回结果是Page<目标实体类> 需求分析与设计 一&#xff1a;产品原型 系统中的菜品数据很多的时候&#xff0c;如果在一个页面中全部展示出来会显得比较乱&…

华火电燃灶荣获国家级科技型中小企业

华火电燃灶作为一家国家级科技型中小企业&#xff0c;凭借其创新的技术和卓越的产品性能&#xff0c;在新能源厨电领域取得了显著的成就。华火&#xff0c;潜心钻研等离子电生明火技术近十年&#xff1b;华火电燃灶&#xff0c;电生明火&#xff0c;以“电”作为唯一能源&#…

创建影子用户

文章目录 1.认识影子用户2.创建隐藏账户并加入管理员组3.修改注册表3.删除用户4.添加管理员权限 1.认识影子用户 影子用户通常指的是那些在系统用户列表中不可见&#xff0c;但在某些情况下可以进行操作的用户。在内网渗透过程中&#xff0c;当我们拿到shell时&#xff0c;肯定…

uniapp--登录和注册页面-- login

目录 1.效果展示 2.源代码展示 测试登录 login.js 测试请求 request.js 测试首页index.js 1.效果展示 2.源代码展示 <template><view><f-navbar title="登录" navbarType="4"></f-navbar><view class="tips">…

碳课堂|碳关税是什么?企业如何从容应对?

2023年10月1日&#xff0c;欧盟碳边境调节机制&#xff08;CBAM&#xff09;法规&#xff0c;即全球首个“碳关税”开始实施。据世界银行研究报告称&#xff0c;如果“碳关税”全面实施&#xff0c;在国际市场上&#xff0c;中国制造可能将面临平均26%的关税&#xff0c;出口量…

李沐41_物体检测和数据集——自学笔记

边缘框 1.一个边缘框可以通过4个数字定义&#xff08;左上xy&#xff0c;右上xy&#xff0c;左下xy&#xff0c;右下xy&#xff09; 2.标注成本高 目标检测数据集 1.每行表示一个物体&#xff08;图片文件名、物体类别、边缘框&#xff09; 2.COCO&#xff1a;80物体、330…

前端跨域怎么办?

如果网上搜到的方法都不可行或者比较麻烦&#xff0c;可以尝试改变浏览器的设置&#xff08;仅为临时方案&#xff09; 1.新建一个Chrome浏览器的快捷方式 2.鼠标右键&#xff0c;进入属性&#xff0c;将以下命令复制粘贴到目标位置&#xff08;可根据Chrome实际存放位置修改…

数据结构之树的性质总结

节点的度&#xff1a;该节点拥有的孩子个数 叶子节点&#xff1a;度为0的节点 层数&#xff1a;根节点为第一层&#xff0c;根的子节点为第二层&#xff0c;以此类推 所有树的性质&#xff1a;所有节点的总度数等于节点数减一 完全m叉树性质 完全m 叉树&#xff0c;节点的…

【Hello算法】 > 第 2 关 >数据结构 之 数组与链表

数据结构 之 数组与链表 1&#xff1a;Understanding data structures &#xff01;——了解数据结构——1.1&#xff1a;Classification-分类-1.2&#xff1a;Type-类型- 2&#xff1a;Arrays are the bricks that make up the wall of data structures *——数组是组成数据结…