【数据结构】栈：Java实现顺序栈&栈应用浅析-程序员宅基地

1.栈是什么

定义：后进者先出，先进者后出，这就是典型的“栈”结构
操作特性：栈是一种“操作受限”的线性表，只允许在一端插入和删除数据。
使用场景；当某个数据集合只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性，就应该首选“栈”这种数据结构。

2.Java实现顺序栈

用数组实现的栈，我们叫作顺序栈（效率高），而用链表实现的栈，我们叫作链式栈。

2.1 固定大小的栈

时间复杂度：O（1），每次都只操作count（-1）位，与数据规模无关
空间复杂度：O（1），最开始申请了固定大小数组后运行时不再改变大小，与数据规模无关

public class MyStack {
    
    // 为了简单，这里直接定义成int
    private int[] items;
    private int size; // 栈容量
    private int count; // 栈中实际元素多少
    
    // 指定大小构造
    public MyStack(int size) {
    
        this.size = size; 
        this.items = new int[size];
        this.count = 0;
    }

    // push:每次都给items[count]
    public boolean push(int item) {
    
        // 非满判断
        if (count == size) return false;
        this.items[count] = item; // 关键
        count++;
        return true;
    }

    // pop:items[count-1]
    // 这里count是数组实际元素多少，若不减一返回0
    public int pop() {
    
        // 非空判断
        if (count == 0) return 0;
        int item = this.items[count-1]; // 关键
        count--;
        return item;
    }

    public int peek() {
    
    	// 这里注意要判断栈中是否有元素
        return count == 0 ? 0 : this.items[count-1];
    }
}

上面是基于数组实现的栈，是一个固定大小的栈，也就是说，在初始化栈时需要事先指定栈的大小。当栈满之后，就无法再往栈里添加数据了。

2.2 动态扩容的栈

尽管链式栈的大小不受限，但要存储 next 指针，内存消耗相对较多。因而实现一个基于数组的动态扩容的栈

最好情况复杂度：O(1）
最坏情况复杂度：O(n)，满了需要扩容
均摊时间复杂度（if{for}）：O(1)，平均到每次push相当于每次只扩容一个

public boolean push(int item) {
    
       // 满了就扩容，只有push涉及扩容
       if (count == size) resize();
       this.items[count] = item;
       count++;
       return true;
}

private void resize() {
    
    int[] newItem = new int[size << 1]; // 将容量变为两倍
    System.arraycopy(items,0,newItem,0,size); // 关键，所有数组的动态扩容本质上都是数组拷贝
    this.items = newItem; // 修改指针指向新数组
}

3.栈的应用

3.1 函数调用栈

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量
每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成返回之后，将这个函数对应的栈帧出栈

int main() {
       
    int a = 1;  
    int ret = 0; 
    int res = 0;  
    ret = add(3, 5);
    res = a + ret; 
    printf("%d", res);   
    reuturn 0;\
}
 
int add(int x, int y) {
       
    int sum = 0;
    sum = x + y; 
    return sum; 
}

在这里插入图片描述

3.2 实现计算器

使用两个栈：操作数栈和符号栈
操作数和符号依次入栈，当 - 和 ÷ 要入栈时清空栈（操作数先出栈，符号再出栈 —> 结果）

比如现在要计算 3 + 5 x 8 - 6 的结果，过程其实很简单：
在这里插入图片描述

3.3 浏览器后退前进

使用两个栈：X(后退栈) 和 Y（前进栈）

把首次浏览的页面依次压入栈 X。比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。比如从页面 c 后退到页面 a 之后，就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bA59r5rb-1601053506076)(03 线性表：栈.assets/1584934365362.png)]

当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。比如这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中
当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。比如，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y

在这里插入图片描述

本文链接：https://blog.csdn.net/weixin_43935927/article/details/108807001

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

浅谈数据安全-程序员宅基地

文章浏览阅读4.4k次。在《网络安全法》中，虽然已经明确了要求保障网络数据的完整性、保密性、可用性的能力，但随着近些年数据安全热点事件的出现，如数据泄露事件、个人信息滥用事件。表明对数据保护的要求仅依赖《网络安全法》中的几款条例是不足以支撑的。因此2021年9月1日《中华人民共和国数据安全法》便正式诞生，从此数据安全也被推上了风口浪尖。那么数据安全如何定义？与传统网络安全有何区别？数据安全体系又应该如何建立？..._数据安全

Leetcode 第338，342，344，345，367，389，392，404，405，409题(Java解法)-程序员宅基地

文章浏览阅读194次。Java解leetcode，助力面试之简单10道题（五）第338题比特位计数解题思路代码第342题 4的幂解题思路代码第344题反转字符串解题思路代码第345题反转字符串中的元音字母解题思路代码第367题有效的完全平方数解题思路代码第389题找不同解题思路代码第392题判断子序列解题思路代码第404题左叶子之和解题思路代码第405题数字转换为十六进制数解题思路代码第409题最长回文串解题思路代码第338题比特位计数示例 1：输入输出[3,2,3]3示例

C++ 学习笔记（对双端队列进行封装，实现数据生产者消费者）-程序员宅基地

文章浏览阅读698次。#pragma once #include <deque>#include <condition_variable>template <typename T>class MsgList { public: void add(const T& msg) { std::unique_lock<std::mutex> lock(mutex); queue.

python水表识别图像识别深度学习 CNN_水表深度学习识别-程序员宅基地

文章浏览阅读551次，点赞8次，收藏8次。重点：项目和文档是本人近期原创所作！程序可以将水表图片里面的数据进行深度学习，提取相关信息训练，lw1.3万字重复15%，可以直接上交那种！具体和看下面的目录。python水表识别，图像识别深度学习 CNN，Opencv,Keras。_水表深度学习识别

【DataSet】遥感图像方面的人工智能数据集_群智感知图像数据集-程序员宅基地

文章浏览阅读288次。遥感图像方面的人工智能数据集数据集类别常用数据集目标检测数据集DSTL 卫星图像数据集;RSOD-Dataset 数据集;NWPUVHR-10地理遥感数据集图像分割数据集Inria AerialImage Labeling Dataset 遥感图像数据集遥感图像分类数据集UCMerced Land-Use Data Set 土地遥感数据集_群智感知图像数据集

python使用镜像安装opencv_opencv_python安装镜像-程序员宅基地

文章浏览阅读2.9k次，点赞3次，收藏11次。如何在pycharm中安装opencv_opencv_python安装镜像

随便推点

问题记录——正则表达式匹配控制符_正则表达式匹配控制字符-程序员宅基地

文章浏览阅读910次。问题前端用xterm.js通过websocket连接docker虚拟终端，返回的字符中包括如下字符串，其中有两个控制字符，“ESC"和"BEL” ，想通过正则表达式匹配这一段字符，然后去掉这段字符:参考文档控制字符编码表转义符对照表通过上面查询得知，"ESC"和"BEL"这两个控制符的ASCII码分别为：十进制为27和7，十六进制为0x1B和0x07，转义符分别为：\e和\a代码**注意：**直接使用ASCII码匹配是不行的，一定要用转义符才行。如下测试代码中，只有regex3才能匹_正则表达式匹配控制字符

Android RIL框架分析-程序员宅基地

文章浏览阅读1.5k次。1.RIL框架 RIL，Radio Interface Layer。本层为一个协议转换层，提供Android Telephony与无线通信设备之间的抽象层。 Android RIL位于Telephony Frameworks之下，Modem之上的，根据源码，RIL可以分为两个部分:Frameworks 框架层中的java程序，简称RILJ。HAL层中C/C++程序，简称RILC，RILC具体的又包括LibRIL、Rild和Reference-RIL这三个部分。 Andr..._ril框架

Python编程基础：第六节 math包的基础使用Math Functions_ps math function-程序员宅基地

文章浏览阅读565次。第六节 math包的基础使用前言实践前言我们通常会对数值型变量进行计算，这里我们给出一些常用的函数用于辅助你的计算过程。常用的数学计算函数均在math包。实践首先我们导入math包，并定义一个浮点型变量pi将其赋值为3.14：import mathpi = 3.14如果我们需要计算浮点型变量四舍五入后的计算结果，用函数round()即可：print(round(pi))>>> 3如果我们需要向上取整，那就需要函数math.ceil()：print(math.cei_ps math function

canal异常 Could not find first log file name in binary log index file_canal could not find first log file name in binary-程序员宅基地

文章浏览阅读4.4k次，点赞3次，收藏2次。Could not find first log file name in binary log index file问题解决解决过程问题最近在使用canal来监测数据库的变化，处理变动的数据。由于有一段时间没有用了，这次启动在日志文件中看到这个异常 Could not find first log file name in binary log index file，详细信息如下：2020-12-16 19:14:42.053 [destination = tradeAndRefund , addr_canal could not find first log file name in binary log index file

【练习】生成10个1到20之间的不重复的随机数并降序输出-程序员宅基地

文章浏览阅读960次。分析：1.创建一个Random对象；2.创建一个hashset的集合对象；3.循环生成10个1-20的随机数4.输出。package edu.xalead;import java.util.*;public class Test { public static void main(String[] args) { Random r...

linux系统扩展名大全,Linux系统文件扩展名学习-程序员宅基地

文章浏览阅读3.2k次。Linux系统下的扩展名并不能标识该文件是属于哪一种类型的文件。文件是否可以执行等都跟文件的扩展名无关。因为文件script没有执行权限，所以也就无法执行，sh-3.2# touch ./scriptsh-3.2# ls -lh ./script-rw-r--r-- 1 root root 0 Dec 28 06:15 ./scriptsh-3.2#sh-3.2# ./scriptsh: /scr..._linux的扩展名