w66利来登录w66利来登录

最给力利来老牌网站
w66利来平台

5 手写Java Stack 核心源码

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()); }

输出如下:

natashawendyjimtom

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

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

完整的源码如下:

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()); }

打印如下:

natashawendyjimtom

欢迎阅读本文章: 陈明铭

利来w66官网官方下载

千赢网址