栈与栈的经典面试题

前言

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

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

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

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

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

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

一、栈的特点

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

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

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

在这里插入图片描述

二、栈的应用

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

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

2.操作系统栈

• 程序在执行过程中，从A函数调用B函数，从B函数调用C函数，返回执行时如何得知从哪开始继续执行呢，其实背后就是栈这个结构~~

在这里插入图片描述

三、栈的实现

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

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

在这里插入图片描述

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

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

3.栈的三个核心操作

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

四、栈的常见问题

1.括号匹配问题

链接如下：20.有效的括号

在这里插入图片描述

解题思路：

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

在这里插入图片描述

解题思路：

1. 首先创建两个栈s1和s2，s1用来存储原本实际元素，s2用来存储最小元素
2. 整个题目的核心操作就是push()，每次入栈的时候进行判断。
3. 当s2为空，当前元素直接入栈 （情况一）
4. 当s2的栈顶元素>当前元素，直接入栈 （情况二）
5. 当s2的栈顶元素<当前元素，就把栈顶元素再入一次栈（情况三）
6. 此时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<>()类，这个实现类既实现了栈的诸多个抽象方法以及队列的抽象方法，所以不管是栈或者是队列都可以使用这个实现类。