阅读量:0
1. 概述
计算机科学中，stack是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书。
先提供一个栈接口
package com.itheima.datastructure.Stack; public interface Stack<E> { /** * 向栈顶压入元素 * * @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<E> implements Stack<E>, Iterable<E> { static class Node<E> { E value; Node<E> next; public Node(E value, Node<E> next) { this.value = value; this.next = next; } } private int capacity = Integer.MAX_VALUE; private int size = 0; private Node<E> head = new Node<E>(null, null); private Node<E> 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<E> 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<E> iterator() { return new Iterator<E>() { Node<E> 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<E> implements Stack<E>, Iterable<E>{ 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<E> iterator() { return new Iterator<E>() { int p = top; @Override public boolean hasNext() { return p > 0; } @Override public E next() { return array[--p]; } }; } } 4. 应用
5. 习题
5.1 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}" 输出：true 示例 3：
输入：s = "(]" 输出：false
提示：
1 <= s.length <= 104s仅由括号'()[]{}'组成
解法一：
①遇到左括号，把要配对的右括号放入栈顶
②遇到右括号，若此时栈为空，返回false，否则把它与栈顶元素对比
- 若相等，栈顶元素弹出，继续对比下一组
- 若不等，无效括号直接返回false
③循环结束
- 若栈为空，表示所有括号都配上对，返回true
- 若栈不为空，表示有没配对的括号，应返回false
import java.util.HashMap; import java.util.Map; import java.util.Stack; class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); // 创建栈用于存储左括号 Map<Character, Character> 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<Character> 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^4tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在范围[-200, 200]内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
解法一：需要JDK17+
class Solution { public int evalRPN(String[] tokens) { Stack<Integer> 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<Integer> 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<Integer> 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<Character> 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<Integer> stack1; // 主栈 private Stack<Integer> 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<Integer> q1; // 主队列 private Queue<Integer> 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<Integer> 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<Integer> 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(); */