算法训练营day10 | {232.用栈实现队列, 225.用队列实现栈, 20.有效的括号，1047.删除字符串中的所有相邻重复项}

第五章栈与队列-part01，熟悉栈和队列的特性，基本应用。

0. JAVA语言的栈与队列

• 在Java中通常使用Deque接口配合ArrayDeque作为栈或队列；作为栈时使用 push / pop / peek，作为队列时使用 offer / poll / peek，底层是循环数组，性能优于Stack和LinkedList。

  1. 作为栈的使用示例：

     Deque<Integer> stack = new ArrayDeque<>();
     
     stack.push(10);
     stack.push(20);
     System.out.println(stack.pop());  // 20
     System.out.println(stack.peek());  // 查看栈顶

  2. 作为队列的使用示例：

     Deque<Integer> queue = new ArrayDeque<>();
     
     queue.offer(10);  // 入队
     queue.offer(20); 
     System.out.println(queue.poll());  // 出队 10
     System.out.println(queue.peek());  // 查看队头 20

• 注意，使用Deque模拟一个栈时，只用队头（First），即通过队头模拟栈顶，push=addFirst。

  • API等价表

    栈方法	StackAPI	DequeAPI
    入栈	push(e)	addFirst(e) / push(e)
    出栈	pop()	removeFirst(e) / pop()
    查看栈顶	peek()	peekFirst() / peek()
    是否为空	empty()	isEmpty()
    栈大小	size()	size()

• 同时，关于空指针异常，API

  • pop()
  • peek()
  • removeFirst()都会抛异常；

• 而使用API

  • pollFisrt()、
  • peekFirst()在栈为空时返回null。

• 注意，使用Deque模拟一个单向队列时，头出尾进。

  • API等价表

    队列方法	QueueAPI	DequeAPI
    入队	offer(e)	offerLast(e)
    出队	poll()	pollFirst(e)
    查看队头	peek()	peekFirst()
    是否为空	empty()	isEmpty()
    队列大小	size()	size()

232. 用栈实现队列

• 题目链接：232. 用栈实现队列
• 文档讲解：代码随想录–232. 用栈实现队列
• 状态：JAVA语言的双端队列来模拟一个栈，然后看了视频解析。

1.1 解题过程

• 使用两个栈来模拟一个队列，出队操作时，在stackOut非空的时候，从这个栈中pop一个就行了。
• peek可以复用pop函数代码。
  ▶

  232. 用栈实现队列

  public class MyQueue {
  
      private Deque<Integer> stackIn;
      private Deque<Integer> stackOut;
  
      public MyQueue() {
          stackIn = new ArrayDeque<>();
          stackOut = new ArrayDeque<>();
      }
  
      public void push(int x) {
          stackIn.push(x);
      }
  
      public int pop() {
          if(stackOut.isEmpty()) {
              while(!stackIn.isEmpty()) stackOut.push(stackIn.pop());
          }
          return stackOut.pop();
      }
  
      public int peek() {
          int top = pop();  // 函数复用
          stackOut.push(top);
          return top;
      }
  
      public boolean empty() {
          return stackIn.isEmpty() && stackOut.isEmpty();
      }
  }
  
  /**
   * 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. 用队列实现栈

• 题目链接：225. 用队列实现栈
• 文档讲解：代码随想录–225. 用队列实现栈
• 状态：先被提醒了用一个队列就能模拟栈，然后明白了。

2.1 解题过程

• 对于栈来说，pop和peek的区别只在一个将栈顶元素弹出，另一个不弹出而已，注意代码复用。
  ▶

  225. 用队列实现栈

  import java.util.ArrayDeque;
  import java.util.Deque;
  
  public class MyStack {
  
      private Deque<Integer> queue;
  
      public MyStack() {
          queue = new ArrayDeque<>();
      }
  
      public void push(int x) {
          queue.offer(x);
      }
  
      public int pop() {
          int len = queue.size();
          while(len-- > 1) {
              queue.offer(queue.poll());
          }
          return queue.poll();
      }
  
      public int top() {
          int stackTop = pop();
          queue.offer(stackTop);
          return stackTop;
      }
  
      public boolean empty() {
          return queue.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();
   */

20. 有效的括号

• 题目链接：20. 有效的括号
• 文档讲解：代码随想录–20. 有效的括号
• 状态：栈的应用。

3.1 解题过程

• 只是借助了栈的特性，题很简单。

▶

20. 有效的括号

class Solution {
    public boolean isValid(String s) {
        char[] arr = s.toCharArray();
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == '(' || arr[i] == '{' || arr[i] == '[') stack.push(arr[i]);
            else {
                if(!stack.isEmpty()) {
                    char c = stack.pop();
                    if (arr[i] == ')' && c != '(') return false;
                    else if(arr[i] == '}' && c != '{') return false;
                    else if(arr[i] == ']' && c != '[') return false;
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

• 可以剪枝，如果括号串长度是奇数，一定不匹配；另外，左括号和右括号之间的对应关系可以用HashMap存储起来，方便匹配。

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

• 题目链接：1047. 删除字符串中的所有相邻重复项
• 文档讲解：代码随想录–1047. 删除字符串中的所有相邻重复项
• 状态：栈的应用。

4.1 解题过程

• 题目说会选择相邻且相同的字母进行删除，符合栈的特性。不过要注意将一个循环数组转为String时，元素取出的方向、用StringBuilder暂存。

▶

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

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new ArrayDeque<>();  // LinkedList作实现类也是可以的
        char[] arr = s.toCharArray();
        for (int i = 0; i < arr.length; i++) {
            if(stack.isEmpty() || stack.peek() != arr[i]) stack.push(arr[i]);
            else stack.pop();
        }
        // 转为字符串
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pollLast());
        }
        return String.valueOf(sb);
    }
}