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

【Java数据结构】栈和队列相关算法

news 来源：原创 2025/7/17 1:22:26

第一题：改变元素的序列

例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

例2：一个栈的初始状态为空，现将元素1，2，3，4，5，A，B，C，D，E依次入栈，然后再次依次出栈，则元素出栈的顺序是（）；

A：12345ABCDE B：EDCBA54321

C：ABCDE12345 D：54321EDCBA

题目意思是先把元素全部一个一个入栈，然后再一个一个出栈，得到的结果就是B。

第二题：逆序打印链表

题目想表达的意思是，对于一个单链表，它只能从头结点打印到尾结点，而不能从尾结点到头结点，所以想让程序员设计一个逆向的打印（通过上节所学的栈来实现）。大概思路就是将一个单链表中的元素都入栈，然后将出栈元素打印即可。

public void reversePrint1(){Stack<Integer> s = new Stack<>();ListNode cur = head;while (cur != null){s.push(cur.val);cur = cur.next;}while (!s.empty()){System.out.print(s.pop()+"  ");}System.out.println();
}

也可以将结点入栈，然后打印出栈结点的值（道理相同）

public void reversePrint(){Stack<ListNode> s = new Stack<ListNode>();ListNode cur = head;while (cur != null){s.push(cur);cur = cur.next;}while (!s.empty()){ListNode top = s.pop();System.out.print(top.val+"   ");}System.out.println();
}

第三题：括号匹配

20. 有效的括号 - 力扣（LeetCode）

这题可以通过栈来作答，将左括号入栈，右括号则需判断栈顶元素是否和它匹配。做这题要考虑多种选择：

（1）.如果字符串第一个字符就是左边的括号，就不用往后看了（离它最近的没有字符可以和它匹配）。

（2）.如果栈中出现空然后下一个字符串又是右边括号，这个也是后面不需要再看的，如果不为空，那就进行匹配。（所以需要在遇见右边括号后看栈是否为空）

（3）.如果遇到左边括号，那就将其入栈。

（4）.如果最后字符串都遍历完了，栈为空则匹配否则不匹配。

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

第四题：逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）

这题也是通过栈来实现的，解题思路就是如果字符串为数字那就入栈，如果遇到运算符号就进行运算，栈顶元素放在运算符号后面进行运算（也就是栈顶下一个元素【+-*/】栈顶元素）。要注意的遇到字符串是数字的还需要转类型存入栈中（字符串转整型Integer.parseInt(字符串)）。

public static int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack();int a = 0;int b = 0;for (int i = 0; i < tokens.length; i++) {String s = tokens[i];switch (s) {case "+":b = stack.pop();a = stack.pop();stack.push(a + b);break;case "-":b = stack.pop();a = stack.pop();stack.push(a - b);break;case "*":b = stack.pop();a = stack.pop();stack.push(a * b);break;case "/":b = stack.pop();a = stack.pop();stack.push((int) a / b);break;default:stack.push(Integer.parseInt(s));}}return stack.pop();
}

第五题：出栈入栈次序匹配

栈的压入、弹出序列_牛客题霸_牛客网

这题就是将第一题的选择题用代码实现，思路就是需要将元素依次入栈，在入栈后都要判断栈顶元素是否存在与出栈列表相同的元素，也有可能出栈多个元素，所以在while循环里，重点：如果栈为空但是还存在元素就需要跳出循环继续入栈。

public static 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.peek() == popV[j]) {j++;stack.pop();if (stack.empty()){break;}}}return stack.empty();
}

第六题：最小栈

155. 最小栈 - 力扣（LeetCode）

实现最小栈的方式是两个栈一块使用，一个存入栈的元素，一个存栈中最小的元素，两个栈相辅相成就可以每次拿出最小值的复杂度是O(1)；

（1）.先创建两个栈，再写一个构造方法；

（2）.入栈：入栈分栈为空和不为空入栈，为空时：两个栈都入栈，不为空时又分两种最小值和非最小值（这个判断条件就是入栈元素比s2中的栈顶元素小或者等于时两个栈都要进）；

（3）.出栈：如果两个栈的栈顶元素相同那就两边都出栈，不相同那就出s1；

（4）.获得栈顶元素：也就是获得s1中的栈顶元素；

（5）.得到栈中最小值：获得s2的栈顶元素即可；

class MinStack {Stack<Integer> s1;Stack<Integer> s2;public MinStack() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int val) {if (s1.empty()){s1.push(val);s2.push(val);return;}if (val <= s2.peek()){s2.push(val);}s1.push(val);}public void pop() {if (s1.peek().equals(s2.peek())){s1.pop();s2.pop();return;}else{s1.pop();}}public int top() {if (s1.empty())return -1;return s1.peek();}public int getMin() {return s2.peek();}
}

第七题：用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）

用两个队列实现栈，思路如下：

（1）.实现入栈：把元素放在不是空的队列，如果两个都为空就放在q1（起始时默认q2是空）

（2）. 实现出栈：将不为空的栈中的所有元素个-1全部出栈并依次放入为空的栈中，此时栈中剩下的一个元素就是一个栈出栈的元素；

（3）.获取栈顶元；素：还是同出栈原理相同就是将每次出栈的元素都存起来，最后一个就是栈顶元素

（4）.判断是否为空：当两个队都为空时为空，其它情况都不为空；

class MyStack {Queue<Integer> q1;Queue<Integer> q2;public MyStack() {q1 = new LinkedList<>();q2  = new LinkedList<>();}public void push(int x) {if (!q1.isEmpty()){q1.offer(x);}else if (!q2.isEmpty()){q2.offer(x);}else{q1.offer(x);}}public int pop() {if (empty()){return -1;}if (!q1.isEmpty()){int size = q1.size();for (int i = 0; i < size - 1; i++){q2.offer(q1.poll());}return q1.poll();}else{int size = q2.size();for (int i = 0; i < size - 1; i++){q1.offer(q2.poll());}return q2.poll();}}public int top() {if (empty()){return -1;}int temp = 0;if (!q1.isEmpty()){int size = q1.size();for (int i = 0; i < size; i++){temp = q1.poll();q2.offer(temp);}return temp;}else{int size = q2.size();for (int i = 0; i < size; i++){temp = q2.poll();q1.offer(temp);}return temp;}}public boolean empty() {return q1.isEmpty()&&q2.isEmpty();}
}

第八题：用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）

用两个栈实现队列，思路是：

（1）. 实现入队：直接将元素入队到s1中；

（2）. 实现出队：判断s2的栈中是否为空，为空那就将s1中所有元素都进入到s2中，然后s2中出一个元素就是队列的出队操作，如果不为空直接从s2中出一个元素；

（3）. 获取栈顶元素：和出队相像，只是返回栈顶元素；

（4）.判断是否为空：当两个栈都为空时为空，其它情况都不为空；

class MyQueue {private Stack<Integer> s1;private Stack<Integer> s2;public MyQueue() {s1 = new Stack<>();s2 = new Stack<>();}public void push(int x) {s1.push(x);}public int pop() {if (s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.pop();}public int peek() {if (s2.empty()){while(!s1.empty()){s2.push(s1.pop());}}return s2.peek();}public boolean empty() {return s1.empty()&&s2.empty();}
}

还有很对与栈和队列相关的算法题，大家可以在LeetCode和牛客等网站上找找呀！