【数据结构初阶】第五节.栈的详讲

这篇具有很好参考价值的文章主要介绍了【数据结构初阶】第五节.栈的详讲。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

文章目录

前言

一、栈的基本认识

二、栈模拟实现: 

三、栈的实战演练

3.1 有效的括号

3.2 逆波兰表达式

3.3 栈的压入、弹出序列

总结


前言

上一节内容我们学习了链表的有关内容,今天我们将进行栈的学习;栈也是一种十分重要的数据结构;就让我们一起进入到今天的学习当中吧!!!!!!


提示:以下是本篇文章正文内容,下面案例可供参考

一、栈的基本认识

同链表和顺序表一样,栈也是用来存储逻辑关系为 "一对一" 数据线性数据结构,如图所示。

【数据结构初阶】第五节.栈的详讲

从图 中我们看到,栈存储结构与之前所学的链表和顺序表有所差异,这缘于栈对数据 "存" 和 "取" 的过程有特殊的要求: 

1.栈只能从表的一端存取数据,另一端是封闭的;
2.在栈中,无论是存数据还是取数据,都必须遵循"先进后出"的原则,即最先进栈的元素最后出栈。拿图中的栈来说,从图中数据的存储状态可判断出,元素 1 是最先进的栈。因此,当需要从栈中取出元素 1 时,根据"先进后出"的原则,需提前将元素 3 和元素 2 从栈中取出,然后才能成功取出元素 1。

因此,我们可以给栈下一个定义,即栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。

通常,栈的开口端被称为栈顶;相应地,封口端被称为栈底。因此,栈顶元素指的就是距离栈顶最近的元素,同理,栈底元素指的是位于栈最底部的元素;

【数据结构初阶】第五节.栈的详讲

那么了解了栈的基本结构,在栈中我们如何实现元素的增加和删除呢? 

从上面的图我们不难发现,在栈中我们无论是放元素还是取元素,顺序都是从上到下,即都是从栈顶开始、到栈底结束,所以增加和删除的也是通过栈顶来实现的,即我们删除一个元素就是把当前栈顶的元素给挪开,让该元素下面的元素变成新的栈顶;我们增加一个元素就是让新增加的元素变成我们新的栈顶;

  1. 我们存放数据的过程就叫做入栈
  2. 我们取出数据的过程就叫做出栈

【数据结构初阶】第五节.栈的详讲

二、栈模拟实现: 

别看说了这么多其实栈的实现很简单,不信你看

public class MyStack {
    public int[] elem;
    public int usedSize;
    MyStack() { // 栈的初始化
        elem = new int[]{1, 2, 3, 4};
        usedSize = elem.length;
    }
    public void push(int val) { // 默认相当于是尾插, 来入栈
        elem[usedSize] = val;
        ++usedSize;
    }
    public void pop() { // 出栈
        if (empty()) {
            System.out.println("当前栈为空,你的操作不合法!");
            return;
        }
        --usedSize;
    }
    // 判断栈是否为空, 空则返回true,非空则返回false
    public boolean empty() {
        if (usedSize == 0) return true;
        return false;
    }
    // 获取栈中元素的个数
    public int size() {
        return usedSize;
    }
    // 顺序打印当前栈中的所有元素
    public void printMyStack(){
        for (int i = 0; i < usedSize; i++) {
            System.out.print(elem[i] + " ");
        }
        System.out.println();
    }
}

运行结果如图所示 :

【数据结构初阶】第五节.栈的详讲

【数据结构初阶】第五节.栈的详讲

三、栈的实战演练

3.1 有效的括号

题目链接 

有效的括号——力扣

【数据结构初阶】第五节.栈的详讲

本题的思路:

只要所给字符串的左右两边是对称的——就合法;

即字符串中左右括号的个数是相当的,注意这里所说的左右括号各有三种类型——"{}、[]、()"

我们不妨用栈来储存左括号,借助栈来看看左右括号的个数是否相等;

再对该字符串进行遍历的过程,如果我们的右边的元素和储存在栈中的左括号相对于,则把当前栈中的所匹配的元素出栈,继续对字符串遍历;

🍑当字符串遍历完后,如果栈中的元素刚好为空,则说明该字符串有效;

🍑如果字符串遍历完后,栈中依然有元素,说明左括号多;

🍑如果字符串还没遍历完,栈就为空了,说明右括号多;

 代码分析:
 

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; // 当然如果右括号所对应的右边元素为空,自然是不匹配
                // 注意此时我们并没有取出栈中的元素(因为还不确定这对括号是否匹配),只是显示当前的堆栈元素
                char top = stack.peek();
                if ( (top == '{' && ch == '}') || (top == '[' && ch == ']') || (top == '(' && ch == ')') ) {
                    stack.pop();
                }
                else{
                    return false; // 说明此时右边的元素和栈中所存放的左边的元素不匹配
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }
}

3.2 逆波兰表达式

 原题链接

【数据结构初阶】第五节.栈的详讲

对于这个题目,首先我们需要先补充一点知识;

中缀表达式转后缀表达式

比如(1 +(2 * 3))+ ((4 * 5) + 6)*  7)这样的中缀表达式要变成像123*+45*6+7*+这样的后缀表达式。

🍑步骤如下:

1、首先将中缀表达式的各个括号对都用不同的颜色清晰的标出来,像这样:
 

 2、然后把运算符符移动到相邻的最近的括号对的后边,(先移动里面的运算符,再移动外面的运算符,然后从前往后的进行移动)

比如对于(1 +(2 * 3))就是先把*号移动——》(1 +(23)*)

然后再是+号——》(1(23)*)+  

3、 最后再把括号去掉才变成了123*+45*6+7*+这种形式

总结:

1)先按照运算符的优先级对中缀表达式加括号,变成( ( a+(b*c) ) + ( ((d*e)+f) *g ) )

2)将运算符移到括号的后面,变成((a(bc)*)+(((de)*f)+g)*)+

3)去掉括号,得到abc*+de*f+g*+


后缀表达式求值:

那么如何像这种后缀表达式123*+45*6+7*+如何进行求值你呢?这就要借助我们的栈了。

1.建立一个空栈 stack。
2.遍历后缀表达式(此后将遍历到的字符称为 s)。
3.当 s 为数字时,将其压入 stack 栈。
4.当 s 为运算符时,弹出 stack 栈顶和次栈顶的两个数字,并将两个数字按照运算符 s 进行运算,然后将运算结果压入stack 栈 。
5.当遍历结束时,存留在栈 stack 中还剩下唯一一个数字,该数字便是运算结果。

下面用例子来解释一下:

举例说明:

假定待求值的后缀表达式为:6  5  2  3  + 8 * + 3  +  *,则其求值过程如下:

1)遍历表达式,遇到的数字首先放入栈中,此时栈如下所示:

【数据结构初阶】第五节.栈的详讲

 2)然后遇到了  +  这个运算符,那么就把当前的栈顶和次栈顶取出来,进行加法运算,但要注意运算时候次栈顶再前面,栈顶再后面 ,即次栈顶+栈顶的顺序来进行运算(其他的减乘除也都是按照次栈顶、栈顶这样的前后位置来进行运算的) 

3)再把刚才的运算结果5放到栈中,成为新的栈顶;

【数据结构初阶】第五节.栈的详讲

4)然后又继续向后走,把接下来的数字8入栈,成为栈顶  ;

【数据结构初阶】第五节.栈的详讲

5)遇到  * 号后,取出栈顶和次栈顶进行 * 的运算——》5,把新的运算结果作为新的栈顶放到栈中 ;

6)这样当遍历结束时,存留在栈 stack 中还剩下唯一一个数字,该数字便是运算结果;

代码分析:

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();
        for (int i = 0; i < tokens.length; ++i) {
            String s = tokens[i]; 
            if (charge(s)) { // 如果是运算符,则进行运算操作
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch(s) { // 对从栈顶和次栈顶取出的元素进行运算
                    case "+":
                        stack.push(num2 + num1); // 把运算的结果放回栈中
                        break;
                    case "-":
                        stack.push(num2 - num1);
                        break;
                    case "*":
                        stack.push(num2 * num1);
                        break;
                    case "/":
                        stack.push(num2 / num1);
                        break;        
                }
            }
            else { // 不是运算符,就存在栈中
                stack.push(Integer.parseInt(s)); // 因为我们的栈中储存的是字符,所以要用Integer中的parseInt进行类型转换
            }
        }
        return(stack.pop()); // 栈中最后一个元素给出栈
        
    }
    public boolean charge(String str) { // 判断当前字符串是否是有效的运算符
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }
}

3.3 栈的压入、弹出序列

原题链接:

栈的压入和弹出——牛客 

【数据结构初阶】第五节.栈的详讲

详细的题解和思路可以看看这篇文章:

转载:栈的压入和弹出题解——牛客  

代码解析:
 

import java.util.*;
 
public class Solution {
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        int j = 0;
        // 用到了一个辅助栈
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]); // 把
            while (!stack.empty() && j < popA.length && stack.peek() == popA[j]) {
                stack.pop();
                ++j;
            }
        }
        if (stack.empty()) {
            return true;
        }
        return false;
    }
    
 
}


总结

今天的内容就介绍到这里,我们一下节内容再见!!!

【数据结构初阶】第五节.栈的详讲

 文章来源地址https://www.toymoban.com/news/detail-422393.html

到了这里,关于【数据结构初阶】第五节.栈的详讲的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构 栈的概念及栈的实现

    目录 1.栈的概念及结构 2.栈的实现  2.1  初始化栈 2.2 入栈  2.3 出栈  2.4 获取栈顶元素 2.5 获取栈中有效元素个数   2.6  检测栈是否为空,如果为空返回非零结果,如果不为空返回0 2.7 销毁栈  3. 完整代码 test.c  Stack.h Stack.c   栈(后进先出,先进后出) : 一种 特殊

    2024年01月21日
    浏览(39)
  • 【数据结构】:栈的实现

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

    2024年02月07日
    浏览(24)
  • 【数据结构】栈的详解

    ☃️个人主页:fighting小泽 🌸作者简介:目前正在学习C语言和数据结构 🌼博客专栏:数据结构 🏵️欢迎关注:评论👊🏻点赞👍🏻留言💪🏻 栈:一种特殊的 线性表 ,其只允许在 固定的一端 进行 插入和删除元素 操作。进行数据插入和删除操作的一端称为 栈顶 ,另一

    2024年02月05日
    浏览(48)
  • 【数据结构】栈的实现

    栈:是一种受限制的线性表,即只能在尾部进行插入、删除的线性表,而且是一种先进后出的数据结构。尾部这一端又叫做栈顶,另一端叫做栈底。 入栈:向一个栈内插入元素叫做入栈或压栈,它把新元素放到栈顶元素的上面,是它成为新的栈顶元素。 出栈:在栈内删除元

    2024年02月01日
    浏览(27)
  • 数据结构-栈的实现

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

    2024年02月05日
    浏览(36)
  • 数据结构---栈的实现

    前言 一、什么是栈? 二、 栈的实现 1. 栈的结构 2. 栈的接口实现过程 总结 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是

    2024年02月02日
    浏览(57)
  • 【数据结构—栈的实现(数组栈)】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、栈 1.1栈的概念及结构 二、栈的实现 2.1头文件的实现—Stack.h 2.2源文件的实现—Stack.c 2.3源文件的测试—test.c 三、栈的实际测试数据展示 3.1正常的出入栈展示: 3.2进栈同时也在出栈的

    2024年02月04日
    浏览(36)
  • 数据结构:线性表(栈的实现)

    栈(Stack)是只允许在一端进行插入或删除操作的线性表.首先栈是一种线性表,但限定这种线性表只能在某一端进行插入和删除操作. 进行 数据插入和删除操作的一端 叫 栈顶 ,另一端称为 栈底 . 栈中的元素遵循 后进先出 LIFO(Last In First Out)的原则 压栈 :栈的插入操作叫做进栈/压栈

    2024年02月09日
    浏览(29)
  • 【数据结构与算法】栈的讲解

    栈(stack)是限定仅在表尾进行插入和删除操作的线性表。 我们把 允许插入和删除的一段称为栈顶(top) , 另一端称为栈底 , 不含任何数据元素的栈称为空栈 。 栈又称为后进先出的线性表 。 进一步理解栈,栈首先他是一个 线性表 ,所以栈元素具有前驱后继关系。 栈的插入操

    2023年04月08日
    浏览(27)
  • 【算法与数据结构】栈的实现详解

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

    2024年03月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包