数组实现栈
数组实现栈
实现栈的方式有两种，一种是数组实现，一种是链表实现。相同之处在于入栈、出栈时间复杂度都为
O(1)。下面是一种数组的实现，支持入栈 push()、出栈 pop()、查看栈顶元素 peek()、判空 isEmpty()、查询栈长度 size()这些基本方法。 import java.util.Arrays;
/** * @author roger * @create 2021-06-28 10:47 */
public class MyStack {
private int[] storage; // 存放栈中元素的数组
private int capacity; // 栈的容量
private int count; // 栈中元素的数量
public static final int GROW_FACTOR = 2;
public MyStack() {
this.capacity = 8;
this.storage = new int[8];
this.count = 0;
}
public MyStack(int initialcapacity) {
if (initialcapacity < 1) {
throw new IllegalArgumentException("Capacity too small.");
}
this.capacity = initialcapacity;
this.storage = new int[initialcapacity];
this.count = 0;
}
// 入栈
public void push(int value) {
if (count == capacity) {
ensureCapacity();
}
storage[count++] = value;
}
// 确保容量大小
private void ensureCapacity() {
int newCapacity = capacity * GROW_FACTOR;
storage = Arrays.copyOf(storage, newCapacity);
capacity = newCapacity;
}
// 返回栈顶元素并出栈
private int pop() {
if (count == 0) {
throw new IllegalArgumentException("Stack is empty.");
}
count--;
return storage[count];
}
// 返回栈顶元素不出栈
private int peek() {
if (count == 0) {
throw new IllegalArgumentException("Stack is empty.");
}
return storage[count - 1];
}
// 判断栈是否为空
private boolean isEmpty() {
return count == 0;
}
// 返回栈中元素的个数
private int size() {
return count;
}
public static void main(String[] args) {
MyStack myStack = new MyStack(3);
myStack.push(7);
myStack.push(6);
myStack.push(5);
myStack.push(3);
myStack.push(4);
myStack.push(2);
myStack.push(1);
myStack.push(10);
System.out.println(myStack.peek());//8
System.out.println(myStack.size());//8
for (int i = 0; i < 8; i++) {
System.out.println(myStack.pop());
}
System.out.println(myStack.isEmpty());//true
myStack.pop();//报错：java.lang.IllegalArgumentException: Stack is empty.
}
}
