Stack 是 Java 中常用的数据结构之一, Stack 具有 "后进先出 (LIFO)" 的性质.
只能在一端进行插入或者删除, 即压栈与出栈
栈的实现比较简单, 性质也简单. 可以用一个数组来实现栈结构.
入栈的时候, 只在数组尾部插入
出栈的时候, 只在数组尾部删除 **
我们来看一下 Stack 的用法 : 如下
- public static void main(String[] args){
- // 新建一个栈
- Stack<String> stack = new Stack<>();
- // 分别向栈中添加不同的元素
- stack.push("tom");
- stack.push("jim");
- stack.push("wendy");
- stack.push("natasha");
- // 分别弹栈
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- }
输出如下:
- natasha
- wendy
- jim
- tom
从输出可以看到, 最后入栈的, 最先出栈
下面我们底层用数组也来实现这样一个栈, 在数组的尾部插入和删除.
也就是入栈和出栈. 如下图:
完整的源码如下:
- public class QStack<E> {
- // 数组的默认大小为 10
- private static final int DEFAULT_INIT_CAPACITY = 10;
- // 底层的数组
- private Object[] elements;
- // 栈中的个数
- private int size;
- public QStack() {
- this(DEFAULT_INIT_CAPACITY);
- }
- public QStack(int capacity) {
- //capacity 条件检查 , 这里我们直接抛出异常
- if (capacity <= 0) {
- throw new IllegalArgumentException("capacity <= 0");
- }
- if (capacity> Integer.MAX_VALUE) {
- throw new IllegalArgumentException("capacity> Integer.MAX_VALUE");
- }
- // 新建一个 capacity 大小的数组
- elements = new Object[capacity];
- // 初始个数为 0
- size = 0;
- }
- // 栈是否为空
- public boolean isEmpty() {
- return size == 0;
- }
- // 返回栈中的元素个数
- public int size() {
- return size;
- }
- // 将一个元素压入栈中
- public E push(E e) {
- // 如果栈已满, 进行扩容
- if (size>= elements.length) {
- grow();
- }
- // 扩容完后将元素 e 压入栈中
- elements[size] = e;
- // 别忘了 size 需要加 1
- size++;
- return e;
- }
- // 出栈, 就是将数组最后一个元素弹出
- public E pop() {
- // 如果栈为空就返回 null
- if (isEmpty()) {
- return null;
- }
- // 拿到栈的大小
- int len = size();
- // 把数组中最后一个元素保存起来
- E e = peek();
- // 个数别忘了减 1
- size--;
- // 将最后一个元素置 null
- elements[len - 1] = null;
- // 返回 e
- return e;
- }
- // 返回最后一个元素
- public E peek() {
- int len = size();
- if (len == 0)
- throw new RuntimeException("stack is empty");
- return (E) elements[len - 1];
- }
- // 扩容
- private void grow() {
- // 将之前的数组保存
- int oldCapacity = elements.length;
- Object[] old = elements;
- // 新的数组大小为原来数组大小的 2 倍
- int newCapacity = oldCapacity * 2;
- // 再新建一个大小为原来数组 2 倍的新数组
- elements = new Object[newCapacity];
- // 把以前的老的数组中的元素都移动新数组中
- for (int i = 0; i <oldCapacity; i++) {
- elements[i] = old[i];
- }
- // 释放以前的内存空间
- old = null;
- }
- }
以上面可知: 用数组实现栈结构, 主要需要注意以下 2 点:
在数组的尾部插入和删除, 也就是压栈和弹栈
由于是用数组实现栈结构, 数组满的时候, 需要扩容
下面我们写一段测试代码来测试, 如下:
- public static void main(String[] args){
- // 创建一个栈
- QStack<String> stack = new QStack<>();
- // 分别向栈中压入 4 个不同的元素
- stack.push("tom");
- stack.push("jim");
- stack.push("wendy");
- stack.push("natasha");
- // 分别弹栈
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- System.out.println(stack.pop());
- }
打印如下:
- natasha
- wendy
- jim
- tom
来源: http://www.bubuko.com/infodetail-2879975.html