5 手写Java Stack 核心源码

Stack是Java中常用的数据结构之一，Stack具有"后进先出(LIFO)"的性质。只能在一端进行插入或者删除，即压栈与出栈

栈的实现比较简单，性质也简单。可以用一个数组来实现栈结构。

入栈的时候，只在数组尾部插入
出栈的时候，只在数组尾部删除**

我们来看一下Stack的用法：如下

1  public static void main(String[] args){
2
3        //新建一个栈
4        Stack<String> stack = new Stack<>();
5
6        //分别向栈中添加不同的元素
7        stack.push("tom");
8        stack.push("jim");
9        stack.push("wendy");
10        stack.push("natasha");
11
12        //分别弹栈
13        System.out.println(stack.pop());
14        System.out.println(stack.pop());
15        System.out.println(stack.pop());
16        System.out.println(stack.pop());
17
18    }

输出如下：

1
2natasha
3wendy
4jim
5tom

从输出可以看到，最后入栈的，最先出栈

下面我们底层用数组也来实现这样一个栈，在数组的尾部插入和删除。也就是入栈和出栈。如下图：

完整的源码如下：

1
2public class QStack<E> {
3    //数组的默认大小为10
4    private static final int DEFAULT_INIT_CAPACITY = 10;
5
6    //底层的数组
7    private Object[] elements;
8
9    //栈中的个数
10    private int size;
11
12    public QStack() {
13        this(DEFAULT_INIT_CAPACITY);
14    }
15
16
17    public QStack(int capacity) {
18        //capacity条件检查 ，这里我们直接抛出异常
19        if (capacity <= 0) {
20            throw new IllegalArgumentException("capacity <= 0");
21        }
22
23        if (capacity > Integer.MAX_VALUE) {
24            throw new IllegalArgumentException("capacity > Integer.MAX_VALUE");
25        }
26
27        //新建一个capacity大小的数组
28        elements = new Object[capacity];
29
30        //初始个数为0
31        size = 0;
32    }
33
34    //栈是否为空
35    public boolean isEmpty() {
36        return size == 0;
37    }
38
39    //返回栈中的元素个数
40    public int size() {
41        return size;
42    }
43
44    //将一个元素压入栈中
45    public E push(E e) {
46        //如果栈已满，进行扩容
47        if (size >= elements.length) {
48            grow();
49        }
50
51        //扩容完后将元素e压入栈中
52        elements[size] = e;
53
54        //别忘了size需要加 1
55        size++;
56
57        return e;
58    }
59
60    //出栈，就是将数组最后一个元素弹出
61    public E pop() {
62        //如果栈为空就返回null
63        if (isEmpty()) {
64            return null;
65        }
66
67        //拿到栈的大小
68        int len = size();
69
70        //把数组中最后一个元素保存起来
71        E e = peek();
72        //个数别忘了减1
73        size--;
74
75        //将最后一个元素置null
76        elements[len - 1] = null;
77
78        //返回e
79        return e;
80    }
81
82    //返回最后一个元素
83    public E peek() {
84        int len = size();
85
86        if (len == 0)
87            throw new RuntimeException("stack is empty");
88
89        return (E) elements[len - 1];
90    }
91
92    //扩容
93    private void grow() {
94        //将之前的数组保存
95        int oldCapacity = elements.length;
96        Object[] old = elements;
97
98        //新的数组大小为原来数组大小的2倍
99        int newCapacity = oldCapacity * 2;
100        //再新建一个大小为原来数组2倍的新数组
101        elements = new Object[newCapacity];
102
103        //把以前的老的数组中的元素都移动新数组中
104        for (int i = 0; i < oldCapacity; i++) {
105            elements[i] = old[i];
106        }
107
108        //释放以前的内存空间
109        old = null;
110    }
111
112}
113
114

以上面可知：用数组实现栈结构，主要需要注意以下 2 点：

在数组的尾部插入和删除，也就是压栈和弹栈
由于是用数组实现栈结构，数组满的时候，需要扩容

下面我们写一段测试代码来测试,如下：

1
2   public static void main(String[] args){
3        //创建一个栈
4        QStack<String> stack = new QStack<>();
5        
6        //分别向栈中压入4个不同的元素
7        stack.push("tom");
8        stack.push("jim");
9        stack.push("wendy");
10        stack.push("natasha");
11
12        //分别弹栈
13        System.out.println(stack.pop());
14        System.out.println(stack.pop());
15        System.out.println(stack.pop());
16        System.out.println(stack.pop());
17    }
18

打印如下：

1
2natasha
3wendy
4jim
5tom

5 手写Java Stack 核心源码

评论区

相关推荐