第四章 栈（Stack）

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

• 往栈中添加元素的操作，一般叫做 push，入栈

• 从栈中移除元素的操作，一般叫做 pop，出栈（只能移除栈顶元素，也叫做：弹出栈顶元素）

• 后进先出的原则，Last In First Out，LIFO

注意：这里说的 “栈” 与内存中的 “栈空间” 是两个不同的概念

栈的接口设计

int size(); // 元素的数量
boolean isEmpty(); // 是否为空
void push(E element); // 入栈
E pop(); // 出栈
E top(); // 获取栈顶元素
void clear(); // 清空

栈的内部实现是否可以直接利用以前学过的数据结构？

链表、动态数组…

动态数组实现栈

利用前面写的动态数组实现栈，极其简单

package cn.xx.java;import cn.xx.java.list.ArrayList;
import cn.xx.java.list.List;/*** @author xiexu* @create 2021-07-18 2:21 下午*/
public class Stack<E> {private List<E> list = new ArrayList<>();public void clear() {list.clear();}public int size() {return list.size();}public boolean isEmpty() {return list.isEmpty();}public void push(E element) {list.add(element);}public E pop() {return list.remove(list.size() - 1);}public E top() {return list.get(list.size() - 1);}
}

List类

package cn.xx.java.list;/*** @author xiexu* @create 2021-07-13 9:59 上午*/
public interface List<E> {static final int ELEMENT_NOT_FOUND = -1;/*** 清除所有元素*/void clear();/*** 元素的数量** @return*/int size();/*** 是否为空** @return*/boolean isEmpty();/*** 是否包含某个元素** @param element* @return*/boolean contains(E element);/*** 添加元素到尾部** @param element*/void add(E element);/*** 获取index位置的元素** @param index* @return*/E get(int index);/*** 设置index位置的元素** @param index* @param element* @return 原来的元素ֵ*/E set(int index, E element);/*** 在index位置插入一个元素** @param index* @param element*/void add(int index, E element);/*** 删除index位置的元素** @param index* @return*/E remove(int index);/*** 查看元素的索引** @param element* @return*/int indexOf(E element);
}

ArrayList类

package cn.xx.java.list;/*** @author xiexu* @create 2021-07-12 5:11 下午*/
public class ArrayList<E> extends AbstractList<E> {private E[] elements; //所有的元素private static final int DEFAULT_CAPACITY = 10;public ArrayList(int capaticy) {//小于默认容量的一律按默认容量处理capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;elements = (E[]) new Object[capaticy];}public ArrayList() {//默认是10个容量this(DEFAULT_CAPACITY);}/*** 清除所有元素*/public void clear() {for (int i = 0; i < size; i++) {elements[i] = null;}size = 0;}/*** 元素的数量** @return*/public int size() {return size;}/*** 是否为空** @return*/public boolean isEmpty() {return size == 0;}/*** 是否包含某个元素** @return*/public boolean contains(E element) {return indexOf(element) != ELEMENT_NOT_FOUND;}/*** 获取index位置的元素** @param index* @return*/public E get(int index) { // O(1)rangeCheck(index);// index * 4 + 数组的首地址return elements[index];}/*** 设置index位置的元素** @param index* @param element* @return 原来的元素*/public E set(int index, E element) { // O(1)rangeCheck(index);E old = elements[index];elements[index] = element;return old;}/*** 添加元素到尾部** @param element*/public void add(E element) { //O(1)add(size, element);}/*** 在index位置插入一个元素** @param index* @param element*/public void add(int index, E element) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/rangeCheckForAdd(index);//扩容ensureCapacity(size + 1);for (int i = size; i > index; i--) {elements[i] = elements[i - 1];}elements[index] = element;size++;}/*** 删除index位置的元素** @param index* @return 返回删掉的元素*/public E remove(int index) {/*** 最好：O(1)* 最坏：O(n)* 平均：O(n)*/rangeCheck(index);E old = elements[index];for (int i = index + 1; i < size; i++) {elements[i - 1] = elements[i];}elements[--size] = null;return old;}/*** 查看元素的索引** @param element* @return*/public int indexOf(E element) {//null值的判断if (element == null) {for (int i = 0; i < size; i++) {if (elements[i] == null) {return i;}}} else {for (int i = 0; i < size; i++) {if (element.equals(elements[i])) {return i;}}}return ELEMENT_NOT_FOUND; //找不到就返回-1}/*** 扩容*/private void ensureCapacity(int capacity) {int oldCapacity = elements.length;if (oldCapacity >= capacity) {return;}//新容量为旧容量的1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1);E[] newElements = (E[]) new Object[newCapacity];for (int i = 0; i < size; i++) {newElements[i] = elements[i];}elements = newElements;System.out.println(oldCapacity + "扩容为：" + newCapacity);}/*** 打印数组** @return*/@Overridepublic String toString() {//size = 3, [99,88,77]StringBuilder string = new StringBuilder();string.append("size = ").append(size).append(", [");for (int i = 0; i < size; i++) {if (i != 0) {string.append(", ");}string.append(elements[i]);}string.append("]");return string.toString();}
}

栈的应用 – 浏览器的前进和后退

类似的应用场景：软件的撤销（Undo）、恢复（Redo）功能

四则运算

表达式树

练习题

练习 - 有效的括号

20_有效的括号：https://leetcode-cn.com/problems/valid-parentheses/

解题分析：

1、遇见左字符，将左字符入栈

2、遇见右字符

如果栈是空的，说明括号无效

如果栈不为空，将栈顶字符出栈，与右字符相匹配

如果左右字符不匹配，说明括号无效

如果左右字符匹配，继续扫描下一个字符

3、所有字符扫描完毕后

栈为空，说明括号有效

栈不为空，说明括号无效

解法一：

/*** [({})]** @param s* @return*/
public boolean isValid1(String s) {while (s.contains("{}") || s.contains("()") || s.contains("[]")) {s = s.replace("{}", "");s = s.replace("()", "");s = s.replace("[]", "");}return s.isEmpty();
}

解法二：

public boolean isValid2(String s) {Stack<Character> stack = new Stack<>();int length = s.length();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(' || c == '{' || c == '[') { //左字符stack.push(c);} else { //右字符if (stack.isEmpty()) {return false;}char left = stack.pop();if (left == '(' && c != ')') {return false;}if (left == '{' && c != '}') {return false;}if (left == '[' && c != ']') {return false;}}}return stack.isEmpty();
}

解法三：

private static HashMap<Character, Character> map = new HashMap<>();static {map.put('(', ')');map.put('{', '}');map.put('[', ']');
}public boolean isValid3(String s) {Stack<Character> stack = new Stack<>();int length = s.length();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (map.containsKey(c)) { //左字符stack.push(c);} else { //右字符if (stack.isEmpty()) {return false;}char left = stack.pop();if (c != map.get(left)) {return false;}}}return stack.isEmpty();
}

练习 - 括号的分数

856_括号的分数：https://leetcode-cn.com/problems/score-of-parentheses/

/*** https://leetcode-cn.com/problems/score-of-parentheses/** @author xiexu* @create 2022-03-07 10:37 AM*/
public class _856_括号的分数 {public int scoreOfParentheses(String s) {Stack<Integer> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {if (s.charAt(i) == '(') {// '('用-1来表示stack.add(-1);} else {// '()' 得1分if (stack.peek() == -1) {stack.pop();stack.push(1);} else { // 遇到数字int temp = 0;while (stack.peek() != -1) {temp += stack.pop();}stack.pop();stack.push(2 * temp);}}}int res = 0;while (!stack.isEmpty()) {res += stack.pop();}return res;}}

练习 - 逆波兰表达式求值

150_逆波兰表达式求值：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

/*** https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/** @author xiexu* @create 2022-03-07 9:07 AM*/
public class _150_逆波兰表达式求值 {public int evalRPN(String[] tokens) {Deque<Integer> stack = new LinkedList<>();for (int i = 0; i < tokens.length; i++) {if ("+".equals(tokens[i])) {stack.push(stack.pop() + stack.pop());} else if ("-".equals(tokens[i])) {// 注意 - 和 / 需要特殊处理stack.push(-stack.pop() + stack.pop());} else if ("*".equals(tokens[i])) {stack.push(stack.pop() * stack.pop());} else if ("/".equals(tokens[i])) {int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2 / temp1);} else {stack.push(Integer.valueOf(tokens[i]));}}return stack.pop();}}

练习 - 基本计算器

224_基本计算器：https://leetcode-cn.com/problems/basic-calculator/