java-数据结构与算法-02-数据结构-05-栈

1. 栈

1. 概述

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

栈是一种特殊的线性表，只能在一端进行操作

• 往栈中添加元素的操作，一般叫做 push，入栈
• 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）
• 后进先出的原则，Last In First Out，LIFO
  

先提供一个栈接口

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;
import java.util.StringJoiner;/*** 链表实现的栈。* 该类实现了Stack接口和Iterable接口，允许对栈中的元素进行迭代。** @param <E> 栈中元素的类型。*/
public class LinkedListStack<E> implements Stack<E>, Iterable<E> {/*** 栈的容量，默认为Integer.MAX_VALUE，表示不限制容量。*/private int capacity = Integer.MAX_VALUE;/*** 栈中元素的数量。*/private int size;/*** 链表的头节点，用于简化插入和删除操作。*/private final Node<E> head = new Node<>(null, null);/*** 默认构造函数。*/public LinkedListStack() {}/*** 带容量限制的构造函数。** @param capacity 栈的容量限制。*/public LinkedListStack(int capacity) {this.capacity = capacity;}/*** 将元素压入栈顶。** @param value 要压入栈的元素。* @return 如果栈未满，则返回true；否则返回false。*//*head -> 2 -> 1 -> null*/@Overridepublic boolean push(E value) {if (isFull()) {return false;}head.next = new Node<>(value, head.next);size++;return true;}/*** 从栈顶弹出一个元素。** @return 如果栈不为空，则返回栈顶元素；否则返回null。*//*head -> 2 -> 1 -> null*/@Overridepublic E pop() {if (isEmpty()) {return null;}Node<E> first = head.next;head.next = first.next;size--;return first.value;}/*** 查看栈顶元素。** @return 如果栈不为空，则返回栈顶元素；否则返回null。*/@Overridepublic E peek() {if (isEmpty()) {return null;}return head.next.value;}/*** 检查栈是否为空。** @return 如果栈为空，则返回true；否则返回false。*/@Overridepublic boolean isEmpty() {return size == 0;}/*** 检查栈是否已满。** @return 如果栈已满，则返回true；否则返回false。*/@Overridepublic boolean isFull() {return size == capacity;}/*** 创建一个迭代器，用于遍历栈中的元素。** @return栈的元素迭代器。*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {Node<E> p = head.next;@Overridepublic boolean hasNext() {return p != null;}@Overridepublic E next() {E value = p.value;p = p.next;return value;}};}/*** 链表节点类，用于存储栈中的元素。** @param <E> 节点中存储的元素类型。*/static class Node<E> {E value;Node<E> next;public Node(E value, Node<E> next) {this.value = value;this.next = next;}}/*** 将栈中的元素转换为字符串表示。** @return 栈的字符串表示，元素之间用逗号分隔。*/@Overridepublic String toString() {StringJoiner sj = new StringJoiner(",");for (E e : this) {sj.add(e.toString());}return sj.toString();}
}

3. 数组实现

/*** 数组实现的栈类，支持泛型元素。* @param <E> 栈中元素的类型。*/
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; // 栈顶指针/*** 构造一个指定容量的栈。* @param capacity 栈的初始容量。*/@SuppressWarnings("all")public ArrayStack(int capacity) {this.array = (E[]) new Object[capacity];}/*** 将元素压入栈顶。* @param value 要压入栈的元素。* @return 如果栈未满，则返回true；否则返回false。*/@Overridepublic boolean push(E value) {if (isFull()) {return false;}array[top++] = value;return true;}/*** 弹出栈顶元素。* @return 栈顶元素，如果栈为空，则返回null。*/@Overridepublic E pop() {if (isEmpty()) {return null;}E e = array[--top];array[top] = null; // help GCreturn e;}/*** 查看栈顶元素。* @return 栈顶元素，如果栈为空，则返回null。*/@Overridepublic E peek() {if (isEmpty()) {return null;}return array[top - 1];}/*** 检查栈是否为空。* @return 如果栈为空，则返回true；否则返回false。*/@Overridepublic boolean isEmpty() {return top == 0;}/*** 检查栈是否已满。* @return 如果栈已满，则返回true；否则返回false。*/@Overridepublic boolean isFull() {return top == array.length;}/*** 返回栈元素的迭代器，用于遍历栈。* @return栈元素的迭代器。*//*底          顶0   1   2   3a   b   c   dp*/@Overridepublic Iterator<E> iterator() {return new Iterator<E>() {int p = top;@Overridepublic boolean hasNext() {return p > 0;}@Overridepublic E next() {return array[--p];}};}
}

4. 应用

模拟如下方法调用

public static void main(String[] args) {System.out.println("main1");System.out.println("main2");method1();method2();System.out.println("main3");
}public static void method1() {System.out.println("method1");method3();
}public static void method2() {System.out.println("method2");
}public static void method3() {System.out.println("method3");
}

模拟代码

package com.itheima.datastructure.stack;/*** CPU模拟类，使用栈来模拟方法的调用与返回。*/
public class CPU {/*** 方法帧类，用于存储方法的退出点。*/static class Frame {int exit;/*** 构造方法，初始化方法帧的退出点。* * @param exit 方法的退出点值。*/public Frame(int exit) {this.exit = exit;}}/*** 程序计数器，用于指示当前执行的指令位置。*/static int pc = 1;/*** 方法调用栈，用于模拟方法的调用与返回过程。*/static ArrayStack<Frame> stack = new ArrayStack<>(100);/*** 程序入口点。* * @param args 命令行参数。*/public static void main(String[] args) {// 初始化方法调用栈，压入一个表示main方法开始的帧stack.push(new Frame(-1));// 当栈不为空时，循环执行指令while (!stack.isEmpty()) {// 根据程序计数器的值执行相应的操作switch (pc) {case 1:// 执行main方法的第一段代码System.out.println("main1");pc++;break;case 2:// 执行main方法的第二段代码System.out.println("main2");pc++;break;case 3:// 调用method1方法stack.push(new Frame(pc + 1));pc = 100;break;case 4:// 调用method2方法stack.push(new Frame(pc + 1));pc = 200;break;case 5:// 方法返回，从栈中弹出方法帧，并跳转到退出点System.out.println("main3");pc = stack.pop().exit;break;case 100:// method1方法的代码段System.out.println("method1");stack.push(new Frame(pc + 1));pc = 300;break;case 101:// method1方法返回pc = stack.pop().exit;break;case 200:// method2方法的代码段System.out.println("method2");pc = stack.pop().exit;break;case 300:// method3方法的代码段System.out.println("method3");pc = stack.pop().exit;break;}}}
}

2. 习题

E01. 有效的括号-Leetcode 20

一个字符串中可能出现 [] () 和 {} 三种括号，判断该括号是否有效
有效的例子

()[]{}([{}])()

无效的例子

[)([)]([]

思路

• 遇到左括号, 把要配对的右括号放入栈顶
• 遇到右括号, 若此时栈为空, 返回 false，否则把它与栈顶元素对比
  • 若相等, 栈顶元素弹出, 继续对比下一组
  • 若不等, 无效括号直接返回 false
• 循环结束
  • 若栈为空, 表示所有括号都配上对, 返回 true
  • 若栈不为空, 表示右没配对的括号, 应返回 false

答案（用到了课堂案例中的 ArrayStack 类）

public boolean isValid(String s) {ArrayStack<Character> stack = new ArrayStack<>(s.length() / 2 + 1);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();
}

E02. 后缀表达式求值-Leetcode 120

后缀表达式也称为逆波兰表达式，即运算符写在后面

• 从左向右进行计算
• 不必考虑运算符优先级，即不用包含括号

示例

输入：tokens = ["2","1","+","3","*"]
输出：9
即：(2 + 1) * 3输入：tokens = ["4","13","5","/","+"]
输出：6
即：4 + (13 / 5)

题目假设

• 数字都视为整数
• 数字和运算符个数给定正确，不会有除零发生

代码

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();
}

E03. 中缀表达式转后缀

public class E03InfixToSuffix {/*思路1. 遇到数字, 拼串2. 遇到 + - * /- 优先级高于栈顶运算符 入栈- 否则将栈中高级或平级运算符出栈拼串, 本运算符入栈3. 遍历完成, 栈中剩余运算符出栈拼串- 先出栈,意味着优先运算4. 带 ()- 左括号直接入栈- 右括号要将栈中直至左括号为止的运算符出栈拼串|   ||   ||   |_____a+ba+b-ca+b*ca*b+c(a+b)*c*/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"));}/*** 将中缀表达式转换为后缀表达式。* 后缀表达式也称为逆波兰表达式，它使用栈的操作来实现运算符的优先级处理，有效地简化了计算过程。* * @param exp 中缀表达式字符串，包含数字、运算符和括号。* @return 后缀表达式字符串。*/static String infixToSuffix(String exp) {// 使用链表作为栈来存储运算符LinkedList<Character> stack = new LinkedList<>();// 使用StringBuilder来构建后缀表达式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();}/*** 计算运算符的优先级。* * @param c 运算符* @return 运算符的优先级* @throws IllegalArgumentException 如果运算符不合法，则抛出此异常*/
static int priority(char c) {// 使用switch表达式来根据运算符的类型返回对应的优先级return switch (c) {case '*' -> 2; // 乘法和除法具有相同的优先级case '/' -> 2;case '+' -> 1; // 加法和减法具有相同的优先级case '-' -> 1;case '(' -> 0; // 左括号具有最低优先级default -> throw new IllegalArgumentException("不合法的运算符:" + c);};
}}

返回结果

ab+c*
abc*+d-e*
abc+*

E04. 双栈模拟队列-Leetcode 232

给力扣题目用的自实现栈，可以定义为静态内部类

class ArrayStack<E> {private E[] array;private int top; // 栈顶指针@SuppressWarnings("all")public ArrayStack(int capacity) {this.array = (E[]) new Object[capacity];}public boolean push(E value) {if (isFull()) {return false;}array[top++] = value;return true;}public E pop() {if (isEmpty()) {return null;}return array[--top];}public E peek() {if (isEmpty()) {return null;}return array[top - 1];}public boolean isEmpty() {return top == 0;}public boolean isFull() {return top == array.length;}
}

参考解答，注意：题目已说明

• 调用 push、pop 等方法的次数最多 100

package com.itheima.datastructure.stack;/*** 双栈模拟队列** <ul>*     <li>调用 push、pop 等方法的次数最多 100</li>* </ul>*/
public class E04Leetcode232 {/*队列头        队列尾b顶   底     底   顶s1              s2队列尾添加s2.push(a)s2.push(b)队列头移除先把 s2 的所有元素移动到 s1s1.pop()*/ArrayStack<Integer> s1 = new ArrayStack<>(100);ArrayStack<Integer> s2 = new ArrayStack<>(100);public void push(int x) { //向队列尾添加s2.push(x);}public int pop() { // 从对列头移除if (s1.isEmpty()) {while (!s2.isEmpty()) {s1.push(s2.pop());}}return s1.pop();}public int peek() { // 从对列头获取if (s1.isEmpty()) {while (!s2.isEmpty()) {s1.push(s2.pop());}}return s1.peek();}public boolean empty() {return s1.isEmpty() && s2.isEmpty();}}

E05. 单队列模拟栈-Leetcode 225

给力扣题目用的自实现队列，可以定义为静态内部类

public class ArrayQueue3<E> {private final E[] array;int head = 0;int tail = 0;@SuppressWarnings("all")public ArrayQueue3(int c) {c -= 1;c |= c >> 1;c |= c >> 2;c |= c >> 4;c |= c >> 8;c |= c >> 16;c += 1;array = (E[]) new Object[c];}public boolean offer(E value) {if (isFull()) {return false;}        array[tail & (array.length - 1)] = value;tail++;return true;}public E poll() {if (isEmpty()) {return null;}E value = array[head & (array.length - 1)];head++;return value;}public E peek() {if (isEmpty()) {return null;}return array[head & (array.length - 1)];}public boolean isEmpty() {return head == tail;}public boolean isFull() {return tail - head == array.length;}
}

参考解答，注意：题目已说明

• 调用 push、pop 等方法的次数最多 100
• 每次调用 pop 和 top 都能保证栈不为空

public class E05Leetcode225 {/*队列头     队列尾cba顶           底queue.offer(a)queue.offer(b)queue.offer(c)*/ArrayQueue3<Integer> queue = new ArrayQueue3<>(100);int size = 0;public void push(int x) {queue.offer(x);for (int i = 0; i < size; i++) {queue.offer(queue.poll());}size++;}public int pop() {size--;return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}