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

数据结构--栈

线性表的定义

前面文章有讲过,线性表就是一次保存单个同类型元素,多个元素之间逻辑上连续
例子:数组,栈,队列,字符串

1.1 栈和队列的特点

栈和队列都是操作受限的线性表。
前面学过的数组,链表,是可以菜任意位置插入和删除的
而栈和队列只能在一端插入元素和删除元素

1.2 栈的定义

只能在一端插入元素(栈顶),也只能从这一端取出元素(栈顶)

先看下入栈的动画:
在这里插入图片描述

再看下出栈的动画:
在这里插入图片描述

利用数组模拟栈,每次入栈从数组后面追加,数组开头是栈底,数组末尾为栈顶。
在这里插入图片描述
在这里插入图片描述

模拟实现栈思路

1、定义

定义stk[N]top 为栈顶 因为栈是一种先进后出的结构。

2、实现初始化

top=-1对栈进行初始化,表示空

3、实现压栈和出栈

压栈 需要++top 然后读入即可 stk[++top]=x
出栈 只需 --top

4、判断栈是否为空

只要top>0栈就不为空
栈顶stk[top]

#include <iostream>using namespace std;const int N = 100010;// stk[N] 为栈, tt 为栈顶下标
int stk[N], tt;// 插入一个数, 栈顶++
stk[ ++ tt] = x;// 弹出
tt --;// 判断栈是否为空
if(tt > 0) not empty
else empty// 栈顶
stk[tt];

Acwing 828

#include <iostream>using namespace std;const int N = 100010;int m;
int stk[N], top;int main()
{cin >> m;while(m --){string op;int x;cin >> op;if(op == "push"){cin >> x;stk[ ++ top] = x;}else if(op == "pop"){-- top;}else if(op == "empty"){//如果top>0 则输出no 否则输出yescout << (top ? "NO" : "YES") << endl;}else{cout << stk[top] << endl;}}return 0;
}

Acwing 830 单调栈

#include <iostream>using namespace std;const int N = 100010;int n;
int stk[N], tt;int main()
{cin >> n;for(int i = 0; i < n; i ++){int x;cin >> x;while(tt && stk[tt] >= x) tt --;if(tt) cout << stk[tt] << ' ';else cout << -1 << ' ';stk[++ tt] = x;}return 0;
}
时间复杂度

每个数只会进栈一次,出栈一次,整个时间复杂度是O(n)。

总结

学数据结构 最主要的还是要画图,先画一遍,代码自然就能够写了

http://www.lryc.cn/news/179996.html

相关文章:

  • 期权定价模型系列【7】:Barone-Adesi-Whaley定价模型
  • 【Axure高保真原型】3D圆柱图_中继器版
  • 多个线程启动 ,等待全部执行完毕再搜集数据
  • 【VIM】VIm-plug插件
  • ssl证书 阿里的域名,腾讯云的证书
  • 力扣算法题:34、在排序数组中查找元素的第一个和最后一个位置.java版
  • [网鼎杯 2020 朱雀组]Nmap
  • 【Leetcode】166.分数到小数
  • 2023-10-01 LeetCode每日一题(买卖股票的最佳时机)
  • 解决 ARouter 无法生成路由表,Toast提示 找不到目标路由
  • 排序算法之【希尔排序】
  • 防火墙基础之H3C防火墙分支与分支之间双向地址转换
  • 【考研数学】概率论与数理统计 —— 第三章 | 二维随机变量及其分布(1,二维连续型和离散型随机变量基本概念与性质)
  • cesium 雷达扫描 (波纹线性雷达扫描效果)
  • SLAM从入门到精通(tf的使用)
  • python代码混淆与代码打包
  • Codeforces Round 899 (Div. 2)
  • 【 SuperPoint 】图像特征提取上的对比实验
  • Chrome获取RequestId
  • cesium 雷达扫描 (线行扩散效果)
  • 【React】React组件生命周期以及触发顺序(部分与vue做比较)
  • 【C++】多线程的学习笔记——白话文版(bushi
  • 图像处理: ImageKit.NET 3.0.10704 Crack
  • K8S内容分发网络之集群,nginx,负载均衡,防火墙
  • 不愧是疑问解决神器!你强任你强
  • 盛最多水的容器 接雨水【基础算法精讲 02】
  • WordPress主题开发( 十二)之—— 主题的functions.php
  • 代码的工厂模式
  • UE5.1编辑器拓展【一、脚本化资产行为,通知,弹窗,高效复制多个同样的资产】
  • mac openssl 版本到底怎么回事 已解决