栈的几个经典应用,真的绝了

简介: 文章总结了栈的几个经典应用场景,包括使用两个栈来实现队列的功能以及利用栈进行对称匹配,并通过LeetCode上的题目示例展示了栈在实际问题中的应用。

一、我们了解的栈

自从最开始接触栈之后,我就知道了栈是一个先进后出数据结构,一直到现在也没忘记这个特点。也就是说访问栈里面的元素顺序是从最近插入的开始访问。但是栈的使用场景其实了解的不多,本文就来总结下栈有哪些经典使用场景吧。

截屏2024-01-25 22.52.31.png

二、栈的经典应用

1、栈其实可以用来实现队列

栈的特点是先进后出,而队列的特点是先进先出

如果我们使用两个栈,可以实现队列的功能,双栈实现队列。

截屏2024-01-25 23.01.29.png

如上图,我们通过将第一个栈的数据导入第二个栈,再通过第二个栈出栈,实现队列先进先出的特性。

image.png

2、栈可以用于对称匹配,如匹配有效的括号有效的算式表达式

比如有一串括号字符串,([{}]),我们需要判断括号是否完全匹配。

截屏2024-01-25 23.10.35.png

通过将一边的括号入栈,遇到了对边的括号,需要出栈匹配。

我们可以发现,}])和出栈的括号顺序可以匹配,如果括号完全匹配,那么最终栈里面没有一个元素。

三、栈应用实战

leetcode20. 有效的括号

class Solution {
   
   
    public boolean isValid(String s) {
   
   
        int n = s.length();
        //存储关系
        Map<Character, Character> map = new HashMap<Character, Character>() {
   
   {
   
   
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < n; i++) {
   
   
            char ch = s.charAt(i);
            //是右边的括号
            if (map.containsKey(ch)) {
   
   
                //栈顶没有匹配的左边括号
                if (stack.isEmpty() || stack.peek() != map.get(ch)) {
   
   
                    return false;
                }
                stack.pop();
            } else {
   
   
                //左边的括号,入栈
                stack.push(ch);
            }
        }
        //栈里如果还要括号,则不匹配
        return stack.isEmpty();
    }
}

leetcode232. 用栈实现队列

class MyQueue {
   
   

    Stack<Integer> stack1 = new Stack<>();
    Stack<Integer> stack2 = new Stack<>();

    public MyQueue() {
   
   

    }

    public void push(int x) {
   
   

        stack1.push(x);

    }

    public int pop() {
   
   

        if(!stack2.isEmpty()) {
   
   
            return stack2.pop();
        }

        while(!stack1.isEmpty()) {
   
   
            stack2.push(stack1.pop());
        }

        if(!stack2.isEmpty()) {
   
   
            return stack2.pop();
        }
        return 0;
    }

    public int peek() {
   
   

        if(!stack2.isEmpty()) {
   
   
            return stack2.peek();
        }

        while(!stack1.isEmpty()) {
   
   
            stack2.push(stack1.pop());
        }

        if(!stack2.isEmpty()) {
   
   
            return stack2.peek();
        }

        return 0;

    }

    public boolean empty() {
   
   

        return stack1.isEmpty() && stack2.isEmpty();

    }
}

四、总结

栈的特性先进后出理解很简单,但是实际操作是有一定难度的,看完栈的应用,发现栈可以解决的问题还是非常有意思的。

相关文章
|
8天前
|
算法 安全 测试技术
golang 栈数据结构的实现和应用
本文详细介绍了“栈”这一数据结构的特点,并用Golang实现栈。栈是一种FILO(First In Last Out,即先进后出或后进先出)的数据结构。文章展示了如何用slice和链表来实现栈,并通过golang benchmark测试了二者的性能差异。此外,还提供了几个使用栈结构解决的实际算法问题示例,如有效的括号匹配等。
golang 栈数据结构的实现和应用
01_设计一个有getMin功能的栈
01_设计一个有getMin功能的栈
|
8天前
|
前端开发
07_用队列实现栈
07_用队列实现栈
06_用栈来求解汉诺塔问题
06_用栈来求解汉诺塔问题
05_用一个栈实现另一个栈的排序
05_用一个栈实现另一个栈的排序
03_如何仅用递归函数和栈操作逆序一个栈
03_如何仅用递归函数和栈操作逆序一个栈
|
8天前
|
测试技术
02_由两个栈组成的队列
02_由两个栈组成的队列
|
9天前
|
存储 数据安全/隐私保护 Python
Python常用数据结构——字典的应用
Python常用数据结构——字典的应用
11 2
|
12天前
|
存储
|
11天前
|
JSON 前端开发 JavaScript
一文了解树在前端中的应用,掌握数据结构中树的生命线
该文章详细介绍了树这一数据结构在前端开发中的应用,包括树的基本概念、遍历方法(如深度优先遍历、广度优先遍历)以及二叉树的先序、中序、后序遍历,并通过实例代码展示了如何在JavaScript中实现这些遍历算法。此外,文章还探讨了树结构在处理JSON数据时的应用场景。
一文了解树在前端中的应用,掌握数据结构中树的生命线