Java数据结构——栈的应用

栈的作用

• • 1.4 栈的应用场景
  • • 1. 改变元素的序列
    • 2. 中缀表达式 转 后缀表达式
    • • 后缀表达式的运算
    • 3. 将递归转化为循环（比如：逆序打印链表 ）
    • • • 递归打印，判断条件（1. 头结点为空 2. 下一个节点为空）
        • 非递归打印，用栈，栈的元素是ListNode
    • 4. 括号匹配
    • • 1. 匹配 和 不匹配的 情况要想清楚，才能写代码
      • 2. 什么叫做匹配
      • 3. String s 遍历完 还需要判断 栈里是否还有元素
      • 答案
    • 5. 根据后续表达式求值
    • • 1. 栈的元素是 Integer
      • 2. 需要写一个函数，判断字符 具体是什么
      • • 具体判断是数字还是 运算符（当然是判断运算符的代码更少一点）
      • 3. num2 和 num1 接收出栈数字
      • 4. switch case
    • 6. 出栈入栈次序匹配
    • • 1. 方法：一个数组入栈 同时出栈数组进行判断
      • *****记住 栈中是 Integer元素，不能直接和int 进行 ==（用equal方法）
      • 不匹配的情况，就是两个数组都遍历完，但是栈中还有元素

1.4 栈的应用场景

1. 改变元素的序列

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）
   A: 1,4,3,2 B: 2,3,4,1 C: 3,1,4,2 D: 3,4,2,1
   2.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺 序是（ B）。
   A: 12345ABCDE B: EDCBA54321 C: ABCDE12345 D: 54321EDCBA

2. 中缀表达式 转 后缀表达式

1. 先把所有运算 用括号 括起来
2. 把运算符 移到 括号外
3. 删除括号

后缀表达式的运算

a b c * + d e * f + g * +

数字依次入栈
碰到符号，栈顶的出栈作为 右操作数
再次出栈 作为左操作数
结果再次入栈

3. 将递归转化为循环（比如：逆序打印链表 ）

递归打印，判断条件（1. 头结点为空 2. 下一个节点为空）

非递归打印，用栈，栈的元素是ListNode

    /*** 递归实现  单链表的逆序打印* @param head*/public void printList(ListNode head) {if(head == null) {return;}if(head.next == null) {System.out.print(head.val+" ");return;}printList(head.next);System.out.print(head.val+" ");}/*** 非递归实现* @param*/public void printList2() {Stack<ListNode> stack = new Stack<>();ListNode cur = head;while (cur != null) {stack.push(cur);cur = cur.next;}//while (!stack.empty()) {ListNode top = stack.pop();System.out.print(top.val+" ");}System.out.println();}

4. 括号匹配

原题链接

1. 匹配 和 不匹配的 情况要想清楚，才能写代码

匹配情况：

所以如果遍历到左括号，需要入栈
右括号：先判断栈里是否还有元素

2. 什么叫做匹配

 if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') 

3. String s 遍历完 还需要判断 栈里是否还有元素

        if(stack.empty()) {return true;}else{//左括号多return false;}

答案

    public boolean isValid(String s) {//时间复杂度O(n)  空间复杂度：O(n)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 {//说明ch里面   是右括号if(stack.empty()) {//右括号多！return false;}char top = stack.peek();if(ch == ')' && top == '(' || ch == ']' && top == '[' || ch == '}' && top == '{') {//只能说明 当前的字符是匹配的stack.pop();}else{//左右括号不匹配return false;}}}if(stack.empty()) {return true;}else{//左括号多return false;}}

5. 根据后续表达式求值

原题链接

1. 栈的元素是 Integer

2. 需要写一个函数，判断字符 具体是什么

具体判断是数字还是 运算符（当然是判断运算符的代码更少一点）

3. num2 和 num1 接收出栈数字

4. switch case

    public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(String x : tokens) {//不是加减乘法if(!isOperation(x)) {stack.push(Integer.parseInt(x));}else{int num2 = stack.pop();int num1 = stack.pop();switch(x) {case "+" :stack.push(num1+num2);break;case "-" :stack.push(num1-num2);break;case "*" :stack.push(num1*num2);break;case "/" :stack.push(num1/num2);break;}}}return stack.pop();}private boolean isOperation(String opera) {if(opera.equals("+") || opera.equals("-") || opera.equals("*") ||  opera.equals("/") ) {return true;}return false;}

6. 出栈入栈次序匹配

原题链接

1. 方法：一个数组入栈 同时出栈数组进行判断

*****记住 栈中是 Integer元素，不能直接和int 进行 ==（用equal方法）

不匹配的情况，就是两个数组都遍历完，但是栈中还有元素

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！