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

简介: 文章总结了栈的几个经典应用场景,包括使用两个栈来实现队列的功能以及利用栈进行对称匹配,并通过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();

    }
}

四、总结

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

相关文章
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
178 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
23天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
44 5
|
21天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
50 1
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
40 5
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
51 4
|
2月前
|
机器学习/深度学习 存储 人工智能
数据结构在实际开发中的广泛应用
【10月更文挑战第20天】数据结构是软件开发的基础,它们贯穿于各种应用场景中,为解决实际问题提供了有力的支持。不同的数据结构具有不同的特点和优势,开发者需要根据具体需求选择合适的数据结构,以实现高效、可靠的程序设计。
108 7
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!