232.用棧實現隊列
題目鏈接 | 文檔講解 |視頻講解 :?鏈接
?1.思路：
-
? 使用2個棧去實現隊列
-
? 先將元素放入棧1中，然后在將棧1中的元素出棧到棧2中，棧2的元素出棧順序就和隊列的出隊一樣
?2.代碼：
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() {judge();return stackOut.pop(); }public int peek() {judge();return stackOut.peek();}public boolean empty() {//輸入和輸出棧都為空，說明隊列為空return stackIn.isEmpty() && stackOut.isEmpty();}public void judge(){if(!stackOut.isEmpty()){return;}while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}
}/*** 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. 用隊列實現棧
題目鏈接 | 文檔講解 |視頻講解：鏈接
?1.思路：
-
? ? ? ? 使用2個隊列實現，一個用于保持與棧的出入順序一致 q1，另一個用于輔助q2
-
? ? ? ? push()：利用兩個隊列，完成元素的倒騰，使得新加入的元素稱為棧頂
-
? ? ? ? pop()： 由于push的時候已經與棧順序元素一致，直接返回隊首即可
-
? ? ? ? top()： 同上
-
? ? ? ?empty() ：只需要判斷q1
?2.代碼：
public class MyStack {//與棧的出入順序保持一致Queue<Integer> q1 = new ArrayDeque<>();//輔助Queue<Integer> q2 = new ArrayDeque<>();public MyStack() {}public void push(int x) {//放入 [1,2]//1：q1[1] q2[]//2: q1[] q2[1] ------ q1[2,1] q2[]//將q1元素倒入q2while (q1.size()>0){q2.add(q1.poll());}//將元素放入q1中q1.add(x);//將q2元素倒回q1,把持棧頂在最前面while (q2.size()>0){q1.add(q2.poll());}}public int pop() {return q1.poll();}public int top() {return q1.peek();}public boolean empty() {return q1.isEmpty();}
}1.思路：
? ? ? ?使用一個雙端隊列實現棧
? ? ? ?push使用?ArrayDeque 在隊尾添加元素，
? ? ? pop的時候，將ArrayDeque中的size-1的元素先pollFirst()出去，在添加到隊尾
2.代碼：
public class MyStack2 {//Deque 接口繼承了 Queue 接口//所以 Queue 中的 add、poll、peek等效于 Deque 中的 addLast、pollFirst、peekFirstDeque<Integer> deque;public MyStack2() {deque=new ArrayDeque<>();}public void push(int x) {// 1 2//往隊尾加deque.addLast(x);}public int pop() {int size = deque.size();size--;while (size-- > 0) {deque.addLast(deque.pollFirst());}return deque.pollFirst();}public int top() {//棧頂元素return deque.peekLast();}public boolean empty() {return deque.isEmpty();}
}| 操作 | MyStack（兩個隊列） | MyStack2（一個 Deque） |
|---|---|---|
| 數據結構 | 兩個普通隊列 | 一個雙端隊列 |
| push 位置 | 插入 q1，然后倒騰 q2，使新元素在隊首 | 插入隊尾 |
| push 時間 | O(n)，需要兩次倒騰 | O(1)，直接插入 |
| pop 位置 | 直接從 q1 隊首彈出 | 把前 n-1 個元素重新放到隊尾，最后彈出 |
| pop 時間 | O(1) | O(n) |
| peek 時間 | O(1) | O(1) |
| 優點 | pop 快，適合頻繁出棧場景 | 結構簡單，空間少 |
| 缺點 | 空間多，push 慢 | pop 慢，不適合頻繁出棧 |
20. 有效的括號
題目鏈接 | 文檔講解 |視頻講解：鏈接
?1.思路：
-
? ??使用棧去解決
-
? ?括號的類型有 (,{,[ 三種，如果當前遍歷的元素時上述三種，則分別向棧中添加 ),},] ,如果當前遍歷的元素不是上述三種情況，判斷棧為空 || 棧頂元素與當前元素不相等，返回false?
-
? 循環外，判斷當前棧是否為空即可
?2.代碼：
public boolean isValid(String s) {Stack<Character> stack=new Stack<>();char [] arr=s.toCharArray();for(char c : arr){if(c == '('){stack.push(')');}else if(c =='{'){stack.push('}');}else if(c=='['){stack.push(']');} else if(stack.isEmpty() || c!= stack.pop()){return false;}}return stack.isEmpty();}1047. 刪除字符串中的所有相鄰重復項
題目鏈接 | 文檔講解 |視頻講解：鏈接
?1.思路：?
-
? ? 使用棧去解決
-
? ? 當棧不為空且棧頂元素和當前遍歷的元素一樣，就將棧頂元素彈出去，其余情況就往棧中添加元素
-
? ?棧中剩余的元素就是字符串中不重復的元素，但是與要求的元素的順序是相反的，需要將順序顛倒過來
?2.代碼：
public static String removeDuplicates(String str) {ArrayDeque<Character> queue = new ArrayDeque<>();for (int i = 0; i < str.length(); i++) {char c = str.charAt(i);//當棧不為空且棧首元素和當前字符串所在元素一樣,就彈出棧首if(!queue.isEmpty() && queue.peek()==c){queue.pop();}else{//往棧中添加元素queue.push(c);}}//剩余元素為不重復的元素String res="";while (!queue.isEmpty()){res=queue.pop()+res;}return res;}
