数据结构-栈-EW帮帮网

一、栈的基本概念

栈是一种重要的线性数据结构，它遵循 "后进先出"（Last In First Out，简称 LIFO）的操作原则。就像我们日常生活中叠放的盘子，最后放上去的盘子总是最先被取走。

在栈中，只有一端可以进行插入和删除操作，这一端被称为 "栈顶"，而另一端则被称为 "栈底"。插入元素的操作称为 "入栈"（push），删除元素的操作称为 "出栈"（pop）。

二、代码实现

1. Stack 类的核心结构

package 栈;

public class Stack {
    // 用数组作为栈的底层存储结构
    private int[] arr = new int[5];
    // 栈顶指针，初始值为-1表示栈空
    private int top = -1;
    
    // ... 方法实现
}

使用数组作为栈的底层存储容器，定义了栈顶指针top来标记当前栈顶的位置：

当top = -1时，表示栈为空
当top = arr.length - 1时，表示栈已满

2. 栈的核心操作

判断栈满

public boolean isFull() {
    return top == arr.length - 1;
}

判断栈空

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

入栈操作

public void push(int num) {
    if (isFull()) {
        System.out.println("栈满了");
        return;
    }
    top++;
    arr[top] = num;
}

入栈操作先判断栈是否已满，若未满则将栈顶指针上移，再存入数据。

出栈操作

public int pop() {
    if (isEmpty()) {
        System.out.println("栈空");
        throw new RuntimeException("栈空");
    }
    int res = arr[top];
    top--;
    return res;
}

出栈操作先判断栈是否为空，若非空则取出栈顶元素，再将栈顶指针下移。

3. 测试代码

package 栈;

public class Test {
    public static void main(String[] args) {
        Stack stack = new Stack();
        
        stack.push(2);
        stack.push(3);
        stack.push(6);
        stack.push(8);
        stack.push(9);
        stack.push(11);  // 此时栈已满，会输出"栈满了"
        System.out.println(stack.pop());  // 9
        System.out.println(stack.pop());  // 8
        System.out.println(stack.pop());  // 6
        System.out.println(stack.pop());  // 3
        System.out.println(stack.pop());  // 2
        System.out.println(stack.pop());  // 栈空，抛出异常
    }
}

测试结果会依次输出 9、8、6、3、2，最后抛出栈空异常，这正体现了栈 "后进先出" 的特性。

三、栈的重要知识点

1. 栈的两种实现方式

数组实现：如上述代码所示，优点是实现简单，访问速度快；缺点是栈的大小固定，可能出现溢出
链表实现：使用链表作为底层存储，优点是大小可以动态变化；缺点是实现相对复杂，访问速度稍慢

2. 栈的时间复杂度

入栈操作（push）：O (1)
出栈操作（pop）：O (1)
查看栈顶元素（peek）：O (1)

栈的所有基本操作都是常数时间复杂度，效率很高。

3. 栈的应用场景

表达式求值：用于实现计算器中的表达式计算
括号匹配：检查代码中的括号是否正确匹配
函数调用：JVM 中的方法调用栈就是典型应用
深度优先搜索（DFS）：利用栈实现图的深度优先遍历
浏览器历史记录：前进后退功能的实现
撤销操作：文本编辑器中的撤销功能

4. 栈的扩展

双栈：可以用于实现队列
单调栈：一种特殊的栈，栈中的元素保持单调递增或递减，用于解决特定问题（如最大矩形面积、接雨水等）
栈与递归：递归的底层实现依赖于栈，每一次递归调用都相当于一次入栈操作，每一次递归返回都相当于一次出栈操作

数据结构-栈