栈与栈的经典面试题

客官°小女子只卖身不卖艺 2023-09-27 10:59 56阅读 0赞

## 前言 ##

在观看此篇博文之前必须会的前置知识：

> **线性表**：一次保存单个`同类型`元素，多个元素之间`逻辑上连续`

例如：数组，链表，栈，队列，字符串（内部就是char\[\]）

**栈和队列其实是操作受限的线性表**

上述讲的数组也罢，链表也罢，既可以在头部插入和删除，也能在尾部插入和删除，甚至可以在任意位置都可以插入和删除。

"栈和队列"只能在一端插入元素和删除元素

## 一、栈的特点 ##

> 先进后出，后进先出的线性表 （LIFO）

添加元素和删除元素的一端称为栈顶，另一端称为栈底。

可以把栈看成一个水杯，只能从一端插入元素，也只能从这一端取出元素（栈顶）。

![在这里插入图片描述][ddc59ef2be384389989b521f2e4d1aa9.png]

## 二、栈的应用 ##

**1.无处不在的undo（撤销）操作**

*  在任何一个编辑器中输错了一个内容使用ctrl+z就返回了上一次输入的内容
 *  在任何一个浏览器左上方点击 ← 箭头 就能返回上一次浏览的网页

**2.操作系统栈**

*  程序在执行过程中，从A函数调用B函数，从B函数调用C函数，返回执行时如何得知从哪开始继续执行呢，其实背后就是栈这个结构~~  
    ![在这里插入图片描述][a26dfc26eb544a8db476498f262fbfa4.png]

## 三、栈的实现 ##

**1. 基于数组实现的栈 -顺序栈**

*  栈只能在栈顶插入元素，在栈顶删除元素的结构

![在这里插入图片描述][c0130fa38b2f4a3b9b8180fdaf36b5cb.png]

**2.基于链表实现的栈 -链式栈**

*  同理，只是基于链表实现而已

**3.栈的三个核心操作**

*  push(E e) : 向栈中添加元素 -> 入栈，压栈
 *  E pop() : 出栈操作，弹出栈顶元素
 *  E peek() : 查看栈顶元素，但不出栈

## 四、栈的常见问题 ##

**1.括号匹配问题**

链接如下：[20.有效的括号][20.]  
![在这里插入图片描述][f79cb7b008894dd4b9fa23a8c1683e57.png]

--------------------

解题思路：

1.  给定的是个字符串，首先要把字符串转为字符数组一个个判断
2.  找到不满足闭合条件的反例即可。(\] -> false
3.  使用栈这个结构辅助

解题步骤：

1.  碰到左括号，直接入栈。（栈中只存储左括号，栈顶就是最新的左括号）
2.  遇到右括号，出栈，查看是否匹配即可。（碰到右括号直接弹出栈顶元素，查看是否匹配，若不匹配，找到反例；若匹配，就接着往后扫描字符）
3.  若还没有扫描完字符串，栈就空了，证明当前右括号匹配不了左括号，不满足条件。 （情况一）
4.  若扫描完整个字符串后仍然没有找到反例且当前栈为空，说明str是一个满足条件的字符串。 （情况二）
5.  否则，若扫描完整个字符串后，栈还不为空，证明了栈中还有若干个左括号，不满足条件。 （情况三）

详细代码：

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.最小栈][155.]

![在这里插入图片描述][a474e3c8b7af48c8b6c2c9fe9ea6c51d.png]

解题思路：

1.  首先创建两个栈s1和s2，s1用来存储原本实际元素，s2用来存储最小元素
2.  整个题目的核心操作就是push()，每次入栈的时候进行判断。
3.  当s2为空，当前元素直接入栈 （情况一）
4.  当s2的栈顶元素>当前元素，直接入栈 （情况二）
5.  当s2的栈顶元素<当前元素，就把栈顶元素再入一次栈（情况三）
6.  此时s2和s1的入栈出栈都是同步的，s2栈顶永远保存了当前数据的最小值

![在这里插入图片描述][8f5453e4cca44540a74f9e290028b53c.png]

详细代码：

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<>()类，这个实现类既实现了栈的诸多个抽象方法以及队列的抽象方法，所以不管是栈或者是队列都可以使用这个实现类。

[ddc59ef2be384389989b521f2e4d1aa9.png]: https://img-blog.csdnimg.cn/ddc59ef2be384389989b521f2e4d1aa9.png
[a26dfc26eb544a8db476498f262fbfa4.png]: https://img-blog.csdnimg.cn/a26dfc26eb544a8db476498f262fbfa4.png
[c0130fa38b2f4a3b9b8180fdaf36b5cb.png]: https://img-blog.csdnimg.cn/c0130fa38b2f4a3b9b8180fdaf36b5cb.png
[20.]: https://leetcode.cn/problems/valid-parentheses/
[f79cb7b008894dd4b9fa23a8c1683e57.png]: https://img-blog.csdnimg.cn/f79cb7b008894dd4b9fa23a8c1683e57.png
[155.]: https://leetcode.cn/problems/min-stack/
[a474e3c8b7af48c8b6c2c9fe9ea6c51d.png]: https://img-blog.csdnimg.cn/a474e3c8b7af48c8b6c2c9fe9ea6c51d.png
[8f5453e4cca44540a74f9e290028b53c.png]: https://img-blog.csdnimg.cn/8f5453e4cca44540a74f9e290028b53c.png