数据结构之探索“栈”的奥秘

2024-06-19 12:28
文章标签 数据结构 探索 奥秘

本文主要是介绍数据结构之探索“栈”的奥秘,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

找往期文章包括但不限于本期文章中不懂的知识点:

个人主页:我要学编程(ಥ_ಥ)-CSDN博客

所属专栏:数据结构(Java版)

目录

栈的有关概念

栈的使用 

栈的模拟实现

栈的应用场景

改变元素的序列

将递归转化为循环 

栈的相关刷题 

20. 有效的括号

150. 逆波兰表达式求值

牛客网——JZ31 栈的压入、弹出序列

155. 最小栈


栈的有关概念

栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

压栈:栈的插入操作叫做进栈/压栈/入栈。 出栈:栈的删除操作叫做出栈。

下面是栈以及其有关操作的图示:

栈的使用 

栈的基本方法
方法功能
Stack()构造一个空的栈
E push(E e)将e入栈,并返回e
E pop()得到并删除栈顶元素
E peek()获取栈顶元素
int size()获取栈中有效元素的个数
boolean empty()检测栈是否为空

下面是上面方法的使用:

public class Test {public static void main(String[] args) {// 构造方法:构造一个空栈Stack<Integer> stack = new Stack<>();// 判断栈是否为空System.out.println(stack.empty());// 开始往栈区增加元素:压栈/入栈stack.push(1);stack.push(2);stack.push(3);stack.push(4);stack.push(5);// 获取栈顶元素System.out.println(stack.peek());// 得到并删除栈顶元素System.out.println(stack.pop());// 获取栈中有效的元素个数int size = stack.size();System.out.println(size);// 开始利用pop方法遍历栈for (int i = 0; i < size; i++) {// 得到并删除栈顶元素System.out.println(stack.pop());}// 判断栈是否为空System.out.println(stack.empty());}
}

运行结果:

栈的模拟实现

模拟栈,就只需要实现模拟我们上面使用的那几种方法即可。

下面是用数组模拟栈的实现:

// 用数组模拟实现栈
public class MyStack {public int[] elem;public int usedSzie;public MyStack() {// 为了方便测试给三个空间this.elem = new int[3];}// 入栈public boolean push(int val) {// 先判断栈空间是否满了if (this.usedSzie == this.elem.length) {return false;}this.elem[(this.usedSzie)++] = val;return true;}// 出栈public int pop() throws StackIsEmptyException {// 先判断栈是否为空if (empty()) {throw new StackIsEmptyException("栈为空异常!");} else {this.usedSzie--;return this.elem[this.usedSzie];}}// 获取栈顶元素public int peek() {// 先判断栈是否为空if (empty()) {throw new StackIsEmptyException("栈为空异常!");} else {return this.elem[this.usedSzie-1];}}public int size() {return this.usedSzie;}public boolean empty() {return this.usedSzie == 0;}
}

异常代码:

public class MyStackIsEmptyException extends RuntimeException {public MyStackIsEmptyException(String msg) {super(msg);}public MyStackIsEmptyException() {super();}
}

除了用数组之外,还可以用链表来模拟实现:

// 用链表来模拟实现栈
public class MyStack {public LinkedList<Integer> linkedList;public MyStack () {this.linkedList = new LinkedList<>();}// 入栈public void push(int val) {// 直接尾插就行this.linkedList.addLast(val);}// 出栈public int pop() throws MyStackIsEmptyException {// 先判断链表是否为空if (empty()) {throw new MyStackIsEmptyException("栈为空异常!");}// 移除最后一个节点int ret = this.linkedList.getLast(); // 得到最后一个元素this.linkedList.removeLast();return ret;}// 获取栈顶元素public int peek() throws MyStackIsEmptyException {// 先判断链表是否为空if (empty()) {throw new MyStackIsEmptyException("栈为空异常!");}return this.linkedList.getLast();}public int size() {return this.linkedList.size();}public boolean empty() {return this.linkedList.size() == 0;}
}

当然,这里的链表没有自己实现,而是用的Java自身提供的。那么也意味着上面的数组实现,可以用顺序表来模拟,也是一样的。 

栈的应用场景

改变元素的序列

例1: 

我们知道栈要遵循一个规律:先进后出,后进先出。那么只要 先进去的 在 后进去的 前面出来,则肯定是错误的。

A选项,正确。当1进去栈,接着再出来,后面的接着全部进去,再一个一个的出来,那么结果就是 1、4、3、2。

B选项,正确。1进去,接着2进去,再出来,一直循环这个过程到全部元素进去,最后1再出来,那么结果就是2、3、4、1。 

C选项,错误。3 要出来,说明1 和 2肯定已经进去了。既然3出去了,栈中就只有1和2了,并且2在栈顶,那么就不可能出现1 比 2先出去的情况。

D选项,正确。3 要出来,肯定 1 和 2 进去了。接着 4再进去、出来。最后就是2 出来,1出来。那么结果就是3、4、2、1。

例2:

这个答案就很明显了是B。

将递归转化为循环 

例如:逆序打印单链表。

正常打印单链表是从头节点开始一直遍历到 null 就停下。但是现在要逆序打印,就是从尾节点开始打印这个单链表。

方式一,递归:

    // 逆序打印节点的值public void printList(ListNode head) {//if (head == null) {//    // 抛异常//}// 找到尾节点就停止if (head.next != null) {printList(head.next);}System.out.print(head.val+" ");}

方式二,栈:

要逆序打印单链表,就是从尾节点开始打印,而尾节点是后面进来的。即后面来的先打印,前面的后打印。这个就可以用栈来实现。

    public void printList(ListNode head) {/*if (head == null) {// 抛异常}*/// 创建一个栈Stack<Integer> stack = new Stack<>();// 遍历链表,把链表的节点放到栈中while (head != null) {stack.push(head.val);head = head.next;}// 开始用栈来打印while (!stack.empty()) {System.out.print(stack.pop()+" ");}}

栈的相关刷题 

20. 有效的括号

给定一个只包括 '('')''{''}''['']' 的字符串 s ,判断字符串是否有效。

有效字符串需满足:

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1:

输入:s = "()"
输出:true

示例 2:

输入:s = "()[]{}"
输出:true

示例 3:

输入:s = "(]"
输出:false

提示:

  • 1 <= s.length <= 104
  • s 仅由括号 '()[]{}' 组成

括号不匹配有三种情况:

1、左括号比右括号多

2、右括号比左括号多

3、左右括号不匹配 

当我们去遍历这个字符串时,会发现一个规律:后遇到的左括号 会比 前遇到的左括号 先匹配。

思路: 先遇到的左括号储存到栈中,直至遇到了右括号,再将栈顶元素拿出来和这个右括号进行匹配,看看是否成功。 成功就继续往后走,失败则返回false。直至遍历完成或者栈为空(右括号多于左括号)。

class Solution {public boolean isValid(String s) {// 创建一个栈Stack<Character>  stack = new Stack<>();// 遍历字符串for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);// 如果遇到左括号就入栈,如果遇到右括号就出栈if (ch == '(' || ch == '{' || ch == '[') {stack.push(ch);}else {// 出栈匹配// 判断栈是否为空if (stack.empty()) {return false;} else {// 开始匹配char x = stack.pop();// 如果匹配说明符合要求,继续往后走if (x == '(' && ch == ')') {continue;} else if (x == '[' && ch == ']') {continue;} else if (x == '{' && ch == '}') {continue;} else {return false;} }}}// 判断栈是否为空if (stack.empty()) {// 栈为空说明全部匹配成功了return true;} else {// 还有括号没有匹配return false;} }
}

150. 逆波兰表达式求值

逆波兰表达式的介绍

给你一个字符串数组 tokens ,表示一个根据逆波兰表示法表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意:

  • 有效的算符为 '+''-''*' 和 '/' 。
  • 每个操作数(运算对象)都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1:

输入:tokens = ["2","1","+","3","*"]
输出:9
解释:该算式转化为常见的中缀算术表达式为:((2 + 1) * 3) = 9

示例 2:

输入:tokens = ["4","13","5","/","+"]
输出:6
解释:该算式转化为常见的中缀算术表达式为:(4 + (13 / 5)) = 6

示例 3:

输入:tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出:22
解释:该算式转化为常见的中缀算术表达式为:((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示:

  • 1 <= tokens.length <= 104
  • tokens[i] 是一个算符("+""-""*" 或 "/"),或是在范围 [-200, 200] 内的一个整数

逆波兰表达式(也称为后缀表达式)的计算通常与栈密切相关,因为栈能够非常自然地处理这种后进先出的操作顺序。不过,理论上讲,不使用栈也可以实现逆波兰表达式的计算,但可能需要更复杂的逻辑和额外的数据结构来模拟栈的功能。

思路:用栈来实现逆波兰表达式。遍历字符串数组,当遇到数字,则入栈;遇到运算符,则将栈顶的元素弹出作为右操作数,再将栈顶的元素弹出作为左操作数,计算完的值再入栈。

class Solution {public int evalRPN(String[] tokens) {Stack<String> stack = new Stack<>();// 遍历字符串数组for (int i = 0; i < tokens.length; i++) {// 判断这个字符串是否为数字// 数字难判断,但运算符很简单,因此可以转换角度来判断运算符if (!isOperator(tokens[i])) {// 是数字就入栈stack.push(tokens[i]);} else {// 开始运算int y = Integer.parseInt(stack.pop()); // 右操作数int x = Integer.parseInt(stack.pop()); // 左操作数 int result = 0;switch (tokens[i]) {case "+" :result = x+y;break;case "-" :result = x-y;break;case "*" :result = x*y;break;case "/" :result = x/y;break;}// 运算完的结果返回到栈中Integer j = result;stack.push(j.toString());}}// 返回栈中最后剩余的元素return Integer.parseInt(stack.pop());}private boolean isOperator(String s) {// 如果不是+、-、*、/,那就是数字字符return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");}
}

注意:我们平常写的运算表达式是属于中缀表达式,即运算符在两个运算数的中间位置,还有前缀表达式和后缀表达式。我们这里的逆波兰表达式就是后缀表达式,即运算符在两个运算数的后面,而前缀表达式就是在两个运算数的前面,也称为波兰表达式。

下面是中缀表达式转后缀表达式的详细过程:

9+(3-1) * 3+8 / 2,这个就是我们平常写的表达式。

转换成后缀表达式:
1、将所有的运算符与运算数之间加上()。即:((9+((3-1) * 3))+(8 / 2))
2、将所有的运算符提到本级括号的外边去。即:((9((3 1)-  3)*)+(8 2) / )+
3、最后将所有的括号全部去掉,就是后缀表达式。即:9 3 1 -  3 * + 8 2 / +

按照栈的特点去计算这个表达式的过程如下: 

牛客网——JZ31 栈的压入、弹出序列

描述

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例1

输入:

[1,2,3,4,5],[4,5,3,2,1]

返回值:

true

说明:

可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
这样的顺序得到[4,5,3,2,1]这个序列,返回true      

示例2

输入:

[1,2,3,4,5],[4,3,5,1,2]

返回值:

false

说明:

由于是[1,2,3,4,5]的压入顺序,[4,3,5,1,2]的弹出顺序,要求4,3,5必须在1,2前压入,且1,2不能弹出,但是这样压入的顺序,1又不能在2之前弹出,所以无法形成的,返回false   

思路:模拟第一个数组入栈出栈时的样子,与第二个数组对比,看结果是否一致。

public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;// 将第一个数组入栈,与第二个数组进行对比,看是否一致for (int i = 0; i < pushV.length; i++) {int x = stack.push(pushV[i]);if (x != popV[j]) {continue;} else {// 一致就继续往后比较,直至栈为空while (!stack.empty()) {if (stack.peek() == popV[j]) {stack.pop();j++;} else {break;}}} }if (stack.empty()) {return true;}return false;}

155. 最小栈

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

  • MinStack() 初始化堆栈对象。
  • void push(int val) 将元素val推入堆栈。
  • void pop() 删除堆栈顶部的元素。
  • int top() 获取堆栈顶部的元素。
  • int getMin() 获取堆栈中的最小元素。

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]输出:
[null,null,null,null,-3,null,0,-2]解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

  • -231 <= val <= 231 - 1
  • poptop 和 getMin 操作总是在 非空栈 上调用
  • pushpoptop, and getMin最多被调用 3 * 104 次

思路:既想要保持原数据不变,又要时刻维护最小数据,一个栈肯定是做不到的,要两个栈,一个普通栈,来存储元素,一个最小栈,来维护最小元素。

class MinStack {Stack<Integer> stack; // 普通栈Stack<Integer> minStack; // 最小栈public MinStack() {stack = new Stack<>(); // 普通栈minStack = new Stack<>(); // 最小栈}public void push(int val) {// 首先得判断这个最小栈中是否有元素。// 如果啥也没有,那么第一个元素肯定是要入栈的// 因为第一个元素肯定既是最大的,也是最小的if (minStack.empty()) {minStack.push(val);} else {if (minStack.peek() >= val) {minStack.push(val);}}// 普通栈就无需判断stack.push(val);}public void pop() {// 这里虽然删除的是普通栈的栈顶元素,// 但是如果普通栈的栈顶元素和最小栈一样,// 那么两者都得删除// 注意:这里的比较要用 equals,下面有解释if (stack.peek().equals(minStack.peek())) {stack.pop();minStack.pop();} else {stack.pop();}}public int top() {// 这里拿的是普通栈的栈顶元素return stack.peek();}public int getMin() {// 这里拿的是最小栈的栈顶元素return minStack.peek();}
}

注意:

1、这里题目明确的说了   poptop 和 getMin 操作总是在 非空栈 上调用 。

2、这里的比较之所以要用 equals() 方法,是因为当 LeetCode 给的测试用例不在 -128~127 之间时,会分配两个不同的对象。如果我们用 == 去比较的话,肯定是 false ,因此就只有两种解决方法:1、用 equals() 方法进行比较;2、将一方进行拆包的操作之后,再去比较两者之间的关系。

下面这篇文章就讲述了 第二点中的来源:同一个数字,但不同的对象

以上就是关于栈的经典题型了。总体难度虽然用栈来解决不是很大,但是要想到用栈的知识去解决,还是挺难的。所以栈的基本知识不能,但做题想到用栈解决就很难了。

好啦!本期  数据结构之栈  的学习之旅就到此结束了!相信通过这篇文章的学习,你对栈的了解将会更进一步!我们下一期再一起学习吧!

这篇关于数据结构之探索“栈”的奥秘的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075023

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

pip install jupyterlab失败的原因问题及探索

《pipinstalljupyterlab失败的原因问题及探索》在学习Yolo模型时,尝试安装JupyterLab但遇到错误,错误提示缺少Rust和Cargo编译环境,因为pywinpty包需要它... 目录背景问题解决方案总结背景最近在学习Yolo模型,然后其中要下载jupyter(有点LSVmu像一个

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

深入探索协同过滤:从原理到推荐模块案例

文章目录 前言一、协同过滤1. 基于用户的协同过滤(UserCF)2. 基于物品的协同过滤(ItemCF)3. 相似度计算方法 二、相似度计算方法1. 欧氏距离2. 皮尔逊相关系数3. 杰卡德相似系数4. 余弦相似度 三、推荐模块案例1.基于文章的协同过滤推荐功能2.基于用户的协同过滤推荐功能 前言     在信息过载的时代,推荐系统成为连接用户与内容的桥梁。本文聚焦于

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出

AI(文生语音)-TTS 技术线路探索学习:从拼接式参数化方法到Tacotron端到端输出 在数字化时代,文本到语音(Text-to-Speech, TTS)技术已成为人机交互的关键桥梁,无论是为视障人士提供辅助阅读,还是为智能助手注入声音的灵魂,TTS 技术都扮演着至关重要的角色。从最初的拼接式方法到参数化技术,再到现今的深度学习解决方案,TTS 技术经历了一段长足的进步。这篇文章将带您穿越时

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

轻松录制每一刻:探索2024年免费高清录屏应用

你不会还在用一些社交工具来录屏吧?现在的市面上有不少免费录屏的软件了。别看如软件是免费的,它的功能比起社交工具的录屏功能来说全面的多。这次我就分享几款我用过的录屏工具。 1.福晰录屏大师 链接直达:https://www.foxitsoftware.cn/REC/  这个软件的操作方式非常简单,打开软件之后从界面设计就能看出来这个软件操作的便捷性。界面的设计简单明了基本一打眼你就会轻松驾驭啦

深入探索嵌入式 Linux

摘要:本文深入探究嵌入式 Linux。首先回顾其发展历程,从早期尝试到克服诸多困难逐渐成熟。接着阐述其体系结构,涵盖硬件、内核、文件系统和应用层。开发环境方面包括交叉编译工具链、调试工具和集成开发环境。在应用领域,广泛应用于消费电子、工业控制、汽车电子和智能家居等领域。关键技术有内核裁剪与优化、设备驱动程序开发、实时性增强和电源管理等。最后展望其未来发展趋势,如与物联网融合、人工智能应用、安全性与