AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

栈和队列的相关应用（二）

2022-10-20 116
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 栈和队列的相关应用（二）
  • 逆波兰表达式求值（ 后缀表达式）
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

(a+b)*c-(a+b)/e的后缀表达式为：

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

思路：构造一个判断运算符的函数，然后判断为数字则入栈，遇到运算符则弹出两个元素进行相关操作，将运算得到的结果再次入栈，直至将最后的元素弹出栈即为最后的结果。

( ( 1 2 + ) ( 3 4 + ) * )

1,2先入栈，遇到运算符+即出栈，1,2相加得3入栈，3，4同理得7入栈，最后遇到 * ,3，7出栈相乘得结果为21

代码实现：

  public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
      //字符数组进行遍历
        for(String x : tokens){
            if(!isOperation(x)){
                //使用parseInt()函数将字符串转换为整型
                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 s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }else{
            return false;
        }
    }
  • 将递归转化为循环

如：逆序打印链表

  1. 递归实现逆序打印
 public void display(ListNode head){
        if(head == null){
            return;
        }
     //直到链表末尾，再归回去
        if(head.next == null){
            System.out.println(head.val+" ");
            return;
        }
        display(head.next);
        System.out.println(head.val+" ");
}
  1. 使用栈实现
public void display(ListNode head){
        if(head == null){
            return;
         }
        Stack<ListNode> stack  = new Stack<>();
        ListNode cur = head;
         while(cur!= null){
              stack.push(cur);
              cur = cur.next;
             }
        while(!stack.empty()){
            ListNode ret =   stack.pop();
            System.out.println(ret.val+" ");
        }
    }
利用栈先进后出的特性，将链表的节点都加入栈中，然后再依次出栈，并打印栈中节点的 val 的值，即实现了链表的逆序打印。

✅栈、虚拟机栈、栈帧有什么区别呢？

栈： 一种先进后出的数据结构

虚拟机栈：JVM中的一块内存空间

栈帧：再调用函数过程当中，在java 虚拟机栈上开辟的一块内存

  • 使用栈来实现队列

image-20221009161421102

思路：初始化两个空栈s1,s2 当实现入队操作时，即入栈 s1 即可，出栈时 如果s1不为空，将s1当中的元素进行出栈，并入栈到s2 中去，s2再进行出栈，即实现了队列先进先出的效果，当s1与s2 都为空时，则此队列为空。

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    
    public MyQueue() {
    s1 = new Stack<>();
    s2 = new Stack<>();
    }
    
    public void push(int x) {
       s1.push(x);
    }
    public int pop() {
       if(empty()){
           return -1;
       }
       if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
       }
       return s2.pop();
    } 
    
    public int peek() {
        if(empty()){
           return -1;
       }
       if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
       }
       return s2.peek();
    }
    
    public boolean empty() {
      return s1.empty()&&s2.empty();
    }
}
  • 使用队列来实现栈

image-20221009165219132

思路：初始化两个空队列 q1与q2，当q1 或者 q2为空时，入队,两者都为空时，入队q1;

当弹出元素时，将其余size -1 个元素全部转移到另一个队列当中，剩余的一个元素出队即可，注意要将非空队列长度提前储存；取队首元素时，将出队列 1中的最后一个元素储存临时变量当中，返回临时变量即可

class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
    public MyStack() {
      qu1 = new LinkedList<>();
      qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }
    
    public int pop() {
       if(empty()){
           return -1;
       }
       if(!qu1.isEmpty()){
           int size = qu1.size()-1;
           for(int i = 0;i <size;i++){
               qu2.offer(qu1.poll());
           }
           return qu1.poll();
       }else{
            int size = qu2.size()-1;
           for(int i = 0;i <size;i++){
               qu1.offer(qu2.poll());
           }
           return qu2.poll();
       }
    }
    
    public int top() {
      if(empty()){
           return -1;
       }
       if(!qu1.isEmpty()){
           int size = qu1.size();
           int ret = -1;
           for(int i = 0;i <size;i++){
               ret = qu1.poll();
               qu2.offer(ret);
           }
           return ret;
       }else{
            int size = qu2.size();
            int ret = -1;
           for(int i = 0;i <size;i++){
               ret = qu2.poll();
               qu1.offer(ret);
           }
           return ret;
       }
    }
    
    public boolean empty() {
      return qu1.isEmpty()&&qu2.isEmpty();
    }
}
  • 栈的压入、弹出序列匹配问题
 /**
     * 栈的次序匹配问题
     * 判断出栈入栈是否符合
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;//遍历popA数组
        for(int  i = 0;i < pushA.length;i++) {
            stack.push(pushA[i]);
//            i下标所指元素直接入栈，入栈之后判断j下标所指元素是否相同
            while(j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
//                如果是则出栈,j++
                stack.pop();
                j++;
            }
        }
//        如果此时栈为空，则满足，不为空则不满足
        return stack.empty();
    }
  • 括号匹配问题

image-20221011163030642

 /*
    * 括号匹配问题
    * */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length();i++) {
            char ch = s.charAt(i);
            //1. 判断是不是左括号
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.empty()) {
                    //2. 遇到了右括号 但是栈为空，此时不匹配！
                    return false;
                }
                char ch2 = stack.peek();
                //3。 此时 如果满足 这里面的任何一个匹配逻辑 都是匹配的
                if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        //4. 当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
        if(!stack.empty()) {
            return false;
        }
        return true;
    }
}
  • 逆波兰表达式求值（ 后缀表达式）
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

(a+b)*c-(a+b)/e的后缀表达式为：

(a+b)*c-(a+b)/e

→((a+b)*c)((a+b)/e)-

→((a+b)c*)((a+b)e/)-

→(ab+c*)(ab+e/)-

→ab+c*ab+e/-

思路：构造一个判断运算符的函数，然后判断为数字则入栈，遇到运算符则弹出两个元素进行相关操作，将运算得到的结果再次入栈，直至将最后的元素弹出栈即为最后的结果。

( ( 1 2 + ) ( 3 4 + ) * )

1,2先入栈，遇到运算符+即出栈，1,2相加得3入栈，3，4同理得7入栈，最后遇到 * ,3，7出栈相乘得结果为21

代码实现：

  public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
      //字符数组进行遍历
        for(String x : tokens){
            if(!isOperation(x)){
                //使用parseInt()函数将字符串转换为整型
                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 s){
        if(s.equals("+")||s.equals("-")||s.equals("*")||s.equals("/")){
            return true;
        }else{
            return false;
        }
    }
  • 将递归转化为循环

如：逆序打印链表

  1. 递归实现逆序打印
 public void display(ListNode head){
        if(head == null){
            return;
        }
     //直到链表末尾，再归回去
        if(head.next == null){
            System.out.println(head.val+" ");
            return;
        }
        display(head.next);
        System.out.println(head.val+" ");
}
  1. 使用栈实现
public void display(ListNode head){
        if(head == null){
            return;
         }
        Stack<ListNode> stack  = new Stack<>();
        ListNode cur = head;
         while(cur!= null){
              stack.push(cur);
              cur = cur.next;
             }
        while(!stack.empty()){
            ListNode ret =   stack.pop();
            System.out.println(ret.val+" ");
        }
    }
利用栈先进后出的特性，将链表的节点都加入栈中，然后再依次出栈，并打印栈中节点的 val 的值，即实现了链表的逆序打印。

✅栈、虚拟机栈、栈帧有什么区别呢？

栈： 一种先进后出的数据结构

虚拟机栈：JVM中的一块内存空间

栈帧：再调用函数过程当中，在java 虚拟机栈上开辟的一块内存

  • 使用栈来实现队列

image-20221009161421102

思路：初始化两个空栈s1,s2 当实现入队操作时，即入栈 s1 即可，出栈时 如果s1不为空，将s1当中的元素进行出栈，并入栈到s2 中去，s2再进行出栈，即实现了队列先进先出的效果，当s1与s2 都为空时，则此队列为空。

class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;
    
    public MyQueue() {
    s1 = new Stack<>();
    s2 = new Stack<>();
    }
    
    public void push(int x) {
       s1.push(x);
    }
    public int pop() {
       if(empty()){
           return -1;
       }
       if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
       }
       return s2.pop();
    } 
    
    public int peek() {
        if(empty()){
           return -1;
       }
       if(s2.empty()){
          while(!s1.empty()){
              s2.push(s1.pop());
          }
       }
       return s2.peek();
    }
    
    public boolean empty() {
      return s1.empty()&&s2.empty();
    }
}
  • 使用队列来实现栈

image-20221009165219132

思路：初始化两个空队列 q1与q2，当q1 或者 q2为空时，入队,两者都为空时，入队q1;

当弹出元素时，将其余size -1 个元素全部转移到另一个队列当中，剩余的一个元素出队即可，注意要将非空队列长度提前储存；取队首元素时，将出队列 1中的最后一个元素储存临时变量当中，返回临时变量即可

class MyStack {

    private Queue<Integer> qu1;
    private Queue<Integer> qu2;
    public MyStack() {
      qu1 = new LinkedList<>();
      qu2 = new LinkedList<>();
    }

    public void push(int x) {
        if(!qu1.isEmpty()){
            qu1.offer(x);
        }else if(!qu2.isEmpty()){
            qu2.offer(x);
        }else{
            qu1.offer(x);
        }
    }
    
    public int pop() {
       if(empty()){
           return -1;
       }
       if(!qu1.isEmpty()){
           int size = qu1.size()-1;
           for(int i = 0;i <size;i++){
               qu2.offer(qu1.poll());
           }
           return qu1.poll();
       }else{
            int size = qu2.size()-1;
           for(int i = 0;i <size;i++){
               qu1.offer(qu2.poll());
           }
           return qu2.poll();
       }
    }
    
    public int top() {
      if(empty()){
           return -1;
       }
       if(!qu1.isEmpty()){
           int size = qu1.size();
           int ret = -1;
           for(int i = 0;i <size;i++){
               ret = qu1.poll();
               qu2.offer(ret);
           }
           return ret;
       }else{
            int size = qu2.size();
            int ret = -1;
           for(int i = 0;i <size;i++){
               ret = qu2.poll();
               qu1.offer(ret);
           }
           return ret;
       }
    }
    
    public boolean empty() {
      return qu1.isEmpty()&&qu2.isEmpty();
    }
}
  • 栈的压入、弹出序列匹配问题
 /**
     * 栈的次序匹配问题
     * 判断出栈入栈是否符合
     * @param pushA
     * @param popA
     * @return
     */
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;//遍历popA数组
        for(int  i = 0;i < pushA.length;i++) {
            stack.push(pushA[i]);
//            i下标所指元素直接入栈，入栈之后判断j下标所指元素是否相同
            while(j < popA.length && !stack.empty() && stack.peek() == popA[j]) {
//                如果是则出栈,j++
                stack.pop();
                j++;
            }
        }
//        如果此时栈为空，则满足，不为空则不满足
        return stack.empty();
    }
  • 括号匹配问题

image-20221011163030642

 /*
    * 括号匹配问题
    * */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length();i++) {
            char ch = s.charAt(i);
            //1. 判断是不是左括号
            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            }else {
                if(stack.empty()) {
                    //2. 遇到了右括号 但是栈为空，此时不匹配！
                    return false;
                }
                char ch2 = stack.peek();
                //3。 此时 如果满足 这里面的任何一个匹配逻辑 都是匹配的
                if(ch2 == '[' && ch == ']' || ch2 == '(' && ch == ')' || ch2 == '{' && ch == '}') {
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        //4. 当字符串遍历完成了，但是栈不为空，说明左括号还在栈当中没有匹配完成
        if(!stack.empty()) {
            return false;
        }
        return true;
    }
}
文章标签：
云数据库 ClickHouse
云虚拟主机
Java
关键词：
栈数据结构
队列数据结构
栈队列数据结构
应用数据结构
栈应用数据结构
署前街的少年
目录
相关文章
2的n次方_
|
5天前
|
存储 机器学习/深度学习
【数据结构】二叉树全攻略，从实现到应用详解
本文介绍了树形结构及其重要类型——二叉树。树由若干节点组成，具有层次关系。二叉树每个节点最多有两个子树，分为左子树和右子树。文中详细描述了二叉树的不同类型，如完全二叉树、满二叉树、平衡二叉树及搜索二叉树，并阐述了二叉树的基本性质与存储方式。此外，还介绍了二叉树的实现方法，包括节点定义、遍历方式（前序、中序、后序、层序遍历），并提供了多个示例代码，帮助理解二叉树的基本操作。
2的n次方_
34 13
【数据结构】二叉树全攻略，从实现到应用详解
2的n次方_
|
6天前
|
存储 Java 索引
【数据结构】链表从实现到应用，保姆级攻略
本文详细介绍了链表这一重要数据结构。链表与数组不同，其元素在内存中非连续分布，通过指针连接。Java中链表常用于需动态添加或删除元素的场景。文章首先解释了单向链表的基本概念，包括节点定义及各种操作如插入、删除等的实现方法。随后介绍了双向链表，说明了其拥有前后两个指针的特点，并展示了相关操作的代码实现。最后，对比了ArrayList与LinkedList的不同之处，包括它们底层实现、时间复杂度以及适用场景等方面。
2的n次方_
28 10
【数据结构】链表从实现到应用，保姆级攻略
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 栈与队列的详解附完整代码
栈是一种仅允许在一端进行插入和删除操作的线性表，常用于解决括号匹配、函数调用等问题。栈分为顺序栈和链栈，顺序栈使用数组存储，链栈基于单链表实现。栈的主要操作包括初始化、销毁、入栈、出栈等。栈的应用广泛，如表达式求值、递归等场景。栈的顺序存储结构由数组和栈顶指针构成，链栈则基于单链表的头插法实现。
小徐在进步
14 3
小徐在进步
|
2天前
|
存储 C语言
数据结构基础详解(C语言): 树与二叉树的应用_哈夫曼树与哈夫曼曼编码_并查集_二叉排序树_平衡二叉树
本文详细介绍了树与二叉树的应用，涵盖哈夫曼树与哈夫曼编码、并查集以及二叉排序树等内容。首先讲解了哈夫曼树的构造方法及其在数据压缩中的应用；接着介绍了并查集的基本概念、存储结构及优化方法；随后探讨了二叉排序树的定义、查找、插入和删除操作；最后阐述了平衡二叉树的概念及其在保证树平衡状态下的插入和删除操作。通过本文，读者可以全面了解树与二叉树在实际问题中的应用技巧和优化策略。
小徐在进步
10 2
2的n次方_
|
3天前
|
Java
【数据结构】栈和队列的深度探索，从实现到应用详解
本文介绍了栈和队列这两种数据结构。栈是一种后进先出（LIFO）的数据结构，元素只能从栈顶进行插入和删除。栈的基本操作包括压栈、出栈、获取栈顶元素、判断是否为空及获取栈的大小。栈可以通过数组或链表实现，并可用于将递归转化为循环。队列则是一种先进先出（FIFO）的数据结构，元素只能从队尾插入，从队首移除。队列的基本操作包括入队、出队、获取队首元素、判断是否为空及获取队列大小。队列可通过双向链表或数组实现。此外，双端队列（Deque）支持两端插入和删除元素，提供了更丰富的操作。
2的n次方_
10 0
【数据结构】栈和队列的深度探索，从实现到应用详解
可能只会写BUG
|
8天前
|
Linux C++ Windows
栈对象返回的问题 RVO / NRVO
具名返回值优化（(Name)Return Value Optimization，(N)RVO）是一种优化机制，在函数返回对象时，通过减少临时对象的构造、复制构造及析构调用次数来降低开销。在C++中，通过直接在返回位置构造对象并利用隐藏参数传递地址，可避免不必要的复制操作。然而，Windows和Linux上的RVO与NRVO实现有所不同，且接收栈对象的方式也会影响优化效果。
可能只会写BUG
18 2
1387503158665997
|
10天前
crash —— 获取内核地址布局、页大小、以及栈布局
crash —— 获取内核地址布局、页大小、以及栈布局
1387503158665997
14 0
Star时光
|
10天前
|
存储 程序员 C语言
堆和栈之间有什么区别
【9月更文挑战第1天】堆和栈之间有什么区别
Star时光
77 0
睡觉待开机
|
28天前
|
算法 C语言 C++
【practise】栈的压入和弹出序列
【practise】栈的压入和弹出序列
睡觉待开机
17 0
服务端技术栈
|
26天前
栈的几个经典应用，真的绝了
文章总结了栈的几个经典应用场景，包括使用两个栈来实现队列的功能以及利用栈进行对称匹配，并通过LeetCode上的题目示例展示了栈在实际问题中的应用。
服务端技术栈
37 1
栈的几个经典应用，真的绝了