Java栈学习笔记

一、栈数据结构

Java中栈是一种基本数据结构，它具有“后进先出”的特点：最后进入栈中的元素最先被取出。

Java中栈的实现方式有两种：数组实现和链表实现。

//数组实现
public class ArrayStack {
    private int[] arr;
    private int top;//栈顶指针
    public ArrayStack(int capacity) {
        this.arr = new int[capacity];
        this.top = -1;
    }
    public boolean isEmpty() {
        return top == -1;
    }
    public boolean isFull() {
        return top == arr.length - 1;
    }
    public void push(int data) {
        if (isFull()) {
            throw new RuntimeException("栈已满");
        }
        arr[++top] = data;
    }
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空");
        }
        return arr[top--];
    }
}

链表实现的栈相对于数组实现的栈，在动态扩容方面更为便捷，在链表头部进行插入和删除操作更为高效。

二、基本应用

栈在Java中有很多基本应用，如函数调用栈、表达式求值、括号匹配检查、汉诺塔等。

三、应用扩展

1. 单调栈

单调栈是基于栈数据结构实现的特化版本，其具有以下特点：

1) 只存储特定方向的数据，在单调递增栈中，栈从栈底到栈顶的元素是递增的；在单调递减栈中，栈从栈底到栈顶的元素是递减的。

2) 当新元素入栈时，栈内原有比其小（大）的元素都会被弹出。从而能够在O(n)的时间复杂度内解决一些很难用暴力算法解决的问题。

单调栈可以用于解决一些最值问题，如找出一个数组中元素右边第一个比他大的数、找出一个数组中元素左右两边最近的比他大的数等。

public int[] findRightMax(int[] arr) {
    int len = arr.length;
    int[] res = new int[len];
    Stack<Integer> stack = new Stack<>();
    for(int i = 0; i < len; i++) {
        while(!stack.isEmpty() && arr[i] > arr[stack.peek()]) {
            int top = stack.pop();
            res[top] = i;
        }
        stack.push(i);
    }
    while(!stack.isEmpty()) {
        res[stack.pop()] = -1;
    }
    return res;
}

2. 模拟递归

在递归中，函数调用栈起着关键作用。但是在某些情况下，递归调用栈可能会耗尽堆栈空间，尤其在计算深度大的递归时。

为了克服这个问题，我们可以使用Java中的栈数据结构自己实现递归调用。

public static int recursion(int n) {
    Stack<Integer> stack = new Stack<>();
    int res = 0;
    stack.push(n);
    while(!stack.isEmpty()) {
        int tmp = stack.pop();
        if(tmp == 1) {
            res += 1;
        } else {
            stack.push(tmp - 1);
            stack.push(tmp - 2);
        }
    }
    return res;
}

3. 开发工具

在Java开发中，栈也被广泛应用于开发工具的实现。如命令行模式下的命令历史栈，文本编辑器中的撤销操作栈等。

四、总结

本文通过对Java中栈数据结构的分析，详细介绍了栈的基本应用，及扩展的应用在Java中的实际应用。了解和熟练运用Java中的栈数据结构可以帮助我们更好地解决实际问题。