栈的数组实现

 1/**
 2 * 使用数组实现一个栈，并实现自动扩容
 3 * <p>
 4 * 使用数组实现的栈叫做 <b>【顺序栈】</b>
 5 *
 6 * @author wangy
 7 * @version 1.0
 8 * @date 2021/6/24 / 13:54
 9 */
10public class StackByArray {
11
12    private Object[] data;
13
14    private final int DEFAULT_SIZE = 10;
15
16    private int size;
17
18    private int cap;
19
20    public StackByArray() {
21        this.data = new Object[DEFAULT_SIZE];
22        this.cap = DEFAULT_SIZE;
23    }
24
25    public StackByArray(int cap) {
26        this.data = new Object[cap];
27        this.cap = cap;
28    }
29
30    boolean isEmpty() {
31        return size == 0;
32    }
33
34    boolean isFull() {
35        return size == cap;
36    }
37
38    int size() {
39        return size;
40    }
41
42    // 按照出栈顺序打印栈元素
43    void printAll() {
44        System.out.print("[");
45        for (int i = size; i > 1; ) {
46            System.out.print(data[--i] + ", ");
47        }
48        System.out.println(isEmpty() ? "]" : data[0] + "]");
49    }
50
51    /**
52     * 入栈, 将数据添加到右边
53     * <p>
54     * 当栈空间满时，将栈容量增加1倍
55     * <p>
56     * 均摊时间复杂度：O(1)
57     *
58     * @param e 待入栈元素
59     */
60    void push(int e) {
61        if (isFull()) {
62            cap =  cap + cap;
63            Object[] newData = new Object[cap];
64            // copy data
65            for (int i = 0; i < size ; i++) {
66                newData[i] = data[i];
67            }
68            data = newData;
69        }
70        data[size++] = e;
71    }
72
73    /**
74     * 出栈，右边先出
75     */
76    Object pop() {
77        if (isEmpty()) throw new ArrayStoreException("Stack Empty!");
78
79        return data[--size];
80    }
81
82    Object top(){
83        return data[size -1];
84    }
85
86    public static void main(String[] args) {
87        StackByArray stack = new StackByArray(3);
88        stack.push(1);
89        stack.push(2);
90        stack.push(3);
91        stack.push(4);
92        stack.printAll();
93        stack.pop();
94        stack.pop();
95        stack.printAll();
96
97    }
98}