第3章. 栈(Stack)

栈(Stack)

一、栈的相关概念

• 栈是一种特殊的线性表，只能在一端进行操作
• 往栈中添加元素的操作，一般叫做push，入栈。
• 往栈中移除元素的操作，一般叫做pop，出栈(只能移除栈顶元素，也叫作：弹栈)
• 先进后出的原则：Last IN FIRST OUT，LIFO。

二、栈的接口设计

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

栈的内部实现可以利用之前学过的数据结构：动态数组、链表(单、双链表)

2.1 方法一：继承之前写的ArrayList、LinkedList

package DataStructure._04栈;
import DataStructure._02链表.LinkedList;
/**
 * @author keyongkang
 * @date 2022-07-22-15:23
 */
public class Stack<E> extends LinkedList<E> {
    public boolean isEmpty() {
        return size == 0; // 这个size在AbstractList类中
    }

    public int size() {
        return size;
    }

    public void push(E element) {
        add(element);
    }

    public E pop() {
        return remove(size - 1);
    }

    public E top() {
        return get(size - 1);
    }
    
    public void clear() {
        clear();
    }
}

但是这种方法有缺点：Stack类中因为继承了ArrayList或LinkedList。所以Stack类还可以使用ArrayList或LinkedList类的其他方法，但这些方法对栈来说是多余的。

2.2 方法二：把Java内置的ArrayList或LinkedList作为Stack的成员变量

动态数组实现栈

package DataStructure._04栈;

import java.util.ArrayList;
import java.util.List;
/**
 * @author keyongkang
 * @date 2022-07-22-15:23
 */
public class Stack<E> {
    
    // 面向接口设计，并且用动态数组实现栈
    private List<E> list = new ArrayList<>();

    // 栈是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 元素的数量
    public int size() {
        return list.size();
    }

    // 入栈
    public void push(E element) {
        list.add(element);
    }

    // 出栈，并获取栈顶元素
    public E pop() {
        return list.remove(size() - 1);
    }

    // 获取栈顶元素
    public E top() {
        return list.get(size() - 1);
    }
    
    // 清空栈
    public void clear() {
        list.clear();
    }
}

双向链表实现栈

由于Java中的链表是用双向链表实现的，所以这个用双向链表实现栈。

package DataStructure._04栈;

import java.util.LinkedList;
import java.util.List;
/**
 * @author keyongkang
 * @date 2022-07-22-15:23
 */
public class Stack<E> {

    // 面向接口编程，并且用双向链表实现栈
    private List<E> list = new LinkedList<>();

    // 栈是否为空
    public boolean isEmpty() {
        return list.isEmpty();
    }

    // 元素的数量
    public int size() {
        return list.size();
    }

    // 入栈
    public void push(E element) {
        list.add(element);
    }

    // 出栈，并获取栈顶元素
    public E pop() {
        return list.remove(size() - 1);
    }

    // 获取栈顶元素
    public E top() {
        return list.get(size() - 1);
    }
    
    // 清空栈
    public void clear() {
        list.clear();
    }
}

三、Java官方的栈实现

实现方法：

• class Stack< E > extends Vector< E >

使用：

• 例如：Stack< Interger > stack = new Stack<>()；

常用方法：

• push(E)
• pop()
• peek()
• empty()

四、栈的应用

4.1 逆波兰表达式求值

4.2 有效括号

思路：

1. 遇见左字符，将左字符入栈
2. 遇见右字符

• 如果栈是空的，说明括号无效
• 如果栈不为空，将栈顶字符出栈，与右字符匹配
  • 如果左右字符不匹配，说明括号无效
  • 如果左右字符匹配，继续扫描下一个字符

3. 所有字符扫描完毕

• 栈为空，说明括号有效
• 栈不为空，说明括号无效

五、单调栈

单调栈实际上就是栈，只是利用一些巧妙的逻辑，使得每次新元素入栈后，栈内的元素都保持有序(单调递增或单调递减)。

• 单调递增栈：栈中元素从栈底到栈顶是递增的。
• 单调递减栈：栈中元素从栈底到栈顶是递减的。

应用场景：

• 下一个更大元素
• 上一个更小元素

• 模板

int[] nextGreaterElement(int[] nums) {
    int len = nums.length;
    int[] res = new int[len];
    Stack<Integer> stack = new Stack<>();
    for (int i = len - 1; i >= 0; i --) { // 倒着往栈里面放
        while (!stack.isEmpty() && stack.top() <= nums[i]) { // 判定个子高矮
            stack.pop(); // 矮个子出列
        }
        res[i] = stack.isEmpty() ? -1 : stack.top(); // 这个元素身后第一个高个
        stack.push(nums[i]); // 进栈,接收之后的身高判定
    }
    return res;
}