1. 概述

计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书。

先提供一个栈接口

package com.itheima.datastructure.Stack;  public interface Stack {     /**      * 向栈顶压入元素      *      * @param value 待压入值      * @return 压入成功返回 true, 否则返回 false      */     boolean push(E value);      /**      * 从栈顶弹出元素      *      * @return 栈非空返回栈顶元素, 栈为空返回 null      */     E pop();      /**      * 返回栈顶元素, 不弹出      *      * @return 栈非空返回栈顶元素, 栈为空返回 null      */     E peek();      /**      * 判断栈是否为空      *      * @return 空返回 true, 否则返回 false      */     boolean isEmpty();      /**      * 判断栈是否已满      *      * @return 满返回 true, 否则返回 false      */     boolean isFull(); } 

2. 链表实现

package com.itheima.datastructure.Stack;  import java.util.Iterator;  public class LinkedListStack implements Stack, Iterable {      static class Node {         E value;         Node next;          public Node(E value, Node next) {             this.value = value;             this.next = next;         }     }      private int capacity = Integer.MAX_VALUE;     private int size = 0;     private Node head = new Node(null, null);     private Node tail = head;        public LinkedListStack(int capacity) {         this.capacity = capacity;     }      @Override     public boolean push(E value) {         if(isFull()) {             return false;         }         head.next = new Node<>(value, head.next);         size++;         return true;     }      @Override     public E pop() {         if(isEmpty()) {             return null;         }         Node first = head.next;         head.next = first.next;         size--;         return first.value;     }      @Override     public E peek() {         if(isEmpty()) {             return null;         }         return head.next.value;     }      @Override     public boolean isEmpty() {         return size == 0;     }      @Override     public boolean isFull() {         return size == capacity;     }      @Override     public Iterator iterator() {         return new Iterator() {             Node p = head.next;             @Override             public boolean hasNext() {                 return p != null;             }              @Override             public E next() {                 E value = p.value;                 p = p.next;                 return value;             }         };     } } 

3. 数组实现

package com.itheima.datastructure.Stack;  import java.util.Iterator;  public class ArrayStack implements Stack, Iterable{     private final E[] array;     private int top = 0;  // 栈顶指针      @SuppressWarnings("all")     public ArrayStack(int capacity) {         this.array = (E[]) new Object[capacity];     }      @Override     public boolean push(E value) {         if(isFull()) {             return false;         }         array[top++] = value;         return true;     }      @Override     public E pop() {         if(isEmpty()) {             return null;         }         E value = array[--top];         return value;     }      @Override     public E peek() {         if(isEmpty()) {             return null;         }         E value = array[top - 1];         return value;     }      @Override     public boolean isEmpty() {         return top == 0;     }      @Override     public boolean isFull() {         return top == array.length;     }      @Override     public Iterator iterator() {         return new Iterator() {             int p = top;             @Override             public boolean hasNext() {                 return p > 0;             }              @Override             public E next() {                 return array[--p];             }         };     } } 

4. 应用

5. 习题

5.1 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()" 输出：true 

示例 2：

输入：s = "()[]{}" 输出：true 

示例 3：

输入：s = "(]" 输出：false 

提示：

• 1 <= s.length <= 104
• s 仅由括号 '()[]{}' 组成

解法一：

①遇到左括号，把要配对的右括号放入栈顶

②遇到右括号，若此时栈为空，返回false，否则把它与栈顶元素对比

• 若相等，栈顶元素弹出，继续对比下一组
• 若不等，无效括号直接返回false

③循环结束

• 若栈为空，表示所有括号都配上对，返回true
• 若栈不为空，表示有没配对的括号，应返回false

import java.util.HashMap;   import java.util.Map;   import java.util.Stack;    class Solution {       public boolean isValid(String s) {           Stack stack = new Stack<>(); // 创建栈用于存储左括号           Map brackets = new HashMap<>(); // 创建映射用于存储括号配对            // 初始化括号配对           brackets.put(')', '(');           brackets.put('}', '{');           brackets.put(']', '[');            // 遍历字符串中的每个字符           for (char c : s.toCharArray()) {               // 如果是右括号               if (brackets.containsKey(c)) {                   // 栈为空或者栈顶元素与当前右括号不匹配，返回false                   if (stack.isEmpty() || stack.peek() != brackets.get(c)) {                       return false;                   }                   stack.pop(); // 匹配成功，弹出栈顶元素               } else {                   stack.push(c); // 左括号入栈               }           }           return stack.isEmpty(); // 返回栈是否为空       }   }

import java.util.Stack;    // ({[]}) class Solution {       public boolean isValid(String s) {           Stack stack = new Stack<>(); // 创建栈用于存储右括号           for(int i = 0; i < s.length(); i++) {             char c = s.charAt(i);             // 左括号             if(c == '(') {                 stack.push(')');             } else if(c == '[') {                 stack.push(']');             } else if(c == '{') {                 stack.push('}');             } else {                 // 右括号                 if(!stack.isEmpty() && stack.peek() == c) {                     stack.pop();                 } else {                     return false;                 }             }         }          return stack.isEmpty();     }   }

5.2 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 '+'、'-'、'*' 和 '/' 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 

示例 2：

输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6 

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为：   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22 

提示：

• 1 <= tokens.length <= 10^4
• tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

• 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
• 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

解法一：需要JDK17+

class Solution {     public int evalRPN(String[] tokens) {         Stack st = new Stack<>();          for(String token : tokens) {             if(token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {                 int num2 = st.pop();                 int num1 = st.pop();                 switch(token) {                     case "+":                         st.push(num1 + num2);                         break;                     case "-":                         st.push(num1 - num2);                         break;                     case "*":                         st.push(num1 * num2);                         break;                     case "/":                         st.push(num1 / num2);                         break;                 }             } else {                 st.push(Integer.parseInt(token));             }         }         return st.pop();     } }

或

class Solution {     public int evalRPN(String[] tokens) {         Stack st = new Stack<>();          for (String token : tokens) {             switch (token) {                 case "+" -> {                     Integer num2 = st.pop();                     Integer num1 = st.pop();                     st.push(num1 + num2);                 }                                      case "-" -> {                     Integer num2 = st.pop();                     Integer num1 = st.pop();                     st.push(num1 - num2);                 }                  case "*" -> {                     Integer num2 = st.pop();                     Integer num1 = st.pop();                     st.push(num1 * num2);                 }                 case "/" -> {                     Integer num2 = st.pop();                     Integer num1 = st.pop();                     st.push(num1 / num2);                 }                  default -> st.push(Integer.parseInt(token));             }         }         return st.pop();     } }

解法三：

public int evalRPN(String[] tokens) {     LinkedList numbers = new LinkedList<>();     for (String t : tokens) {         switch (t) {             case "+" -> {                 Integer b = numbers.pop();                 Integer a = numbers.pop();                 numbers.push(a + b);             }             case "-" -> {                 Integer b = numbers.pop();                 Integer a = numbers.pop();                 numbers.push(a - b);             }             case "*" -> {                 Integer b = numbers.pop();                 Integer a = numbers.pop();                 numbers.push(a * b);             }             case "/" -> {                 Integer b = numbers.pop();                 Integer a = numbers.pop();                 numbers.push(a / b);             }             default -> numbers.push(Integer.parseInt(t));         }     }     return numbers.pop(); }

5.3 中缀表达式转后缀

package com.itheima.datastructure.Stack;  import java.util.LinkedList;  public class E03InfixToSuffix {     /**      * 思路      * 1. 遇到数字，拼串      * 2. 遇到 + - * /      *    - 优先级高于栈顶运算符 入栈      *    - 否则将栈中高级或平级运算符出栈拼串，本运算符入栈      * 3. 遍历完成，栈中剩余运算符出栈拼串      *    -先出栈，意味着优先运算      *  4. 带 ()      *    - 左括号直接入栈      *    - 右括号要将栈中直至左括号为止的运算符出栈拼串      */      public static void main(String[] args) {         System.out.println(infixToSuffix("a+b"));         System.out.println(infixToSuffix("a+b-c"));         System.out.println(infixToSuffix("a+b*c"));         System.out.println(infixToSuffix("a*b-c"));         System.out.println(infixToSuffix("(a+b)*c"));         System.out.println(infixToSuffix("a+b*c+(d*e+f)*g"));     }      static String infixToSuffix(String exp) {         LinkedList stack = new LinkedList<>();         StringBuilder sb = new StringBuilder(exp.length());         for (int i = 0; i < exp.length(); i++) {             char c = exp.charAt(i);             switch (c) {                 case '+', '-', '*', '/' -> {                     if(stack.isEmpty()) {                         stack.push(c);                     } else {                         if(priority(c) > priority(stack.peek())) {  // 当前运算符比栈顶运算符优先级高                             stack.push(c);                         } else {                             while(!stack.isEmpty() && priority(stack.peek()) >= priority(c)) {  //将栈中高级或平级运算符出栈拼串                                 sb.append(stack.pop());                             }                             stack.push(c);  // 本运算符入栈                         }                     }                 }                 case '(' -> {                     stack.push(c);                 }                 case ')' -> {                     while (!stack.isEmpty() && stack.peek() != '(') {                         sb.append(stack.pop());                     }                     stack.pop();  // '('出栈                 }                 default -> {                     sb.append(c);                 }             }         }         while(!stack.isEmpty()) {             sb.append(stack.pop());         }         return sb.toString();     }      private static int priority(char c) {         return switch (c) {             case '(' -> 0;             case '*', '/' -> 2;             case '+', '-' -> 1;             default -> throw new IllegalArgumentException("不合法字符：" + c);         };     } } 

5.4 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false]  解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false

提示：

• 1 <= x <= 9
• 最多调用 100 次 push、pop、peek 和 empty
• 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

• 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

class MyQueue {     private Stack stack1;  // 主栈     private Stack stack2;  // 辅助栈      public MyQueue() {         stack1 = new Stack<>();         stack2 = new Stack<>();     }      public void push(int x) {         stack1.push(x);     }      // 先把stack1的所有元素移动到stack2，stack2再出栈     public int pop() {         if (stack2.isEmpty()) {  // 如果不为空，直接弹stack2的栈顶即可             while (!stack1.isEmpty()) {                 stack2.push(stack1.pop());             }         }         return stack2.pop();      }      public int peek() {         if (stack2.isEmpty()) {             while (!stack1.isEmpty()) {                 stack2.push(stack1.pop());             }         }         return stack2.peek();     }      public boolean empty() {         return stack1.isEmpty() && stack2.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();  */

5.5 用队列模拟栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false]  解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False 

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

解法一：两个队列实现栈

思路：

• 入栈：直接添加到q1的末尾；
• 出栈：先将前n- 1个元素从q1移到q2，q1中剩下的一个元素即为栈顶，然后再将q2中的元素恢复到q1
• 栈顶：每次最新入栈的元素
• 判空：q1是否为空

import java.util.LinkedList;   import java.util.Queue;    class MyStack {       private Queue q1;  // 主队列     private Queue q2;  // 辅助队列     private int topElement;        /** Initialize your data structure here. */       public MyStack() {           q1 = new LinkedList<>();           q2 = new LinkedList<>();       }        /** Push element x onto stack. */       public void push(int x) {           q1.offer(x);           topElement = x;       }        /** Removes the element on the top of the stack and returns that element. */       public int pop() {           while (q1.size() > 1) {               topElement = q1.poll(); // Get and remove the front element               q2.offer(topElement);      // Add it to the second queue           }            int result = q1.poll(); // The last remaining element is the top of the stack           // Swap the queues           Queue temp = q1;           q1 = q2;           q2 = temp;           return result;       }        /** Get the top element. */       public int top() {           return topElement;       }        /** Returns whether the stack is empty. */       public boolean empty() {           return q1.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();    */

解法二：一个队列实现栈

思路：

• 出栈：直接移除队头元素
• 出栈：将元素入队；将前size - 1个元素先从队列中移除的同时重新添加到队尾

class MyStack {     private Queue q;      public MyStack() {         q = new LinkedList<>();     }          // 通过多次反转队列中的元素保证最新添加的元素位于队列的前面     public void push(int x) {         // 将x加入队列         q.offer(x);         // 重新调整队列，使得x在队头         int size = q.size();         for(int i = 0; i < size - 1; i++) {             q.offer(q.poll());         }     }          public int pop() {         return q.poll();     }          public int top() {         return q.peek();     }          public boolean empty() {         return q.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();  */