算法训练营day10 栈与队列（栈实现队列，队列实现栈，栈的应用）

💡 解题思路

1. 📝 确定输入与输出
2. 🔍 分析复杂度
3. 🔨 复杂题目拆分 ：严谨且完整 地拆分为更小的可以解决的子问题（栈和队列的功能，栈和队列的应用场景）–（多总结）
4. 💭 选择处理逻辑： 根据拆分后的子问题，总结并选择合适的问题处理思路（栈和队列的转换逻辑）
5. 🔎 检查特殊情况：边界条件和特殊情况
6. 🏁 返回结果

---

232.用栈实现队列

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

225. 用队列实现栈

class MyStack {      private Queue<Integer> mainQueue;     private Queue<Integer> auxiliaryQueue;      public MyStack() {         mainQueue = new LinkedList<>();         auxiliaryQueue = new LinkedList<>();     }      public void push(int x) {         mainQueue.offer(x);     }      public int pop() {         while(mainQueue.size() > 1) {             auxiliaryQueue.offer(mainQueue.poll());         }         int num = mainQueue.poll();         Queue<Integer> temp = mainQueue;         mainQueue = auxiliaryQueue;         auxiliaryQueue = temp;         return num;     }      public int top() {         while(mainQueue.size() > 1) {             auxiliaryQueue.offer(mainQueue.poll());         }         int num = mainQueue.poll();         auxiliaryQueue.offer(num);         Queue<Integer> temp = mainQueue;         mainQueue = auxiliaryQueue;         auxiliaryQueue = temp;         return num;     }      public boolean empty() {         return mainQueue.isEmpty();     } } 

20. 有效的括号

class Solution {     public static boolean isValid(String s) {         HashMap<Character, Character> map = new HashMap<>();         map.put(')','(');         map.put('}','{');         map.put(']','[');         Stack<Character> queueStack = new Stack<>();         int len = s.length();         if (len % 2 != 0) return false;         for (int i = 0; i < len; i++) {             char ch = s.charAt(i);             if (!map.containsKey(ch)) queueStack.push(ch);             else {                 if (queueStack.isEmpty() || queueStack.pop() != map.get(ch)) return false;             }         }         return queueStack.isEmpty();     } } 

1047. 删除字符串中的所有相邻重复项 （可以用栈，下面用的双指针）

class Solution {     public static String removeDuplicates(String s) {         int j = -1;         int len = s.length();         char[] chars = s.toCharArray();         for (int i = 0; i < len; i++) {             if (j >= 0 && chars[i] == chars[j]) {                 j--;             } else {                 j++;                 chars[j] = chars[i];             }         }         return String.copyValueOf(chars, 0, j+1);     } }