【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中的整數除法一致。

對于正數除法：