【数据结构练习】栈的面试题集锦

目录

前言：

1.进栈过程中可以出栈的选择题

2.将递归转化为循环

3.逆波兰表达式求值

4.有效的括号

5. 栈的压入、弹出序列

6. 最小栈 

---

前言：

数据结构想要学的好，刷题少不了，我们不仅要多刷题，还要刷好题！为此我开启了一个必做好题锦集的系列，此为第一篇选择题篇，该系列会不定期更新敬请期待！

栈（Stack）的详解_WHabcwu的博客-CSDN博客

---

1.进栈过程中可以出栈的选择题

1. 若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A: 1,4,3,2                 B: 2,3,4,1                 C: 3,1,4,2               D: 3,4,2,1

A选项进出入栈顺序：

push(1)->pop() 出1；

push(2)->push(3)->push(4)->pop() 出4;

pop() 出3;

pop() 出2;

B C D步骤相同，通过分析可知C明显错误；

选C

---

2.将递归转化为循环

比如：逆序打印链表

使用栈的方法解决：

        public void printfList(Node head) {if (head == null) {return;}Node cur=head;Stack<Node> stack = new Stack<>();while (cur!=null){stack.push(cur);cur=cur.next;}while(!stack.empty()){System.out.println(stack.pop().val);}}

---

3.逆波兰表达式求值

逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/

 

要想彻底的掌握这道题，必先清楚的理解后缀表达式

 总结：

（1）遍历数字，依此压栈

（2）遇到' + ' ' - ' ' * ' ' / '就出栈2数，第一次出栈的数做为右操作数， 第二次出栈的数做为左操作数

（3）再把（2）运算的数压栈

（4）重复（1）（2）（3）

故代码： 

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String x : tokens) {if (!isoperation(x)) {stack.push(Integer.parseInt(x));} else {int x1 = stack.pop();int x2 = stack.pop();switch (x) {case "+":stack.push(x2 + x1);break;case "-":stack.push(x2 - x1);break;case "*":stack.push(x2 * x1);break;case "/":stack.push(x2 / x1);break;}}}return stack.pop();}public boolean isoperation(String x) {if (x.equals("+")  || x.equals("-") || x.equals("*") || x.equals("/")) {return true;}return false;}
}

---

4.有效的括号

有效的括号https://leetcode.cn/problems/valid-parentheses/

 

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

 解析：

（1）遍历给定的字符串，由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

（2）当我们遇到一个右括号时，我们可以取出栈顶的左括号并判断它们是否是相同类型的括号，栈为空返回flase,不为空但不是相同的类型，也返回 false。

(3)在遍历结束后，如果栈中没有左括号,返回 false。

---

5. 栈的压入、弹出序列

 

import java.util.*;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(j<popV.length&&!stack.empty()&&stack.peek().equals(popV[j])){stack.pop();j++;}}return stack.empty();}
}

解析：

---

6. 最小栈 

 最小栈https://leetcode.cn/problems/min-stack/

 

import java.util.Stack;public class MinStack {private Stack<Integer> stack;private Stack<Integer> minstack;public MinStack() {this.stack = new Stack<>();this.minstack = new Stack<>();}public void push(int val) {stack.push(val);if (minstack.empty()) {minstack.push(val);} else {if (minstack.peek() >= val) {minstack.push(val);}}}public void pop() {if(!stack.empty()){int x = stack.pop();if (x == minstack.peek()) {minstack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minstack.peek();}
}

 解析：

辅助栈法：

(1)一个用来正常存放数据->stack

(1)一个用来存放最小数据->minstack

  private Stack<Integer> stack;
    private Stack<Integer> minstack;

 push：

stack无差别入栈,对于minstack进行判断，若为空，直接入栈，若不为空，则需要与栈顶元素进行比较，若小于等于则入栈。

其余过于简单，无需多讲。

---

以上为我个人的小分享，如有问题，欢迎讨论！！！ 

都看到这了，不如关注一下，给个免费的赞