【java】【python】leetcode刷题记录--栈与队列

232 用栈实现队列

题目描述
两个栈模拟队列的思路是利用栈（后进先出结构）的特性来实现队列（先进先出结构）的行为。这种方法依赖于两个栈来逆转元素的入队和出队顺序，从而实现队列的功能。

入队操作（使用stackIn）：所有新加入的元素都直接推入stackIn。因为栈支持后进先出，所以此时不需要考虑元素的顺序。

出队操作（使用stackOut）：当需要进行出队操作（即移除队列的最前端元素）时，我们先检查stackOut：如果stackOut为空，则将stackIn中所有元素逐一弹出并推入stackOut。这样，最先进入stackIn的元素（也就是最早入队的元素）会位于stackOut的顶部。如果stackOut不为空，则直接从stackOut弹出顶部元素（队列的前端元素）。

通过这种方式，stackOut的栈顶始终保持为队列的最前端，而stackIn用于处理新的入队操作。

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;public MyQueue() {stackIn = new Stack<>();stackOut = new Stack<>();}public void push(int x) {stackIn.push(x);}public int pop() {// 将in栈的内容全部转移到out栈，从out栈进行输出// 如果out栈有内容就先输出if(stackOut.empty()){while(!stackIn.empty()){stackOut.push(stackIn.pop());}}return stackOut.pop();}public int peek() {if(stackOut.empty()){while(!stackIn.empty()){stackOut.push(stackIn.pop());}}return stackOut.peek();}public boolean empty() {return (stackIn.empty())&&(stackOut.empty());}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

225 用队列实现栈

题目链接
这题也是利用两个队列来进行元素顺序的调整。

queue2是辅助队列，queue1存放进入栈的元素，当想要得到栈顶（队尾）元素，即把queue1的元素放入queue2，知道queue1只剩一个元素，该元素则为栈顶元素。将其弹出即可。剩余操作也是类似。

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}Queue<Integer> queueTemp;queueTemp = queue1;queue1 = queue2;queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

python版本：

from queue import Queueclass MyStack:def __init__(self):self.queue1 = Queue()def push(self, x):# 临时队列，用于转移元素temp_queue = Queue()temp_queue.put(x)  # 先放入新元素（栈顶元素）# 将原队列中的元素转移到临时队列中，确保新元素始终在队列头部while not self.queue1.empty():temp_queue.put(self.queue1.get())self.queue1 = temp_queue  # 更新队列为新的队列def pop(self):# 直接从 queue1 中取出元素，因为 queue1 的队头是栈顶return self.queue1.get()def top(self):# 获取队头元素即栈顶元素top_element = self.queue1.get()# 为保持队列状态，将该元素重新放回队头temp_queue = Queue()temp_queue.put(top_element)while not self.queue1.empty():temp_queue.put(self.queue1.get())self.queue1 = temp_queue  # 更新队列return top_elementdef empty(self):# 如果 queue1 为空，则栈为空return self.queue1.empty()

20 有效的括号

题目描述
很经典的栈的题目。

如果遇到左括号则要入栈，遇到右括号则与栈顶的元素配对，配对失败则是false，反之继续配对。这里要特别注意，右括号来的适合左括号可能为空，这是false。或者最后左括号剩余，这也是false。

class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for(int i=0; i<s.length(); i++){char tmp = s.charAt(i);if (tmp == '(' || tmp == '{' || tmp == '[') {stack.push(tmp);} else {if (stack.empty()) return false; // 先检查栈是否为空char top = stack.pop(); // 弹出栈顶元素以匹配if (tmp == ')' && top != '(') return false;if (tmp == '}' && top != '{') return false;if (tmp == ']' && top != '[') return false;}}return stack.empty();}
}

python版本：

class Solution:def isValid(self, s: str) -> bool:stack = []for char in s:if char in '({[':stack.append(char)else:if not stack:return False  # 检查栈是否为空top = stack.pop()  # 弹出栈顶元素以匹配if char == ')' and top != '(':return Falseif char == '}' and top != '{':return Falseif char == ']' and top != '[':return Falsereturn not stack  # 栈空则有效，非空则无效

当然，这题也可以用set（map）进行查找的优化，但意义不太大。比如如下代码：

import java.util.HashMap;
import java.util.Stack;public class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();HashMap<Character, Character> map = new HashMap<>();// 存储括号对应关系map.put(')', '(');map.put('}', '{');map.put(']', '[');for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 如果是右括号if (map.containsKey(c)) {// 栈为空或栈顶元素不匹配当前右括号对应的左括号if (stack.isEmpty() || stack.pop() != map.get(c)) {return false;}} else {// 否则为左括号，压入栈中stack.push(c);}}// 如果栈为空，说明所有括号都匹配成功return stack.isEmpty();}
}

1047 删除字符串中的所有相邻重复项

题目链接
第一眼还以为要双指针或者滑动窗口，但并不用，双指针往往是对数组/字符串/链表进行操作，滑动窗口则是找子序列/最大长度这种。

这题实际上就是栈的应用，没遇到一个新元素就入栈，如果栈顶元素与新的元素相同，则把栈顶元素出栈，以此类推。

关于java的StringBuider，看这篇：链接

class Solution {public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();for(int i=0; i<s.length(); i++){char tmp = s.charAt(i);if(!stack.isEmpty() && stack.peek()==tmp){stack.pop();}else{stack.push(tmp);}}StringBuilder res = new StringBuilder();for (char ch : stack) {res.append(ch);}return res.toString();}
}

python版本：join可以方便的把列表转换为字符串。如果不用join那会浪费一些时间。

class Solution:def removeDuplicates(self, s: str) -> str:stack = []for char in s:if stack and stack[-1] == char:stack.pop()else:stack.append(char)return ''.join(stack)#或者这样res = ''for c in stack:res = res + creturn res

150 逆波兰表达式求值

题目链接
题目很简单，如果了解后缀表达式很轻松能写出来，将数字存在栈中，遇到符号取出栈顶的2个元素计算，再将结果放回栈内即可。

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();for (String token : tokens) {if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {int b = stack.pop();  // 先弹出的是第二个操作数int a = stack.pop();  // 再弹出的是第一个操作数switch (token) {case "+":stack.push(a + b);break;case "-":stack.push(a - b);break;case "*":stack.push(a * b);break;case "/":stack.push(a / b);break;}} else {// 直接将字符串转换为整数并压栈stack.push(Integer.parseInt(token));}}// 最终栈顶元素就是表达式的结果return stack.peek();}
}

python版本：

class Solution:def evalRPN(self, tokens: List[str]) -> int:res = []print(int(6/(-132)))for token in tokens:if token not in {'+', '-', '*', '/'}:res.append(int(token))else:a = res.pop()b = res.pop()if token == '+':res.append(a+b)elif token == '-':res.append(b-a)elif token == '*':res.append(a*b)elif token == '/':res.append(int(b/a))return res[0]

在Python中，对于整数除法，/ 操作符执行的是真除法（返回浮点结果），而 // 操作符执行的是地板除（即对结果向下取整到最近的整数）。因此，当使用 / 并将结果强制转换为 int 时，它只是简单地去掉了小数部分，不进行四舍五入，而且对于负数结果也只是截断小数部分。而使用 //，则是在计算结果后直接返回一个整数，且结果总是向下取整，这种方式与C++和Java中的整数除法一致。

对于正数除法：

• 5 / 2 结果为 2.5，int(5 / 2) 结果为 2
• 5 // 2 结果为 2。

对于负数除法：

• -5 / 2 结果为 -2.5，int(-5 / 2) 结果为 -2。
• -5 // 2 结果为 -3，因为 -2.5 向下取整是 -3。

因此这里要使用转换为int，而不是//。