数据结构：栈(Stack)和队列(Queue)—面试题（一）

目录

1、括号匹配

2、逆波兰表达式求值 

3、栈的压入、弹出序列

4、最小栈 

---

1、括号匹配

习题链接https://leetcode.cn/problems/valid-parentheses/description/

描述：

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

 

根据题意它是要要我们判断对应的括号是否匹配，首先这两个括号必须是相同类型的，其次，必须按照正确的顺序匹配。

例如例2和例4，他的匹配顺序是当我们遇到右括号时，让此时最后的左括号和第一个右括号进行匹配，（并不是第一个左括号就和最后一个右括号匹配这样的匹配方式 ）那么我们该用什么样的方法实现这种顺序的匹配呢？

这就要利用到我们刚学完的栈来实现了，我们可以遇到一个左括号就将它放入栈中，直到遇到右括号，这时我们遇到右括号后，此时最后的左括号就是我们此时的栈顶元素，将他与右括号进行匹配，如果匹配成功就将栈顶元素弹出，不成功就代表不是有效括号返回false,成功继续往后走，遇到左括号就放入栈中，最后查找完了整个字符串后，栈中有剩余元素就代表没有完全匹配（右括号数不够），因此不是有效括号返回false。

 

完整代码

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i = 0 ;i < s.length(); i++){char ch = s.charAt(i);if(ch == '(' || ch == '{' || ch == '['){stack.push(ch);}else{if(stack.isEmpty()){return false;}char peekchar = stack.peek();if(peekchar == '(' && ch == ')' || peekchar == '{' && ch == '}'|| peekchar == '[' && ch == ']'){stack.pop();}else{return false;}}}if(!stack.isEmpty()){return false;}return true;}
}

 

2、逆波兰表达式求值 

习题链接https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/

描述：给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

 

在了解什么是逆波兰表达是前我们要先来了解什么是中缀表达式和后缀表达式 

所谓的中缀表达式其实就是我们正常写的a+b*c这样的式子。

所谓后缀表达式其实就是我们的逆波兰表达式，而他的形式跟中缀表达式有关，首先我们要将中缀表达式按照运算优先级按上括号，再把我们的运算符提到自己所在括号的后面，最后去掉括号就能得到我们的逆波兰表达式（后缀表达式）了。

这道题他会给我们一个逆波兰表达式，让我们进行求值，如果我们想要求值我们需要将他转换为正常的计算，我们还是利用栈来解决，

我们可以将不是运算符的值（数字）转从字符串换成整数值在放入栈中，如果遇到的运算符就将弹两次栈顶元素，注意我们要将第一次弹出的元素放到运算符右边，第二次弹出的元素放到运算符左边，这样是为了防止运算符为“ - ”或者“ / ”时，改变被减数和减数 或 被除数和除数的位置，导致结果出错，因为a-b会有先弹出b在弹出a,如果不放到后面就会变成b-a.

最后将算完的值从栈中弹出去，就是我们的最终结果

完整代码 

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for(int i = 0 ; i<tokens.length ; i++){String s = tokens[i];if(!operator(s)){Integer val = Integer.valueOf(s);stack.push(val);}else{Integer val2 = stack.pop();Integer val1 = stack.pop();switch(s){case "+":stack.push(val1 + val2);break;case "-":stack.push(val1 - val2);break;case "*":stack.push(val1 * val2);break;case "/":stack.push(val1 / val2);break;}}}return stack.pop();}public boolean operator(String s){if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")){return true;}return false;}
}

3、栈的压入、弹出序列

习题链接https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

 

根据题意，他要我们判断根据我们的入栈顺序，来判断出栈顺序是否正确， 首先我们创建一个栈

利用循环将第一个数组依次压入栈中，每入栈一次就要和第二个数组判断是否出栈顺序正确，如果出栈顺序的数与入栈数不同就继续入栈，如果出栈顺序对，同时栈不为空，第二个数组没有走到最后，就让第二个数组向后移到下一个要判断的出栈元素，同时让栈此时的栈顶出栈，

最后当入栈的元素都已经入栈过了第一个数组走到了最后，判断此时栈是否为空，如果为空就代表出栈顺序对，如果不为空就代表有元素没有出栈，出栈顺序不对

 

完整代码 

public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param pushV int整型一维数组 * @param popV int整型一维数组 * @return bool布尔型*/public boolean IsPopOrder (int[] pushV, int[] popV) {Stack<Integer> stack = new Stack<>();int j = 0;for(int i = 0; i<pushV.length;i++){stack.push(pushV[i]);while(!stack.isEmpty() &&  j< popV.length && stack.peek() == popV[j]){stack.pop();j++;}}return stack.isEmpty();}
}

4、最小栈 

习题链接https://leetcode.cn/problems/min-stack/description/

描述：设计一个支持 push ，pop ，top 操作，并能在常数时间O（1）内检索到最小元素的栈。

实现 MinStack 类:

这道题的目的其实是想要我们实现一个栈，在并且在O（1）时间内找到栈的最小元素，但是如果如果我们按照正常的程序来找我们需要一个元素一个元素的来判断，这就需要O（n）的时间 ，但是这时我们可以实现一个最小栈让这个最小栈的栈顶元素为我们的最小元素，

但是我们要注意

• 当两个栈为空时，不管第一个元素是什么我们都要入栈，
• 当栈中都有元素时，我们要让普通栈入栈，最小栈先判断比不比此时的栈顶元素大，如果比此时的栈顶元素小或者等于才能入栈
• 最小栈出栈时，要跟我们普通栈栈顶元素相同才能出栈。

 

完整代码

class MinStack {Stack<Integer> stack;Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if(minStack.empty()){minStack.push(val);}else{int peekMinval = minStack.peek();if(val <= peekMinval){minStack.push(val);}}}public void pop() {int val = stack.pop();if(val == minStack.peek()){minStack.pop();}}public int top() {return  stack.peek();}public int getMin() {return minStack.peek();}
}

---

好了今天的分享就到这里了，还请大家多多关注，我们下一篇见！