Java栈的实例-数组和链表两种方法 数组和链表.pdf

Java中的栈是一种重要的数据结构，它遵循“后进先出”（LIFO）的原则，常用于处理临时存储和撤销操作等问题。栈的操作主要包括以下几个基本运算： 1. **判断栈是否为空**：`isEmpty()`方法检查栈中是否还有元素，如果size为0，则表示栈为空。 2. **清空栈**：`clear()`方法将栈中的所有元素移除，使size恢复到0，栈变为空。 3. **栈的长度**：`length()`方法返回栈中元素的数量，即size的值。 4. **数据入栈**：`push(T data)`方法将一个元素添加到栈顶，增加size的值。 5. **数据出栈并删除**：`pop()`方法将栈顶元素移除并返回，同时减小size的值。 6. **数据出栈但不删除**：`peek()`方法返回栈顶元素的值，但不改变栈的状态，size保持不变。 在Java中，栈可以使用两种不同的方式来实现：数组和链表。 ### 数组实现栈 数组实现栈是最基础的方式，通过预先分配一个固定大小的数组来存储栈中的元素。在`MyArrayStack`类中，数组`objs`用来存储元素，`size`变量记录当前栈中的元素个数。`push()`方法将元素添加到数组末尾，`pop()`方法则移除数组末尾的元素。由于数组的大小是固定的，当栈满时，需要考虑扩容；反之，当栈空时，需要进行缩容操作，以节省内存。 ```java public class MyArrayStack<T> implements MyStack<T> { private Object[] objs = new Object[16]; // 初始化数组 private int size; @Override public boolean isEmpty() { return size == 0; } // 其他方法实现... } ``` ### 链表实现栈 链表实现栈提供了更灵活的动态扩展能力，不需要预先指定容量。在Java中，可以使用LinkedList类作为底层数据结构。链表中的每个节点包含数据以及指向下一个节点的引用，这样可以方便地在链表头部（栈顶）进行插入和删除操作。 ```java import java.util.LinkedList; public class MyLinkedListStack<T> implements MyStack<T> { private LinkedList<T> stack = new LinkedList<>(); @Override public boolean isEmpty() { return stack.isEmpty(); } // 其他方法实现... } ``` 链表实现的栈在空间效率上可能不如数组实现的栈，因为每个节点都需要额外的空间存储指针，但在处理大量数据且频繁的动态扩展时，链表的性能更优，因为它不需要像数组那样移动元素。 Java中的栈可以通过数组或链表两种方式实现，每种实现都有其优势和适用场景。选择哪种实现取决于具体的应用需求，如内存使用、插入删除效率等因素。在实际编程中，可以根据具体问题来决定采用哪种数据结构实现栈。