作者：小傅哥 博客：https://bugstack.cn
沉淀、分享、成长，让自己和他人都能有所收获！😄
买房子最重要的是房屋格局！
如果买房子能接受地理位置、平米价格外，最重要的就是房屋格局。什么？丈母娘！你🤦🏻♂，出去！ 房屋的格局其实对应的就是程序开发的根本，也就是数据结构。有的土豪可以用钱换空间，房间格局更大，那没钱的就只能选经济小空间节省钱。是不是很像不同的数据结构，直接影响着是空间换时间，还是时间换空间。那么，再细看房间，如；客厅沙发坐人像散列表、去厨房🥣叫进栈「LIFO」、上厕所🚽叫入队列「FIFO」、晚上各回各屋子像进数组。所以你能在这个屋子生活的舒服，很大一部分取决于整个房间的布局。也同样你能把程序写好，很大的原因是因为数据结构定义的合理。
那么决定这程序开发基础数据结构有哪些呢？
程序开发中数据结构可以分为这八类；数组、链表、栈、队列、散列表、树、堆、图。其中，数组、链表、散列表、树是程序开发直接或者间接用到的最多的。相关的对应实现类可以包括如下；
类型实现文章数组ArrayListArrayList也这么多知识？一个指定位置插入就把谢飞机面晕了！链表LinkedListLinkedList插入速度比ArrayList快？你确定吗？树2-3树、红黑树看图说话，讲解2-3平衡树「红黑树的前身」 红黑树操作原理，解析什么时候染色、怎么进行旋转、与2-3树有什么关联散列表HashMapHashMap核心知识，扰动函数、负载因子、扩容链表拆分，深度学习HashMap数据插入、查找、删除、遍历，源码分析栈Stack队列Queue、Deque 如上，除了栈和队列外，小傅哥已经编写了非常细致的文章来介绍了其他数据结构的核心知识和具体的实现应用。接下来就把剩下的栈和队列在本章介绍完，其实这部分知识并不难了，有了以上对数组和链表的理解，其他的数据结构基本都从这两方面扩展出来的。本文涉及了较多的代码和实践验证图稿，欢迎关注公众号：bugstack虫洞栈，回复下载得到一个链接打开后，找到ID：19🤫获取！
谢飞机，飞机你旁边这是？
答：啊，谢坦克，我弟弟。还没毕业，想来看看大公司面试官的容颜。
问：飞机，上次把LinkedList都看了吧，那我问你哈。LinkedList可以当队列用吗？
答：啊？可以，可以吧！
问：那，数组能当队列用吗？不能？对列有啥特点吗？
答：队列先进先出，嗯，嗯。
问：还有吗？了解延时队列吗？双端队列呢？
飞机拉着坦克的手出门了，还带走了面试官送的一本《面经手册》，坦克对飞机说，基础不牢，地动山摇，我要好好学习。
把我们已经掌握了的数组和链表立起来，就是栈和队列了！
如图，这一章节的数据结构的知识点并不难，只要已经学习过数组和链表，那么对于掌握其他数据结构就已经有了基础，只不过对于数据的存放、读取加了一些限定规则。尤其像链表这样的数据结构，只操作头尾的效率是非常高的。
有时候不会反而不会犯错误！怕就怕在只知道一知半解。
抛弃的不是栈这种数据结构，而是Stack实现类，如果你还不了解就用到业务开发中，就很可能会影响系统性能。其实Stack这个栈已经是不建议使用了，但是为什么不建议使用，我们可以通过使用和源码分析了解下根本原因。
在学习之前先大概的了解下这样的数据结构，它很像羽毛球的摆放，是一种后进先出队列，如下；
例子是对Stack栈的使用，如果不运行你能知道它的输出结果吗？
测试结果：
获取最后一个元素：ccc 获取最后一个元素：ccc 获取最先放置元素：aaa 弹出一个元素[LIFO]：ccc 弹出一个元素[LIFO]：bbb 弹出一个元素[LIFO]：aaa Process finished with exit code 0看到测试结果，与你想的答案是否一致？
peek，是偷看的意思，就是看一下，不会弹出元素。满足后进先出的规则，它看的是最后放进去的元素ccc。lastElement、firstElement，字面意思的方法，获取最后一个和获取第一个元素。pop，是队列中弹出元素，弹出后也代表着要把属于这个位置都元素清空，删掉。我们说Stack栈，这个实现类已经不推荐使用了，需要从它的源码上看。
/** * * <p>A more complete and consistent set of LIFO stack operations is * provided by the {@link Deque} interface and its implementations, which * should be used in preference to this class. For example: * <pre> {@code * Deque<Integer> stack = new ArrayDeque<Integer>();}</pre> * * @author Jonathan Payne * @since JDK1.0 */ public class Stack<E> extends Vector<E> s.push("aaa"); public synchronized void addElement(E obj) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = obj; } Stack 栈是在JDK1.0时代时，基于继承Vector，实现的。本身Vector就是一个不推荐使用的类，主要在于它的一些操作方法锁🔒(synchronized)的力度太粗，都是放到方法上。Stack 栈底层是使用Vector数组实现，在学习ArrayList时候我们知道，数组结构在元素添加和擅长需要通过System.arraycopy，进行扩容操作。而本身栈的特点是首尾元素的操作，也不需要遍历，使用数组结构其实并不太理想。同时在这个方法的注释上也明确标出来，推荐使用Deque<Integer> stack = new ArrayDeque<Integer>();，虽然这也是数组结构，但是它没有粗粒度的锁，同时可以申请指定空间并且在扩容时操作时也要优于Stack 。并且它还是一个双端队列，使用起来更灵活。ArrayDeque 是基于数组实现的可动态扩容的双端队列，也就是说你可以在队列的头和尾同时插入和弹出元素。当元素数量超过数组初始化长度时，则需要扩容和迁移数据。
数据结构和操作，如下；
从上图我们可以了解到如下几个知识点；
双端队列是基于数组实现，所以扩容迁移数据操作。push，像结尾插入、offerLast，向头部插入，这样两端都满足后进先出。整体来看，双端队列，就是一个环形。所以扩容后继续插入元素也满足后进先出。以上这部分代码就是与上图的展现是一致的，按照图中的分析我们看下输出结果，如下；
数据出栈： i d c b a e f g h j Process finished with exit code 0 i d c b a e f g h j，正好满足了我们的说的数据出栈顺序。可以参考上图再进行理解ArrayDeque 这种双端队列是基于数组实现的，所以源码上从初始化到数据入栈扩容，都会有数组操作的痕迹。接下来我们就依次分析下。
new ArrayDeque<String>(1);，其实它的构造函数初始化默认也提供了几个方法，比如你可以指定大小以及提供默认元素。
private static int calculateSize(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 element } return initialCapacity; } 在初始化的过程中，它需要找到你当前传输值最小的2的倍数的一个容量。这与HashMap的初始化过程相似。deque.push("a");，ArrayDeque，提供了一个 push 方法，这个方法与deque.offerFirst(“a”)，一致，因为它们的底层源码是一样的，如下；
addFirst：
public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); }addLast：
public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); }这部分入栈元素，其实就是给数组赋值，知识点如下；
在addFirst()中，定位下标，head = (head - 1) & (elements.length - 1)，因为我们的数组长度是2^n的倍数，所以 2^n - 1 就是一个全是1的二进制数，可以用于与运算得出数组下标。同样addLast()中，也使用了相同的方式定位下标，只不过它是从0开始，往上增加。最后，当头(head)与尾(tile)，数组则需要两倍扩容doubleCapacity。下标计算：head = (head - 1) & (elements.length - 1)：
(0 - 1) & (8 - 1) = 7(7 - 1) & (8 - 1) = 6(6 - 1) & (8 - 1) = 5…其实以上这部分源码，就是进行两倍n << 1扩容，同时把两端数据迁移进新的数组，整个操作过程也与我们上图对应。为了更好的理解，我们单独把这部分代码做一些测试。
测试代码：
@Test public void test_arraycopy() { int head = 0, tail = 0; Object[] elements = new Object[8]; elements[head = (head - 1) & (elements.length - 1)] = "a"; elements[head = (head - 1) & (elements.length - 1)] = "b"; elements[head = (head - 1) & (elements.length - 1)] = "c"; elements[head = (head - 1) & (elements.length - 1)] = "d"; elements[tail] = "e"; tail = (tail + 1) & (elements.length - 1); elements[tail] = "f"; tail = (tail + 1) & (elements.length - 1); elements[tail] = "g"; tail = (tail + 1) & (elements.length - 1); elements[tail] = "h"; tail = (tail + 1) & (elements.length - 1); System.out.println("head：" + head); System.out.println("tail：" + tail); int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p // 输出当前的元素 System.out.println(JSON.toJSONString(elements)); // head == tail 扩容 Object[] a = new Object[8 << 1]; System.arraycopy(elements, p, a, 0, r); System.out.println(JSON.toJSONString(a)); System.arraycopy(elements, 0, a, r, p); System.out.println(JSON.toJSONString(a)); elements = a; head = 0; tail = n; a[head = (head - 1) & (a.length - 1)] = "i"; System.out.println(JSON.toJSONString(a)); }以上的测试过程主要模拟了8个长度的空间的数组，在进行双端队列操作时数组扩容，数据迁移操作，可以单独运行，测试结果如下；
head：4 tail：4 ["e","f","g","h","d","c","b","a"] ["d","c","b","a",null,null,null,null,null,null,null,null,null,null,null,null] ["d","c","b","a","e","f","g","h",null,null,null,null,null,null,null,null] ["d","c","b","a","e","f","g","h","j",null,null,null,null,null,null,"i"] Process finished with exit code 0从测试结果可以看到；
当head与tail相等时，进行扩容操作。第一次数据迁移，System.arraycopy(elements, p, a, 0, r);，d、c、b、a，落入新数组。第二次数据迁移，System.arraycopy(elements, 0, a, r, p);，e、f、g、h，落入新数组。最后再尝试添加新的元素，i和j。每一次的输出结果都可以看到整个双端链路的变化。Linkedlist天生就可以支持双端队列，而且从头尾取数据也是它时间复杂度O(1)的。同时数据的插入和删除也不需要像数组队列那样拷贝数据，虽然Linkedlist有这些优点，但不能说ArrayDeque因为有数组复制性能比它低。
Linkedlist，数据结构：
测试结果：
数据出栈： i d c b a e f g h j Process finished with exit code 0 测试结果上看与使用ArrayDeque是一样的，功能上没有差异。压栈：deque.push("a");、deque.offerFirst("a");
private void linkFirst(E e) { final Node<E> f = first; final Node<E> newNode = new Node<>(null, e, f); first = newNode; if (f == null) last = newNode; else f.prev = newNode; size++; modCount++; }压栈：deque.offerLast("e");
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } linkFirst、linkLast，两个方法分别是给链表的首尾节点插入元素，因为这是链表结构，所以也不存在扩容，只需要把双向链路链接上即可。你是否有时候需要把一些数据存起来，倒计时到某个时刻在使用？
在Java的队列数据结构中，还有一种队列是延时队列，可以通过设定存放时间，依次轮训获取。
先写一个Delayed的实现类：
public class TestDelayed implements Delayed { private String str; private long time; public TestDelayed(String str, long time, TimeUnit unit) { this.str = str; this.time = System.currentTimeMillis() + (time > 0 ? unit.toMillis(time) : 0); } @Override public long getDelay(TimeUnit unit) { return time - System.currentTimeMillis(); } @Override public int compareTo(Delayed o) { TestDelayed work = (TestDelayed) o; long diff = this.time - work.time; if (diff <= 0) { return -1; } else { return 1; } } public String getStr() { return str; } } 这个相当于延时队列的一个固定模版方法，通过这种方式来控制延时。案例测试：
@Test public void test_DelayQueue() throws InterruptedException { DelayQueue<TestDelayed> delayQueue = new DelayQueue<TestDelayed>(); delayQueue.offer(new TestDelayed("aaa", 5, TimeUnit.SECONDS)); delayQueue.offer(new TestDelayed("ccc", 1, TimeUnit.SECONDS)); delayQueue.offer(new TestDelayed("bbb", 3, TimeUnit.SECONDS)); logger.info(((TestDelayed) delayQueue.take()).getStr()); logger.info(((TestDelayed) delayQueue.take()).getStr()); logger.info(((TestDelayed) delayQueue.take()).getStr()); }测试结果：
01:44:21.000 [main] INFO org.itstack.interview.test.ApiTest - ccc 01:44:22.997 [main] INFO org.itstack.interview.test.ApiTest - bbb 01:44:24.997 [main] INFO org.itstack.interview.test.ApiTest - aaa Process finished with exit code 0 在案例测试中我们分别设定不同的休眠时间，1、3、5，TimeUnit.SECONDS。测试结果分别在21、22、24，输出了我们要的队列结果。队列中的元素不会因为存放的先后顺序而导致输出顺序，它们是依赖于休眠时长决定。入栈：：delayQueue.offer(new TestDelayed("aaa", 5, TimeUnit.SECONDS));
public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; } private void siftUpUsingComparator(int k, E x) { while (k > 0) { int parent = (k - 1) >>> 1; Object e = queue[parent]; if (comparator.compare(x, (E) e) >= 0) break; queue[k] = e; k = parent; } queue[k] = x; } 关于数据存放还有 ReentrantLock 可重入锁🔒，但暂时不是我们本章节数据结构的重点，后面章节会介绍到。DelayQueue 是基于数组实现的，所以可以动态扩容，另外它插入元素的顺序并不影响最终的输出顺序。而元素的排序依赖于compareTo方法进行排序，也就是休眠的时间长短决定的。同时只有实现了Delayed接口，才能存放元素。出栈：delayQueue.take()
public E take() throws InterruptedException { final ReentrantLock lock = this.lock; lock.lockInterruptibly(); try { for (;;) { E first = q.peek(); if (first == null) available.await(); else { long delay = first.getDelay(NANOSECONDS if (delay <= 0) return q.poll(); first = null; // don't retain ref while if (leader != null) available.await(); else { Thread thisThread = Thread.currentT leader = thisThread; try { available.awaitNanos(delay); } finally { if (leader == thisThread) leader = null; } } } } } finally { if (leader == null && q.peek() != null) available.signal(); lock.unlock(); } } 这部分的代码有点长，主要是元素的获取。DelayQueue 是 Leader-Followr 模式的变种，消费者线程处于等待await时，总是等待最先休眠完成的元素。这里会最小化的空等时间，提高线程利用率。数据结构讲完后，后面会有专门章节介绍