栈与栈的经典面试题
栈与栈的经典面试题
Killing Vibe
已于2022-10-14 14:56:23修改
592
收藏
27
分类专栏：
数据结构
LeetCode
文章标签：
链表
数据结构
于2022-09-25 13:42:00首次发布
数据结构
同时被 2 个专栏收录
7 篇文章
0 订阅
订阅专栏
LeetCode
5 篇文章
0 订阅
订阅专栏
前言
在观看此篇博文之前必须会的前置知识：
线性表：一次保存单个同类型元素，多个元素之间逻辑上连续
例如：数组，链表，栈，队列，字符串（内部就是char[]）
栈和队列其实是操作受限的线性表
上述讲的数组也罢，链表也罢，既可以在头部插入和删除，也能在尾部插入和删除，甚至可以在任意位置都可以插入和删除。
"栈和队列"只能在一端插入元素和删除元素
一、栈的特点先进后出，后进先出的线性表 （LIFO）
添加元素和删除元素的一端称为栈顶，另一端称为栈底。
可以把栈看成一个水杯，只能从一端插入元素，也只能从这一端取出元素（栈顶）。
二、栈的应用1.无处不在的undo（撤销）操作
在任何一个编辑器中输错了一个内容使用ctrl+z就返回了上一次输入的内容
在任何一个浏览器左上方点击 ← 箭头 就能返回上一次浏览的网页
2.操作系统栈
程序在执行过程中，从A函数调用B函数，从B函数调用C函数，返回执行时如何得知从哪开始继续执行呢，其实背后就是栈这个结构~~ 三、栈的实现1. 基于数组实现的栈 -顺序栈
栈只能在栈顶插入元素，在栈顶删除元素的结构2.基于链表实现的栈 -链式栈
同理，只是基于链表实现而已3.栈的三个核心操作
push(E e) : 向栈中添加元素 -> 入栈，压栈E pop() : 出栈操作，弹出栈顶元素E peek() : 查看栈顶元素，但不出栈 四、栈的常见问题1.括号匹配问题
链接如下：20.有效的括号
解题思路：
给定的是个字符串，首先要把字符串转为字符数组一个个判断找到不满足闭合条件的反例即可。(] -> false使用栈这个结构辅助解题步骤：
碰到左括号，直接入栈。（栈中只存储左括号，栈顶就是最新的左括号）遇到右括号，出栈，查看是否匹配即可。（碰到右括号直接弹出栈顶元素，查看是否匹配，若不匹配，找到反例；若匹配，就接着往后扫描字符）若还没有扫描完字符串，栈就空了，证明当前右括号匹配不了左括号，不满足条件。 （情况一）若扫描完整个字符串后仍然没有找到反例且当前栈为空，说明str是一个满足条件的字符串。 （情况二）否则，若扫描完整个字符串后，栈还不为空，证明了栈中还有若干个左括号，不满足条件。 （情况三）详细代码：
class Solution { public boolean isValid(String s) { Deque<Character> stack = new LinkedList<>(); char[] array=s.toCharArray(); for(int i=0;i<array.length;i++){ if(array[i]=='('){ stack.push(')'); }else if (array[i] == '['){ stack.push(']'); }else if (array[i] == '{'){ stack.push('}'); } else{ if(stack.isEmpty() || stack.pop()!=array[i] ){ return false; } } } return stack.isEmpty(); } }2.最小栈问题
链接如下：155.最小栈
解题思路：
首先创建两个栈s1和s2，s1用来存储原本实际元素，s2用来存储最小元素整个题目的核心操作就是push()，每次入栈的时候进行判断。当s2为空，当前元素直接入栈 （情况一）当s2的栈顶元素>当前元素，直接入栈 （情况二）当s2的栈顶元素<当前元素，就把栈顶元素再入一次栈（情况三）此时s2和s1的入栈出栈都是同步的，s2栈顶永远保存了当前数据的最小值详细代码：
class MinStack { Deque<Integer> xStack; Deque<Integer> minStack; public MinStack() { xStack = new LinkedList<Integer>(); minStack = new LinkedList<Integer>(); minStack.push(Integer.MAX_VALUE); } public void push(int x) { xStack.push(x); minStack.push(Math.min(minStack.peek(), x)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } } 心得创建栈或者队列的时候，我们最好都使用Deque接口下的LinkedList<>()类，这个实现类既实现了栈的诸多个抽象方法以及队列的抽象方法，所以不管是栈或者是队列都可以使用这个实现类。