java实现基本栈操作实现:设计程序实现栈的基本操作,包括入栈(push)和出栈(pop)操作。确保栈的动态扩容和缩容。
时间: 2024-09-28 14:05:13 浏览: 4
在Java中,我们可以使用`java.util.Stack`或者自定义一个数组或链表实现栈的数据结构来完成基本的操作。这里我将演示如何自定义一个基于数组的线性栈(Linear Stack)来实现:
```java
import java.util.Arrays;
class DynamicArrayStack<T> {
private static final int DEFAULT_CAPACITY = 8;
private T[] stackData;
private int top; // 栈顶指针
public DynamicArrayStack() {
this.stackData = (T[]) new Object[DEFAULT_CAPACITY];
}
// 入栈(push)
public void push(T item) {
if (top == stackData.length) {
// 扩容,如果已满则创建新数组并复制元素
resize(2 * stackData.length);
}
stackData[top++] = item;
}
// 出栈(pop)
public T pop() {
if (isEmpty()) {
throw new EmptyStackException("Stack is empty");
}
T item = stackData[top - 1]; // 从栈顶取数据
stackData[top - 1] = null; // 清理空间
top--;
return item;
}
// 查看栈顶元素但不移除(peek)
public T peek() {
if (isEmpty()) {
throw new EmptyStackException("Stack is empty");
}
return stackData[top - 1];
}
// 判断栈是否为空
public boolean isEmpty() {
return top == 0;
}
// 返回栈的大小
public int size() {
return top;
}
// 动态扩容,创建新的大容量数组,并把原数组的内容复制过去
private void resize(int newSize) {
T[] newStackData = (T[]) new Object[newSize];
System.arraycopy(stackData, 0, newStackData, 0, top);
stackData = newStackData;
}
}
```