4 堆栈(栈)Stack
4.1 简介
堆栈是一种抽象数据类型,用作元素的集合,具有两个主要的操作:
- PUSH:将元素添加到集合
- POP:删除最近添加但尚未删除的元素
堆栈是一种 LIFO(后进先出)的线性的数据结构,或者更抽象说是一种顺序集合,push 和 pop 操作只发生在结构的一端,称为栈顶。这种结构可以很容易地从堆栈顶部取出一个项目,而要到达堆栈更深处的一个项目可能需要先取出多个其它项
4.2 实现
Deque 接口及其实现提供了一组更完整和一致的 LIFO 堆栈操作,应优先使用此类。所以我们本章也是以 ArrayDeque 为原型做代码实现
当你真的有场景需要使用后进先出堆栈时,一定是不能使用 Java 提供的 Stack 的。因为这个工具类是在 JDK 1.0 阶段开发的,实现的特别粗糙,包括像 synchronized 锁也是直接加到方法上。同时 JDK Stack 类的注解也提醒,使用 ArrayDeque 替代
4.2.1 ArrayDeque
基于数组实现的堆栈数据结构,在数据存放时元素通过二进制与运算获取对应的索引存放元素。当数组长度超过初始空间后,进行2的n次幂左移一位扩容,并将数组内容的元素按照分半分别进行迁移
- 堆栈的数据结构是以2的次幂进行初始化,扩容时候为2的倍数。它之所这样是因为保证了在后续计算元素索引位置时,可以进行与运算。也就说 2的n次幂-1 得到的值是一个011111的范围,在与元素索引位置计算时候,找到两个值之间1的位置即可
- 数据的压栈,压栈是一个在数组中倒放的方式,通过与运算得到索引值。当发生空间不足时扩容迁移数据,会有2次操作。一次是空间的前半段复制,另外一次是后半段复制
- 最后在数据弹出时,按照空间的元素数量总数开始,同样通过与运算计算索引值。分为弹出队列中未发生迁移的数据,和已经完全迁移好的数据。凡是迁移的数据,都是保证了一个顺序
4.2.2 添加元素
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 元素的过程相当于找到初始化数组长度的队尾
- 扩容后从新的队尾开始依次添加元素。此时不用担心元素的输出,因为输出时是从扩容起始点开始输出元素
4.2.3 扩容空间
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;
}
- 空间扩容以2的倍数进行操作,以此保证2的幂等。
- System.arraycopy 是操作数据迁移的本地方法,从源数组的某个指定位置,把元素迁移到新数组的指定位置和指定个数个元素。
- 另外是数据迁移,以 [2、1、4、3] 举例;
- 第一次拷贝元素:[2、1、4、3] 将数组中的扩容后一半元素拷贝到新数组0开始往后的位置。拷贝4、3
- 第二次拷贝元素:[2、1、4、3] 将数组中的前面一半数量的元素,拷贝到新数组后一半开始的位置往后。拷贝2、1
4.2.4 弹出元素
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索引对应的值
4.2.5 测试
@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());
}
Run
INFO - push.idx head:1
INFO - push.idx head:0
INFO - push.idx head:3
INFO - push.idx head:2
INFO - push.idx head:7
INFO - push.idx head:6
INFO - push.idx head:5
INFO - pop.idx 6 = 110 & 111
INFO - 弹出元素:7
INFO - pop.idx 7 = 111 & 111
INFO - 弹出元素:6
INFO - pop.idx 0 = 1000 & 111
INFO - 弹出元素:5
INFO - pop.idx 1 = 1 & 111
INFO - 弹出元素:4
INFO - pop.idx 2 = 10 & 111
INFO - 弹出元素:3
INFO - pop.idx 3 = 11 & 111
INFO - 弹出元素:2
4.3 常见面试问题
-
堆栈的使用场景?
- 需要使用先入后出的数据结构的场景
-
为什么不是用 Stack 类?
- Stack十分粗糙,效率低下(见 4.2 引用)
-
ArrayDeque 是基于什么实现的?
- 数组(见 4.2.1)
-
ArrayDeque 数据结构使用过程叙述
- 回顾 4.2(见 4.2)
-
ArrayDeque 为什么要初始化2的n次幂个长度?
- 为了便于进行无符号取模(2^n - 1)得到索引