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

数据结构-顺序栈C++示例

(stack)是限定仅在表尾进行插入或删除操作的线性表。

对栈来说,表尾端称为栈顶(top), 表头端称为栈底(bottom),不含元素的空表称为空栈

假设栈 S = ( a 1 , a 2 , a 3 , ⋯ , a n ) S=(a_1,a_2,a_3,\cdots,a_n) S=(a1,a2,a3,,an) , 则称 a 1 a_1 a1为栈底元素, a n a_n an为栈顶元素,插入元素到栈顶(即表尾)的操作称为入栈, 从栈顶(即表尾)删除最后一个元素的操作称为出栈。栈元素的修改是按后进先出的原则进行的,因此栈又称为后进先出(Last In First Out, LIFO)的线性表。

由于栈固有的后进先出特性,使得栈称为程序设计中的有用工具,另外,如果问题求解的过程具有“后进先出”的天然特性的话,则求解的算法中也需要利用“栈”, 如:

  • 数制转换
  • 表达式求值
  • 括号匹配的检验
  • 八皇后问题
  • 行编辑程序
  • 函数调用
  • 迷宫求解
  • 递归调用的实现

抽象数据类型定义

ADT Stack{

​ 数据对象: D = { a i ∣ a i ∈ E l e m S e t , i = 1 , 2 , 3 , ⋯ , n , n ≥ 0 } D=\{{a_i}| a_i \in ElemSet, i=1,2,3,\cdots,n, n \geq 0\} D={aiaiElemSet,i=1,2,3,,n,n0}

​ 数据关系: R = { < a i − 1 , a i > ∣ a i − 1 , a i ∈ D , i = 1 , 2 , 3 , ⋯ , n } R=\{<a_{i-1}, a_i> | a_{i-1},a_i \in D, i = 1,2,3,\cdots,n\} R={<ai1,ai>ai1,aiD,i=1,2,3,,n}

​ 约定 a n a_n an 端为栈顶, a 1 a_1 a1 端为栈底。

​ 基本操作:

InitStack(&S)

​ 操作结果:构造一个空栈 S S S

DestroyStack(&S)

​ 初始条件:栈 S S S已经存在

​ 操作结果:栈 S S S被销毁

ClearStack(&S)

​ 初始条件:栈 S S S已经存在

​ 操作结果:将栈 S S S 清空

StackEmpty(&S)

​ 初始条件:栈 S S S已经存在

​ 操作结果:若栈 S S S 为空栈,则返回true, 否则返回false

StackLength(&S)

​ 初始条件:栈 S S S已经存在

​ 操作结果:返回栈 S S S 的元素个数,即栈的长度

GetTop(&S)

​ 初始条件:栈 S S S已经存在且非空

​ 操作结果:返回栈 S S S 的栈顶元素

Push(&S,e)

​ 初始条件:栈 S S S已经存在

​ 操作结果:插入元素e为新的栈顶元素

Pop(&S,e)

​ 初始条件:栈 S S S已经存在且非空

​ 操作结果:删除S的栈顶元素,并且用e 返回其值

StackTraverse(&S,e)

​ 初始条件:栈 S S S已经存在且非空

​ 操作结果:从栈底到栈顶一次对S的每个数据元素进行访问

}ADT Stack

顺序栈

顺序栈是指利用顺序存储结构实现的栈。

初始化
bool InitStack(SqStack &S)
{S.base = new SElemType[MaxSize];if (!S.base){std::cerr << "内存分配失败" << std::endl;return false;}S.front = S.base;S.stacksize = MaxSize;return true;
}
销毁
bool DestroyStack(SqStack &S)
{if (S.base){delete[] S.base;S.stacksize = 0;S.base = S.front = nullptr;return true;}return false;
}
清空
bool ClearStack(SqStack &S)
{if (S.base){S.front = S.base;return true;}return false;
}
是否为空栈
bool StackEmpty(const SqStack &S)
{return S.base == S.front;
}
栈长度
int StackLength(const SqStack &S)
{return S.front - S.base;
}
入栈
bool Push(SqStack &S, const SElemType &e)
{if (S.front - S.base == S.stacksize){std::cerr << "顺序栈已满,无法插入新元素" << std::endl;return false;}*(S.front) = e;S.front++;return true;
}
出栈
bool Pop(SqStack &S, SElemType &e)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}S.front--;e = *(S.front);return true;
}
获取栈顶元素
SElemType GetTop(const SqStack &S)
{if (StackEmpty(S)){std::cerr << "空栈无法取值" << std::endl;return false;}return *(S.front - 1);
}
遍历栈元素
void StackTraverse(const SqStack &S)
{for (int i = 0; i < S.front - S.base; i++){std::cout << "第 " << i + 1 << " 个元素为: " << S.base[i] << std::endl;}
}
头文件
#pragma once
#include <iostream>const int MaxSize = 100;
typedef int SElemType;
typedef struct _SqStack
{SElemType *base;  // 栈底SElemType *front; // 栈顶int stacksize;    // 栈可用的最大容量
} SqStack;bool InitStack(SqStack &S);
bool DestroyStack(SqStack &S);
bool ClearStack(SqStack &S);
bool StackEmpty(const SqStack &S);
int StackLength(const SqStack &S);
bool Push(SqStack &S, const SElemType &e);
bool Pop(SqStack &S, SElemType &e);
void StackTraverse(const SqStack &S);
SElemType GetTop(const SqStack &S);
测试文件
#include "include/stack.h"int main()
{SqStack S;InitStack(S);Push(S, 1);Push(S, 2);Push(S, 3);Push(S, 4);StackTraverse(S);SElemType top = GetTop(S);std::cout << "栈顶元素为: " << top << std::endl;int stack_len = StackLength(S);std::cout << "栈长度: " << stack_len << std::endl;Pop(S, top);StackTraverse(S);std::cout << "++++++++++++++" << std::endl;ClearStack(S);StackTraverse(S);DestroyStack(S);return 0;
}

链栈

链栈是指采用链式存储结构实现的栈。通常使用单链表来表示,由于栈的主要操作是在栈顶插入和删除,为了方便,这里将链表的头结点作为栈顶,且不需要头结点

初始化
bool InitStack(LinkStack &S)
{S = nullptr;return true;
}
销毁
bool DestroyStack(LinkStack &S)
{while (S){StackNode *tmp = S->next;S = S->next;delete tmp;}return true;
}
清空
bool ClearStack(LinkStack &S)
{DestroyStack(S->next);S = nullptr;return true;
}
是否为空栈
bool StackEmpty(const LinkStack &S)
{return !S;
}
栈长度
int StackLength(const LinkStack &S)
{int len = 0;StackNode *tmp = S;while (tmp){len++;tmp = tmp->next;}return len;
}
入栈
bool Push(LinkStack &S, const ElemType &e)
{StackNode *p = new StackNode;p->data = e;p->next = S;S = p;return true;
}
出栈
bool Pop(LinkStack &S, ElemType &e)
{if (S){e = S->data;StackNode *tmp = S;S = S->next;delete tmp;return true;}return false;
}
获取栈顶元素
ElemType GetTop(const LinkStack &S)
{if (S)return S->data;else{return 0;}
}
遍历栈元素
void StackTraverse(const LinkStack &S)
{StackNode *tmp = S;int i = 0;while (tmp){i++;std::cout << "第 " << i << " 个元素为: " << tmp->data << std::endl;tmp = tmp->next;}
}

文章参考 严蔚敏老师《数据结构 C语言版 第2版》和青岛大学王卓数据结构视频课

相关文章:

数据结构-顺序栈C++示例

栈(stack)是限定仅在表尾进行插入或删除操作的线性表。 对栈来说&#xff0c;表尾端称为栈顶(top)&#xff0c; 表头端称为栈底(bottom)&#xff0c;不含元素的空表称为空栈。 假设栈 S ( a 1 , a 2 , a 3 , ⋯ , a n ) S(a_1,a_2,a_3,\cdots,a_n) S(a1​,a2​,a3​,⋯,an​…...

若依cloud -【 100 ~ 103 】

100 分布式日志介绍 | RuoYi 分布式日志就相当于把日志存储在不同的设备上面。比如若依项目中有ruoyi-modules-file、ruoyi-modules-gen、ruoyi-modules-job、ruoyi-modules-system四个应用&#xff0c;每个应用都部署在单独的一台机器里边&#xff0c;应用对应的日志的也单独存…...

可转债实战与案例分析——成功的和失败的可转债投资案例、教训与经验分享

实战与案例分析——投资案例研究 股票量化程序化自动交易接口 一、成功的可转债投资案例 成功的可转债投资案例提供了有价值的经验教训&#xff0c;以下是一个典型的成功案例&#xff1a; 案例&#xff1a;投资者B的成功可转债投资 投资者B是一位懂得风险管理的投资者&#…...

@NotNull注解不生效,全局异常处理

1.引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-validation</artifactId><version>3.1.2</version> </dependency> 2&#xff1a;实体类 实体类属性加上NotNull注解…...

【办公自动化】使用Python一键往Word文档的表格中填写数据(文末送书)

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

OpenHarmony应用核心技术理念与需求机遇简析

一、核心技术理念 图片来源&#xff1a;OpenHarmony官方网站 二、需求机遇简析 新的万物互联智能世界代表着新规则、新赛道、新切入点、新财富机会;各WEB网站、客户端( 苹果APP、安卓APK)、微信小程序等上的组织、企业、商户等;OpenHarmony既是一次机遇、同时又是一次大的挑战&…...

让Pegasus天马座开发板实现超声波测距

在完成《让Pegasus天马座开发板用上OLED屏》后&#xff0c;我觉得可以把超声波测距功能也在Pegasus天马座开发板上实现。于是在箱子里找到了&#xff0c;Grove - Ultrasonic Ranger 这一超声波测传感器。 官方地址: https://wiki.seeedstudio.com/Grove-Ultrasonic_Ranger 超声…...

C++11 多线程学习

C11学习 一、多线程 1、模板线程是以右值传递的 template <class Fn, class... Args> explicit thread(Fn&& fn, Args&&... args)则需要使用到std::ref和std::cref很好地解决了这个问题&#xff0c;std::ref 可以包装按引用传递的值。 std::cref 可以…...

数学公式测试

MVP变换 MVP变换用来描述视图变换的任务&#xff0c;即将虚拟世界中的三维物体映射&#xff08;变换&#xff09;到二维坐标中。 MVP变换分为三步&#xff1a; 模型变换(model tranformation)&#xff1a;将模型空间转换到世界空间&#xff08;找个好的地方&#xff0c;把所…...

机器学习——SVM(支持向量机)

0、前言&#xff1a; SVM应用&#xff1a;主要针对小样本数据进行学习、分类和回归&#xff08;预测&#xff09;&#xff0c;能解决神经网络不能解决的过学习问题&#xff0c;有很好的泛化能力。&#xff08;注意&#xff1a;SVM算法的数学原理涉及知识点比较多&#xff0c;所…...

【李沐深度学习笔记】基础优化方法

课程地址和说明 基础优化方法p2 本系列文章是我学习李沐老师深度学习系列课程的学习笔记&#xff0c;可能会对李沐老师上课没讲到的进行补充。 基础优化方法 在讲具体的线性回归实现之前&#xff0c;要先讲一下基础的优化模型的方法 梯度下降 当模型没有显示解&#xff08…...

tmux 配置vim风格按键,支持gbk编码

vim修改~/.tmux.conf文件&#xff0c;没有则新增&#xff0c;添加如下内容。默认前缀更改为Ctrla。强烈建议更换Caps lock键位与Ctrl键位&#xff0c;用过的都说好&#xff0c;换过就回不来了。 unbind C-b set -g prefix C-a bind a send-prefixset -sg escape-time 1bind r …...

Python —— excel文件操作(超详细)

背景 很多公司还是用excel去管理测试用例的&#xff0c;所以为了减少重复繁琐的导出导出工作&#xff0c;学会如何用代码操作excel表格很实用~ 1、读取excel文件基本步骤 1、操作excel的一些库 1、xlrd&#xff1a;读取库&#xff0c;xlwt&#xff1a;写入&#xff0c;现在…...

什么是AI问答机器人?它的应用场景有哪些?

近年来&#xff0c;由于技术的进步和对个性化客户体验的需求不断增长&#xff0c;AI问答机器人也是获得了巨大的关注。AI问答机器人&#xff0c;也被称为AI聊天机器人&#xff0c;是一种旨在模拟人类对话并通过基于文本或语音的界面与用户交互的计算机程序。其能够自动执行各种…...

静态文件

静态文件 静态文件配置 - settings.py中 1&#xff0c;配置静态文件的访问路径【该配置默认存在】 通过哪个url地址找静态文件 STATIC URL‘/static/’ 说明 指定访问静态文件时是需要通过/static/xxx或http://127.0.0.1:8000/static/xxx [xxx表示具体的静态资源位置] 模…...

Centos7 自部署中间件开机启动,以及java应用开机启动方法

一、zookeeper cd /etc/rc.d/init.d/ touch zookeeper chmod x zookeeper vi zookeeper#以下为内容&#xff0c;自行修改 路径#!/bin/bash ##chkconfig:2345 10 90#description:service zookeeper #修改为自己的目录 export ZOO_LOG_DIR/data/apache-zookeeper-3.7.0/logs…...

密度估计公式

极大似然估计&#xff1a; y p ( x 1 , x 2 , x 3 , . . . , x n ) 1 2 π σ e − ( x 1 − μ ) 2 2 σ 2 1 2 π σ e − ( x 2 − μ ) 2 2 σ 2 . . . 1 2 π σ e − ( x n − μ ) 2 2 σ 2 y p(x_1,x_2,x_3,...,x_n) \frac{1}{\sqrt{2\pi} \sigma} e ^{-\frac{(x_1…...

2023 ICPC 网络赛 第一场(补题:F)

7题罚时879&#xff0c; 队排235&#xff0c;校排79。 除了I题dp没注意空间限制第一发没有用滚动数组MLE&#xff0c;以及G题启发式合并脑抽用set当容器T一发&#xff0c;以及K没注意是平方的期望白wa4发这些应当避免的失误外&#xff0c;基本满意。剩下的题基本都是当时写不出…...

MySQL慢查询优化、日志收集定位排查、慢查询sql分析

MySQL慢查询日志收集、定位&#xff0c;慢查询分析、排查。 一 MySQL慢查询定位 1. 确定是否已开启慢查询日志 查看慢查询日志是否已经被开启&#xff1a; SHOW VARIABLES LIKE slow_query_log; 如果返回值是OFF&#xff0c;你需要开启它。 2. 开启慢查询日志 你可以临时在运…...

HZOJ-266:表达式计算

题目描述 ​ 给出一个表达式,其中运算符仅包含 ,-,*,/,^ 要求求出表达式的最终值。 ​ 数据可能会出现括号情况&#xff0c;还有可能出现多余括号情况&#xff0c;忽略多余括号&#xff0c;正常计算即可&#xff1b; ​ 数据保证不会出现大于 max long int 的数据&#xff1…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

基于TurtleBot3在Gazebo地图实现机器人远程控制

1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

android RelativeLayout布局

<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...

离线语音识别方案分析

随着人工智能技术的不断发展&#xff0c;语音识别技术也得到了广泛的应用&#xff0c;从智能家居到车载系统&#xff0c;语音识别正在改变我们与设备的交互方式。尤其是离线语音识别&#xff0c;由于其在没有网络连接的情况下仍然能提供稳定、准确的语音处理能力&#xff0c;广…...