【Java--数据结构】栈的应用

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

目录

将递归转化为循环

逆波兰表达式

有效的括号

栈得压入、弹出系列

最小栈

---

将递归转化为循环

把递归代码实现为非递归代码

比如：逆序打印链表

// 递归方式
void printList(Node head){
    if(null != head){
        printList(head.next);
        System.out.print(head.val + " ");
   }
}
 
// 循环方式
void printList(Node head){
    if(null == head){
        return;
   }
    
    Stack s = new Stack();
    // 将链表中的结点保存在栈中
    Node cur = head;
    while(null != cur){
        s.push(cur);
        cur = cur.next;
   }

逆波兰表达式

也叫后缀表达式（运算符在操作数的后面）,好处是：忽略运算符的优先级

我们平时运算加减乘除的式子其实是 中缀表达式 

比如式子a+b*c+(d*e+f)*g转成逆波兰表达式 abc*+de*f+g*+

逆波兰表达式的运算规则：

1. 将操作数压入栈中
2. 遇到运算符弹出操作数（分别作为右操作数和左操作数）计算
3. 将计算的结果压入栈中

比如式子1+2*3+（4*5+6）*7

逆波兰表达式1 2 3*4 5*6 +7 *+

• 将1 2 3压入栈内，
• 遇到*，取出2和3，计算2*3得6
• 将6压入栈
• 又遇到+，取出6和1，计算6+1得7

  ……

  

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

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

  ​

  class Solution {
      public int evalRPN(String[] tokens) {
          Stack stack=new Stack();
          for(int i=0;i