当前位置：首页 > 后端开发 > 正文

Java如何手写自定义栈实战？

admin
后端开发
2025-06-09
2118

Java中实现自定义栈可通过数组或链表结构，核心步骤包括定义栈类、内部存储数组或链表、栈顶指针，以及实现push、pop、peek和isEmpty等方法，数组实现需处理扩容，链表实现更灵活但需管理节点。

在Java中实现自定义栈是理解数据结构基础的重要实践，栈遵循后进先出（LIFO）原则，核心操作包括入栈（push）、出栈（pop）、查看栈顶（peek）等，下面通过两种典型实现——数组和链表，详细讲解开发步骤,代码可直接用于实际项目。

数组实现（固定容量）

数组实现适合预先知道栈最大深度的场景，内存连续、访问高效。

类结构与成员变量

public class ArrayStack {
    private int maxSize;   // 栈的最大容量
    private int[] stack;   // 用数组存储元素
    private int top;       // 栈顶指针（索引）
}

构造方法

初始化数组并置空栈：

public ArrayStack(int size) {
    this.maxSize = size;
    this.stack = new int[maxSize];
    this.top = -1;  // 初始化栈顶指针为-1（空栈）
}

核心方法实现

入栈 (push)：

Java如何手写自定义栈实战？第1张

public void push(int value) {
    if (isFull()) {
        throw new RuntimeException("栈已满！");
    }
    stack[++top] = value;  // 指针上移后写入数据
}

出栈 (pop)：

public int pop() {
    if (isEmpty()) {
        throw new RuntimeException("栈为空！");
    }
    return stack[top--];  // 返回栈顶元素，指针下移
}

查看栈顶 (peek)：

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("栈为空！");
    }
    return stack[top];
}

判空 & 判满：

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

链表实现（动态扩容）

链表实现无需预设容量，动态扩展内存,避免空间浪费。

节点类定义

private class Node {
    int value;
    Node next;
    Node(int value) {
        this.value = value;
    }
}

栈类与构造方法

public class LinkedStack {
    private Node top;  // 栈顶节点
    public LinkedStack() {
        top = null;    // 初始空栈
    }
}

核心方法实现

入栈 (push)：

public void push(int value) {
    Node newNode = new Node(value);
    newNode.next = top;  // 新节点指向原栈顶
    top = newNode;       // 更新栈顶指针
}

出栈 (pop)：

public int pop() {
    if (isEmpty()) {
        throw new RuntimeException("栈为空！");
    }
    int value = top.value;
    top = top.next;  // 栈顶下移
    return value;
}

查看栈顶 (peek)：

public int peek() {
    if (isEmpty()) {
        throw new RuntimeException("栈为空！");
    }
    return top.value;
}

判空：

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

两种实现的对比

特性	数组实现	链表实现
容量	固定大小（需预设）	动态扩展（无上限）
内存效率	连续内存，无额外指针开销	每个节点含指针，略占空间
时间复杂度	所有操作 O(1)	所有操作 O(1)
适用场景	明确最大深度的场景（如递归解析）	频繁增减元素的动态场景