当前位置：首页 > news >正文

Java-数据结构-栈和队列-习题 (＜ゝω・)☆

news 2025/6/5 20:23:22

文本目录：

❄️一、习题一(括号匹配)：

▶ 思路：

▶ 代码：

❄️二、习题二(逆波兰表达式求值)：

※ 中缀表达式转换为后缀表达式

▶ 代码：

❄️三、习题三(出栈入栈次序匹配)：

▶ 思路：

▶ 代码：

❄️四、习题四(最小栈)：

▶ 思路：

▶ 代码：

❄️五、习题五(用队列实现栈)：

▶ 思路：

▶ 代码：

▶ 总代码：

❄️六、习题六(用栈实现队列)：

▶ 思路：

▶ 代码：

❄️总结：

❄️一、习题一(括号匹配)：

☑ 题的传送门：

有效的括号(括号的匹配)

▶ 思路：

我们先来看看什么样的是括号匹配的，并且在括号匹配中都有哪几种类型是不匹配的：

这呢就是这个括号匹配如何是匹配成功的匹配不成功又有哪几种类型。那对于这个括号匹配呢，我们是如何进行判断的呢？我们这里是把 左括号的最后一个括号和右括号的第一个括号进行比较。 所以呢这里我们使用到的数据结构呢，我们可以使用栈来做这道题。

我们要如何使用栈来做这道题呢？我们用一个下标来遍历输入的括号，当我们下标对应的括号如果是左括号就入栈，当我们遇到右括号的时候用栈顶数据和右括号进行匹配，如果匹配正确就出栈并且下标往后走，不匹配就之间返回false ，直至遍历结束，并且 i 下标没有数据，栈里没有数据，为空，才是正确的匹配。这样说呢不够直观，我们来看看思路图：

这个呢，就是我们括号匹配的流程图了，当在这个进程中出现错误都是匹配不成功的。

我们来看看当匹配不成功的情况的流程图：

▶ 代码：

我们来看看代码是如何实现的：

 public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch1 = s.charAt(i);if (ch1 == '(' || ch1 == '[' || ch1 == '{') {//左括号放进栈中stack.push(ch1);}else {//出现的是)}]if (stack.empty()) {//栈如果为空，就是没有左括号，匹配不成功return false;}//开始匹配char ch2 = stack.peek();if (ch1 == ')' && ch2 == '('|| ch1 == '}' && ch2 == '{'|| ch1 == ']' && ch2 == '[') {//匹配成功的话，出栈顶数据stack.pop();}else {return false;}}}if (!stack.empty()) {// i 下标走完，看看栈是否为空，不为空就是没有匹配成功，有剩余return false;}return true;}

OK啦，我们的这个括号匹配的题就完事了，让我们继续往下看下一道题。

❄️二、习题二(逆波兰表达式求值)：

☑ 题的传送门：

逆波兰表达式求值

※ 中缀表达式转换为后缀表达式

我们在讲解这个题之前呢，我们先来了解一下一个非常重要的东西:中缀表达式转换为后缀表达式

我们来看看什么是中缀和后缀表达式：

这个呢就是中缀表达式转换为后缀表达式的一个例子。那么这个转换过程又是怎样进行的呢？

我们来看：

这就是我们把中缀表达式转换为后缀表达式的流程。我们来举一个数字的例子，并且我们使用栈来看看后缀表达式怎么运算的。我们来看看怎么运算的：

这个呢，关于中缀表达式转换为后缀表达式的流程呢，就结束了。我们接下来看看这个题要如何编写，我们可以看到我们的这个题呢，是使用后缀表达式来计算的最终值，所以这里我们要借助栈，来完成这个操作，我们上面的流程图也是这道题的思路图，所以我们直接来看代码：

▶ 代码：

private boolean isOperator(String ch) {//判断 s 是否是运算符if (ch.equals("+") || ch.equals("-") || ch.equals("*") || ch.equals("/")) {return true;}return false;}public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String s : tokens) {if (!isOperator(s)) {//不是运算符的话，就把字符串转换为数字，进行入栈int x = Integer.parseInt(s);//把s这个字符串转换为数字stack.push(x);} else {//是运算符的时候我们要出栈顶数据进行计算，//注意先出的数据放在运算符的右面int val2 = stack.pop();int 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();}

这里有我们要注意的点：

1、我们对于检查是否是运算符我们要用 equals 这个方法。

2、我们往栈里放数据的时候呢，我们要把字符串转换为数字，来进行放入。

这个转换方法在我的这篇博客里有介绍：Java—数据类型和变量 (～￣▽￣)～

❄️三、习题三(出栈入栈次序匹配)：

☑ 题的传送门：

栈的压入、弹出序列

▶ 思路：

这道题呢，我们有两个数组，一个输入栈顺序，一个是出栈顺序，这个题就相当于我们在上次博客中做的选择题是一样的。 我们把都每个数据入栈之后呢，把栈顶的数据和出栈顺序的数组的第一个数据进行比较如果相等，我们把栈顶数据出栈，并且把数组的下标往后移，这个下标要小于数组的长度，最后我们返回栈是否为空，为空就是正确的出栈顺序，如果不是空，就不是。我们来看看这个题的思路图：

这个呢，就是我们做这道题的思路了，我们接下来来看看代码如何编写：

▶ 代码：

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.empty() && j < popV.length && stack.peek() == popV[j]) {stack.pop();j++;}}if (stack.empty()) {return true;}else {return false;}}

这道题呢，就到这里就结束了，我们继续往下看。

❄️四、习题四(最小栈)：

☑ 题的传送门：

最小栈

▶ 思路：

这到题是什么意思呢，就是我们在常数时间内找到栈中的最小数据。对于这个操作呢，我们只是使用一个栈，是不可能实现的，所以这里呢我们要使用两个栈来实现这道题，其一相当于普通的栈，另一个我们放栈中的小的数据。

我们来用这个题里给的例子，来分析一下这道题是如何做的：

我们先来分析一下这个例子的方法：

这里不要看这个例子使用的是一个栈，但是呢，我们要使用两个栈进行做这道题。

来看看如何做到的：

由此我们可以得出，我们的 minstack 这个栈：

入栈时：1、当栈为空的时候，我们不管第一个数据是什么数据，我们都要入栈。

2、当栈里有数据的时候，我们判断当入栈的数据 小于等于 minstack 栈的栈顶数据的时候才能入栈。

出栈时：1、只有当我们 stack 的要出栈的数据和 minstack 的栈顶数据相等的时候，我们才能出栈。

我们把其思路分析完之后呢，来看看这道题的代码吧：

▶ 代码：

class MinStack {public Stack<Integer> stack;public 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 {if (val <= minstack.peek()) {minstack.push(val);}}}public void pop() {// 出栈if (stack.empty()) {return;}int x = stack.pop();if (x == minstack.peek()) {minstack.pop();}}public int top() {// 返回栈顶数据if (stack.empty()) {return -1;}return stack.peek();}public int getMin() {// 返回栈中的最小数据if (minstack.empty()) {return -1;}return minstack.peek();}
}

那么这样呢，我们的这个题的代码就结束了，我们继续往下看。

❄️五、习题五(用队列实现栈)：

  ☑ 题的传送门：

  用队列实现栈

我们的这道题呢，也是我们在面试中呢可能出现的一道题。

▶ 思路：

这道题呢，我们要使用两个普通的 队列(先进先出) 实现 栈(先进后出) ，我们需要围绕这个规则来进行。

我们模拟入栈呢就是：先选择一个队列把数据放到其中，之后每次我们在入栈中间要是出栈之后呢，我们再次入栈的话就把数据放到不为空的队列当中。

我们模拟出栈呢就是：我们把有数据的那个队列当中的数据出队到另一个队列当中，另一个队列进行入队操作，但是我们要把原先的那个队列当中的数据剩下来一个，之后这个剩下来的数据，就是我们模拟出栈的数据了。

我们来看流程图更加的直观，我们来看：

▶ 代码：

我们对于这个的代码，我们来一个一个实现：

我们先来看看它的成员变量和构造方法：

因为这里的 Queue 是接口所以使用 LinkedList 来实现对象。

模拟入栈操作：

就是谁不为空，把数据放到谁那里。

判空操作：

只有当我们的两个队列都为空的时候才为空。

模拟出栈操作：

这里我们要先判空，之后再不为空的队列的当中进行操作，我们要把队列的长度减一的数据放到另一个队列当中，只剩下的最后一个数据就是我们模拟出栈的值。这里我们要注意不能再循环里面用 queue1.size()-1 最为长度，因为每次我们出队，这个 queue1.size() 长度会变。

模拟查看栈顶的数据：

我们同样先判空，之后在不为空的队列里操作。我们把栈顶的数据取出放到一个变量中，之后把这个变量入队到另一个队列中，直至这个队列里没有数据，这时我们的 val 就是栈顶元素。

▶ 总代码：

class MyStack {public Queue<Integer> queue1;public Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if (!queue1.isEmpty()) {queue1.offer(x);} else if (!queue2.isEmpty()) {queue2.offer(x);} else {// 都为空，选一个队列放数据queue1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!queue1.isEmpty()) {int size = queue1.size();for (int i = 0; i < size - 1; i++) {// 把size - 1 的数据都出栈并入栈到 queue2中queue2.offer(queue1.poll());}return queue1.poll();// 出队最后一个数据} else {int size = queue2.size();for (int i = 0; i < size - 1; i++) {// 把size - 1 的数据都出栈并入栈到 queue1中queue1.offer(queue2.poll());}return queue2.poll();// 出队最后一个数据}}public int top() {if (empty()) {return -1;}if (!queue1.isEmpty()) {int size = queue1.size();int val = 0;for (int i = 0; i < size; i++) {val = queue1.poll();queue2.offer(val);}return val;} else {int size = queue2.size();int val = 0;for (int i = 0; i < size; i++) {val = queue2.poll();queue1.offer(val);}return val;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}

这个题就结束了，下面我们再来看一个面试题，我们队列都实现栈了，是不是也应该到栈实现队列了呢，所以我们接下来看栈实现队列。

❄️六、习题六(用栈实现队列)：

☑ 题的传送门：

用栈实现队列

我们的这道题呢，也是我们在面试中呢可能出现的一道题。

▶ 思路：

我们有上面代码的经验，对于这道呢，和上面也是差不多的啦，就是把其思路转换一下就可以了。但是呢和上面的思路还是有一些区别的，我们来看这个思路：

我们的 栈(先进后出) 队列(先进先出) 我们同样使用两个栈来实现。

模拟入队：我们是其中一个栈只是用于入队的操作。

模拟出队：1、我们要先判断另一个栈是否为空，如果是就把 stack1 中的所有数据都放到 stack2 中，之后我们把 stack2 中的栈顶数据出栈就是我们的模拟出队。

2、如果不为空的话，我们直接返回 stack2 中的栈顶数据。

思路图：

我们来看看代码：

▶ 代码：

我们直接来看总代码就可以了

class MyQueue {public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();// 入队stack2 = new Stack<>();// 出队}public void push(int x) {stack1.push(x);}public int pop() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (empty()) {return -1;}if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

这到题呢，到这里就已经结束了。