简单数组栈的局限性
栈的最大空间必须预先声明并且不能改变，试图对一个满栈执行入栈操作会产生一个针对简单数组这种 特定实现方式的异常
动态数组实现
方案一 栈满时，每次将数组的大小增加1 Push() 数组的容量增加1 Pop() 数组的大小减1 方法存在的问题：这种增加数组大小的方法开销太大，具体分析如下，例如，当n=1时候，执行 push的过程为，新建一个大小为2的数组，复制原数组中的所有元素到新数组中，在新数组末端添 加元素，当n=2时，执行push操作的过程为，新建一个大小为3的数组，复制原数组中的所有元素到 新数组中，在新数组末端添加新元素 以此类推，当n = n-1时，执行push操作的过程为，新建一个大小为n的数组，复制原来数组中的所有元素到新数组中，在新数组末端添加新元素，在执行n次push操作后，总时间开销T(n)(复制操作的数量)为1+2+…+n≈O（N*2）
重复倍增 使用数组倍增技术来提高性能，如果数组空间已满，新建一个比原数组空间大一倍的数组，然后复制元素，采用这种处理方法，执行n次push操作的时间开销为n,假设从n=1开始，一直增大到n=32,按照1,2 4,8次序倍增 倍增操作需执行logn次 n次push操作总时间开销T(n)为1+2+4+8+…+n/4+n/2+n=n(1+1/2+1/4+…+1/n)≈n(2)≈2n≈O(n) T(n)为O(n),一次push操作的平摊时间为O(1)
代码实现
public class DynArrayStack {
private int top
;
private int capacity
;
private int[] array
;
public DynArrayStack(int capacity
) {
this.capacity
= capacity
;
array
= new int[capacity
];
top
= -1;
}
public DynArrayStack() {
this(1);
}
public boolean isEmpty() {
return top
== -1;
}
public boolean isStackFull() {
return top
== (array
.length
- 1);
}
public void push(int data
) {
if (isStackFull()) {
doubleStack();
}
}
private void doubleStack() {
int[] newArray
= new int[capacity
* 2];
System
.arraycopy(array
, 0, newArray
, 0, capacity
);
capacity
= capacity
* 2;
array
= newArray
;
}
public int pop() {
if (isEmpty()) {
throw new RuntimeException("Stack is Empty!");
} else {
return array
[top
--];
}
}
public void deleteStack() {
top
= -1;
}
}
