一、前言
二、堆栈数据结构
三、实现堆栈结构
1. ArrayDeque 介绍
2. 添加元素
3. 扩容空间
4. 弹出元素
四、堆栈功能测试
五、常见面试问题
一、前言 堆栈的历史
堆栈于 1946 年进入计算机科学文献,当时当时 Alan M. Turing 使用术语“bury”和“unbury”作为调用子程序和从子程序返回的一种方式。1945 年, Konrad Zuse 的 Z4 中已经实现了子程序。
慕尼黑工业大学的 Klaus Samelson 和 Friedrich L. Bauer 在 1955 年提出了堆栈的想法,并于 1957 年申请了专利。1988 年 3 月,其中在萨梅尔森去世时,鲍尔因发明堆栈原理而获得了 IEEE 计算机先锋奖。Charles Leonard Hamblin 在 1954 年上半年和Wilhelm Kämmerer [ de ] 在 1958 年独立开发了类似的概念。
二、堆栈数据结构 在计算机科学中,堆栈是一种抽象数据类型,用作元素的集合,具有两个主要的操作;
堆栈是一种 LIFO(后进先出)的线性的数据结构,或者更抽象说是一种顺序集合,push 和 pop 操作只发生在结构的一端,称为栈顶。这种结构可以很容易地从堆栈顶部取出一个项目,而要到达堆栈更深处的一个项目可能需要先取出多个其他项目。例如;我们经常看到的浏览器访问记录,总是把最近记录展示给你。还包括:一摞书、一叠盘子、一脑瓜子生活琐事。
三、实现堆栈结构 当你真的有场景需要使用后进先出堆栈时,一定是不能使用 Java 提供的 Stack 的。因为这个工具类是在 JDK 1.0 阶段开发的,实现的特别粗糙,包括像 synchronized 锁也是直接加到方法上。同时 JDK Stack 类的注解也提醒,使用 ArrayDeque 替代;
Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作,应优先使用此类。所以我们本章也是以 ArrayDeque 为原型做代码实现。 当小傅哥去翻看 ArrayDeque 时,发现这又是 Doug Lea 老爷子的作品,只要有这大神的存在,这份代码一定很多骚操作! 1. ArrayDeque 介绍 ArrayDeque 是一个基于数组实现的堆栈数据结构,在数据存放时元素通过二进制与运算获取对应的索引存放元素。当数组长度超过初始空间后,进行2的n次幂左移一位扩容,并将数组内容的元素按照分半分别进行迁移。这块逻辑多一些,接下来的内容会以此进行讲解,同时在学习过程中可以在小傅哥提供的源码中完成断点调试,方便快速掌握。
堆栈的数据结构是以2的次幂进行初始化,扩容时候为2的倍数。它之所这样是因为保证了在后续计算元素索引位置时,可以进行与运算。也就说 2的n次幂-1 得到的值是一个011111的范围,在与元素索引位置计算时候,找到两个值之间1的位置即可。 数据的压栈,压榨是一个在数组中倒放的方式,通过与运算得到索引值。当发生空间不足时扩容迁移数据,会有2次操作。一次是空间的前半断复制,另外一次是后半段复制。 最后在数据弹出时,按照空间的元素数量总数开始,同样通过与运算计算索引值。氛围弹出队列中未发生迁移的数据,和已经完全迁移好的数据。凡是迁移的数据,都是保证了一个顺序。 综上你可能还不是很理解这个数据结构的精妙设计和使用,接下来小傅哥再带着你从代码实现的角度来看下。 2. 添加元素 源码详见 :cn.bugstack.algorithms.data.stack.ArrayDeque#push
public void push (E e) { if (e == null ) throw new NullPointerException(); elements[head = (head - 1 ) & (elements.length - 1 )] = e; logger.info("push.idx head:{}" , head); if (head == tail) doubleCapacity(); }
push 元素的过程相当于找到初始化数组长度的队尾,另外是扩容后从新的队尾开始依次添加元素。此时不用担心元素的输出,因为输出时是从扩容起始点开始输出元素。 3. 扩容空间 源码详见 :cn.bugstack.algorithms.data.stack.ArrayDeque#doubleCapacity
private void doubleCapacity () { assert head == tail; int p = head; int n = elements.length; int r = n - p; int newCapacity = n << 1 ; if (newCapacity < 0 ) throw new IllegalStateException("Sorry, deque too big" ); Object[] a = new Object[newCapacity]; /* * src - 源数组 * srcPos – 源数组中的起始位置 * dest - 目标数组 * destPos – 目标数据中的起始位置 * length – 要复制的数组元素的数量 */ // 第一次拷贝元素:[2、1、4、3] 将数组中的扩容后一半元素拷贝到新数组0开始往后的位置。拷贝4、3 System.arraycopy(elements, p, a, 0 , r); // 第二次拷贝元素:[2、1、4、3] 将数组中的前面一半数量的元素,拷贝到新数组后一半开始的位置往后。拷贝2、1 System.arraycopy(elements, 0 , a, r, p); elements = a; head = 0 ; tail = n; }
System.arraycopy 是操作数据迁移的本地方法,从源数组的某个指定位置,把元素迁移到新数组的指定位置和指定个数个元素。 第一次拷贝元素:[2、1、4、3] 将数组中的扩容后一半元素拷贝到新数组0开始往后的位置。拷贝4、3 第二次拷贝元素:[2、1、4、3] 将数组中的前面一半数量的元素,拷贝到新数组后一半开始的位置往后。拷贝2、1 4. 弹出元素 源码详见 :cn.bugstack.algorithms.data.stack.ArrayDeque#pop
public E pop () { int h = head; @SuppressWarnings ("unchecked" ) E result = (E) elements[h]; if (result == null ) { return null ; } elements[h] = null ; head = (h + 1 ) & (elements.length - 1 ); logger.info("pop.idx {} = {} & {}" , head, Integer.toBinaryString(h + 1 ), Integer.toBinaryString(elements.length - 1 )); return result; }
按照索引的计算,以此是弹出索引为:6、7、0、1、2、3、4 对应的元素。head 的值从扩容的长度添加元素后逐步减小,所以当前最开始弹出的元素是6索引对应的值。读者可以尝试在添加一个元素,进行验证 四、堆栈功能测试 @Test public void test_stack () { Deque<Integer> deque = new ArrayDeque<>(); deque.push(1 ); deque.push(2 ); deque.push(3 ); deque.push(4 ); deque.push(5 ); deque.push(6 ); deque.push(7 ); logger.info("弹出元素:{}" , deque.pop()); logger.info("弹出元素:{}" , deque.pop()); logger.info("弹出元素:{}" , deque.pop()); logger.info("弹出元素:{}" , deque.pop()); logger.info("弹出元素:{}" , deque.pop()); logger.info("弹出元素:{}" , deque.pop()); }
测试结果
07 :09 :49.407 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:1 07 :09 :49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:0 07 :09 :49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:3 07 :09 :49.412 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:2 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:7 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:6 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - push.idx head:5 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 6 = 110 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:7 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 7 = 111 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:6 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 0 = 1000 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:5 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 1 = 1 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:4 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 2 = 10 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:3 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.data.stack.ArrayDeque - pop.idx 3 = 11 & 111 07 :09 :49.413 [main] INFO cn.bugstack.algorithms.test.AlgorithmsTest - 弹出元素:2
从测试结果中可以看到小傅哥添加的日志,打印出所应的添加元素、弹出元素的过程。读者在学习的过程中也可以添加一些额外的日志信息。 Integer.toBinaryString()
是一个用于打印二进制结果的操作,方便查看二进制的计算。五、常见面试问题 ArrayDeque 为什么要初始化2的n次幂个长度?