【数据结构与算法】之栈详解

栈（Stack）是一种基本的线性数据结构，遵循后进先出、先进后出的原则。本文将更详细地介绍栈的概念、特点、Java 实现以及应用场景。

1. 栈概念概述

想象一摞叠放的盘子，你只能从最上面取盘子，放盘子也只能放在最上面。栈就像这样一摞盘子，它只有一个开口，称为栈顶 (Top)。另一端封闭，称为栈底 (Bottom)。元素的添加操作称为入栈 (Push)，删除操作称为出栈 (Pop)。

栈是一种抽象数据类型 (ADT)，这意味着我们只关心它的操作和特性，而不关心具体的实现方式。栈的关键操作包括：

push(item): 将元素 item 添加到栈顶。
pop(): 移除并返回栈顶元素。
peek(): 返回栈顶元素，但不移除它。
isEmpty(): 检查栈是否为空。
size(): 返回栈中元素的数量 (部分实现可能不包含此方法)。

2. 栈的特点

后进先出 (LIFO): 这是栈最核心的特点，最后入栈的元素总是最先出栈。
操作受限: 只能在栈顶进行插入和删除操作，这限制了访问元素的灵活性，但也保证了操作的高效性 (时间复杂度为 O(1))。
有序性: 栈维护了元素的插入顺序，虽然不像队列那样严格的 FIFO，但仍然保留了元素的相对顺序。

3. 栈的 Java 实现

Java 中可以使用数组或链表实现栈。

3.1 基于数组的实现

public class ArrayStack<T> {
    private T[] data; // 存储栈元素的数组
    private int top; // 栈顶指针，指向栈顶元素的索引，-1 表示栈空
    private int capacity; // 栈的容量

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        this.data = (T[]) new Object[capacity]; // 创建泛型数组
        this.top = -1; 
    }


    //判空
    public boolean isEmpty() {
        return top == -1;
    }

    
    //判满
    public boolean isFull() {
        return top == capacity - 1;
    }

    
    //入栈操作
    public void push(T item) {
        if (isFull()) {
            // 数组实现需要处理栈满的情况，可以抛出异常或进行扩容
            throw new RuntimeException("Stack is full"); 
            // 或者： resizeArray();  // 扩容操作 (此处未实现)
        }
        data[++top] = item; // 先将 top 指针加 1，再放入元素
    }


    //出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T item = data[top]; // 获取栈顶元素
        data[top--] = null; //  为了避免对象游离，建议将出栈元素置为 null。先获取元素再将 top 指针减 1
        return item;
    }


    //返回栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return data[top];
    }


    //返回栈容量
    public int size() {
        return top + 1;
    }
}

3.2 基于链表的实现

public class LinkedListStack<T> {
    private Node<T> top; // 指向栈顶节点的指针

    private static class Node<T> { // 链表节点的内部类
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
        }
    }

    public LinkedListStack() {
        this.top = null; // 初始化栈为空
    }

    public boolean isEmpty() {
        return top == null;
    }


    //入栈
    public void push(T item) {
        Node<T> newNode = new Node<>(item); // 创建新节点
        newNode.next = top; // 新节点指向原栈顶
        top = newNode; // 更新栈顶指针
    }


    //出战
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        T data = top.data; // 获取栈顶元素
        top = top.next; // 更新栈顶指针
        return data;
    }


    //返回栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.data;
    }
}

4. 栈的基本操作图解

4.1 初始化栈

4.2 进栈

分别是：元素 a 进栈；元素 b、c 进栈

4.3 出栈

分别是：元素 c 出栈；b、a 出栈

4.4 获取栈顶元素

略，先判断栈是否空，不空直接返回 data[top] 即可。

5. 各个操作的时间复杂度

入栈 (push): 数组实现: 均摊 O(1) (因为需要考虑扩容的情况，但大多数情况下是 O(1))，链表实现: O(1)
出栈 (pop): O(1)
查看栈顶元素 (peek): O(1)

6. 栈的局限性

大小受限 (数组实现): 使用数组实现时，需要预先指定栈的大小。如果数据量超过预设大小，需要进行扩容，这会带来性能开销。链表实现则没有这个限制，可以动态增长。
不灵活的访问方式: 只能访问栈顶元素，无法直接访问其他元素。如果需要访问其他元素，需要先将栈顶元素依次弹出。

7. 总结和应用场景

栈是一种简单但强大的数据结构，其 LIFO 特性使其在许多场景下都非常有用，例如：

函数调用栈: 程序执行函数时，会将函数的局部变量、参数、返回地址等信息存储在栈中。当函数执行完毕后，这些信息会从栈中弹出，程序回到调用函数的地方继续执行。递归函数的实现也依赖于函数调用栈。
表达式求值: 例如，可以使用栈来计算后缀表达式 (逆波兰表达式)。
浏览器历史记录: 浏览器的前进和后退按钮利用了栈的特性。点击后退按钮时，会从栈中弹出上一个访问的页面。
撤销操作 (Undo/Redo): 许多软件的撤销操作使用了栈来存储操作的历史记录。每次执行操作时，将操作的信息压入栈中。点击撤销按钮时，从栈中弹出最近的操作并将其逆操作应用。
深度优先搜索 (DFS): 图算法中常用的深度优先搜索算法使用栈来存储待访问的节点。