要实现带动态扩容的顺序栈,可以按照以下步骤进行:
1. 创建一个类`DynamicArrayStack`,其中包含以下属性:
- `capacity`:表示顺序栈的容量,初始值可为一个较小的常量。
- `array`:用于存储栈元素的数组。
- `top`:表示栈顶元素在数组中的索引。
2. 创建`DynamicArrayStack`类的构造方法,初始化`array`为长度为`capacity`的数组,`top`的初始值为-1。
3. 创建`push`方法,用于将新元素压入栈中:
- 首先检查栈是否已满,若已满则调用`resize`方法进行扩容。
- 将新元素放入`array`中的下一个空闲位置(即`top`的下一个位置),并将`top`值加1。
4. 创建`resize`方法,用于扩容栈的容量:
- 创建一个新的容量为原容量两倍的数组`newArray`。
- 将原数组`array`中的元素依次复制到`newArray`中。
- 将`array`引用指向`newArray`,更新`capacity`的值。
5. 创建`pop`方法,用于将栈顶元素弹出并返回:
- 首先检查栈是否为空,若为空则抛出异常。
- 获取栈顶元素的值,并将`top`值减1。
- 返回栈顶元素的值。
6. 创建`peek`方法,用于获取栈顶元素的值但不弹出:
- 首先检查栈是否为空,若为空则抛出异常。
- 获取栈顶元素的值并返回。
下面是用Java代码实现带动态扩容的顺序栈的示例:
public class DynamicArrayStack {
private int capacity;
private int[] array;
private int top;
public DynamicArrayStack() {
this.capacity = 10;
this.array = new int[capacity];
this.top = -1;
}
public void push(int data) {
if (top == capacity - 1) {
resize();
}
array[++top] = data;
}
private void resize() {
capacity *= 2;
int[] newArray = new int[capacity];
System.arraycopy(array, 0, newArray, 0, top + 1);
array = newArray;
}
public int pop() {
if (isEmpty()) {
throw new EmptyStackException();
}
return array[top--];
}
public int peek() {
if (isEmpty()) {
throw new EmptyStackException();
}
return array[top];
}
public boolean isEmpty() {
return top == -1;
}
}
可以使用以下代码测试上述实现:
public class Main {
public static void main(String[] args) {
DynamicArrayStack stack = new DynamicArrayStack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println(stack.pop()); // 输出:4
System.out.println(stack.peek()); // 输出:3
System.out.println(stack.isEmpty()); // 输出:false
}
}
输出结果:
4
3
false