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

java栈怎么实现

admin
后端开发
2025-08-24
6

va栈可通过数组或链表实现，数组访问快但容量固定；链表动态扩展灵活，适用于不同场景需求

Java中实现栈（Stack）这一数据结构时，通常有两种主流方式：基于数组和基于链表，这两种方法各有优缺点，适用于不同的应用场景，以下是详细的实现步骤、代码示例以及对比分析,帮助开发者根据实际需求选择合适的方案。

基于数组的栈实现

核心思想：利用固定大小的数组存储元素，通过一个指针（如top）跟踪栈顶位置，入栈时检查是否已满,出栈时确保不为空。
关键操作逻辑
- 初始化：创建指定容量的数组，并将顶端索引设为-1（表示空栈）。
- push(E item)：若当前元素数量小于容量，则将新元素放在top+1的位置，并更新top；否则抛出异常或返回错误。
- pop()：如果栈非空，返回array[top]的值并将top减1；否则抛出异常。
- peek()：直接返回array[top]而不修改指针。
- isEmpty()/size()：通过判断top == -1或计算已用空间实现。

示例代码框架

public class ArrayStack<T> {
 private T[] data;      // 泛型数组存储数据
 private int topIndex; // 栈顶指针，初始为-1
 @SuppressWarnings("unchecked")
 public ArrayStack(int capacity) {
     data = (T[]) new Object[capacity]; // 类型转换警告抑制
     topIndex = -1;
 }
 public void push(T element) throws StackOverflowError {
     if (topIndex + 1 >= data.length) {
         throw new StackOverflowError("Stack is full");
     }
     data[++topIndex] = element;
 }
 public T pop() throws StackUnderflowError {
     if (isEmpty()) {
         throw new StackUnderflowError("Stack is empty");
     }
     return data[topIndex--];
 }
 public boolean isEmpty() {
     return topIndex == -1;
 }
 // 其他辅助方法如peek(), size()等可自行补充
}

优缺点归纳
- 优点：内存连续访问速度快，缓存友好度高；实现简单直观。
- 缺点：预设容量固定，无法动态扩展，可能导致栈溢出（StackOverflowError）；扩容需手动处理且成本较高。
适用场景：适合已知最大需求量的场景，例如解析固定长度的表达式、递归深度有限的算法等。

基于链表的栈实现

核心思想：每个节点包含数据域和指向下一个节点的引用，栈顶即为链表头部，所有操作均在头部完成,天然支持动态增长。
关键操作逻辑
- 初始化：维护一个头节点引用head，初始为null。
- push(E item)：创建新节点作为新的头节点，原头节点变为下一节点，时间复杂度O(1)。
- pop()：保存当前头节点的值后，将头指针移至下一个节点，并释放旧头节点，同样O(1)。
- peek()：直接返回头节点的值。
- isEmpty()：判断头节点是否为null。

示例代码框架

java栈怎么实现第1张

public class LinkedListStack<T> {
 private Node<T> head; // 头节点即栈顶
 private static class Node<T> {
     T value;
     Node<T> next;
     Node(T val) { this.value = val; }
 }
 public void push(T element) {
     Node<T> newNode = new Node<>(element);
     newNode.next = head;
     head = newNode;
 }
 public T pop() throws StackUnderflowError {
     if (head == null) {
         throw new StackUnderflowError("Stack is empty");
     }
     T val = head.value;
     head = head.next;
     return val;
 }
 public boolean isEmpty() {
     return head == null;
 }
 // 其他方法如peek(), size()可通过遍历实现
}

优缺点归纳
- 优点：无需预先分配空间，随需求自动扩展；插入/删除效率高且稳定。
- 缺点：每个节点需额外存储指针，内存开销略大；相比数组，随机访问性能较差（但栈本身不需要随机访问）。
适用场景：适用于不确定数据量的场合，如浏览器历史记录回退、撤销重做功能开发等。

两种方式对比表

特性	数组实现	链表实现
空间管理	静态分配，固定大小	动态分配，按需增长
插入/删除效率	O(1)，但可能触发扩容	始终O(1)
内存消耗	较低（无指针开销）	较高（每个节点含指针）
典型用例	定长数据处理	变长数据流、频繁增减
Java标准库支持	`java.util.Stack`底层用Vector	推荐自定义实现

注意事项与扩展建议

避免直接使用Java自带的Stack类：因其继承自Vector且线程安全机制导致性能损耗，建议采用上述自定义方案，对于并发环境，可考虑使用ConcurrentLinkedDeque模拟栈行为。
异常处理策略：明确区分栈满（Overflow）与栈空（Underflow）情况,并通过自定义异常提供清晰的错误反馈。
泛型支持：两种实现均应采用泛型以提高代码复用性和类型安全性。
迭代器设计：若需遍历栈内元素,可在链表版本中轻松实现迭代器模式。