| layout | category | title | tagline | tag | excerpt | lock | ||
|---|---|---|---|---|---|---|---|---|
post |
interview |
面经手册 · 第9篇《队列是什么？什么是双端队列、延迟对列、阻塞队列，全是知识盲区！》 |
by 小傅哥 |
|
去厨房🥣叫进栈「LIFO」，上厕所🚽叫入队列「FIFO」，那双端队列呢？都是知识盲区！快点上车🚌吧！🤦🏻♂数组、链表、栈、队列、散列表、树、堆、图，都是基本的数据结构，它们可以有多个特性也可以组合，例如；LinkedList既是链表也是队列，HashMap中用到了散列表、数组、队列、树的组合等等。 |
need |
作者：小傅哥
博客：https://bugstack.cn
沉淀、分享、成长，让自己和他人都能有所收获！😄
买房子最重要的是房屋格局！
如果买房子能接受地理位置、平米价格外，最重要的就是房屋格局。什么？丈母娘！你🤦🏻♂，出去！ 房屋的格局其实对应的就是程序开发的根本，也就是数据结构。有的土豪可以用钱换空间，房间格局更大，那没钱的就只能选经济小空间节省钱。是不是很像不同的数据结构，直接影响着是空间换时间，还是时间换空间。那么，再细看房间，如；客厅沙发坐人像散列表、去厨房🥣叫进栈「LIFO」、上厕所🚽叫入队列「FIFO」、晚上各回各屋子像进数组。所以你能在这个屋子生活的舒服，很大一部分取决于整个房间的布局。也同样你能把程序写好，很大的原因是因为数据结构定义的合理。
那么决定这程序开发基础数据结构有哪些呢？
程序开发中数据结构可以分为这八类；数组、链表、栈、队列、散列表、树、堆、图。其中，数组、链表、散列表、树是程序开发直接或者间接用到的最多的。相关的对应实现类可以包括如下；
| 类型 | 实现 | 文章 |
|---|---|---|
| 数组 | ArrayList | ArrayList也这么多知识？一个指定位置插入就把谢飞机面晕了！ |
| 链表 | LinkedList | LinkedList插入速度比ArrayList快？你确定吗？ |
| 树 | 2-3树、红黑树 | 看图说话，讲解2-3平衡树「红黑树的前身」 红黑树操作原理，解析什么时候染色、怎么进行旋转、与2-3树有什么关联 |
| 散列表 | HashMap | HashMap核心知识，扰动函数、负载因子、扩容链表拆分，深度学习 HashMap数据插入、查找、删除、遍历，源码分析 |
| 栈 | Stack<String> |
|
| 队列 | Queue<String>、Deque<String> |
- 如上，除了栈和队列外，小傅哥已经编写了非常细致的文章来介绍了其他数据结构的核心知识和具体的实现应用。
- 接下来就把剩下的栈和队列在本章介绍完，其实这部分知识并不难了，有了以上对数组和链表的理解，其他的数据结构基本都从这两方面扩展出来的。
本文涉及了较多的代码和实践验证图稿，欢迎关注公众号：bugstack虫洞栈，回复下载得到一个链接打开后，找到ID：19🤫获取！
谢飞机，飞机你旁边这是？
答：啊，谢坦克，我弟弟。还没毕业，想来看看大公司面试官的容颜。
问：飞机，上次把LinkedList都看了吧，那我问你哈。LinkedList可以当队列用吗？
答：啊？可以，可以吧！
问：那，数组能当队列用吗？不能？对列有啥特点吗？
答：队列先进先出，嗯，嗯。
问：还有吗？了解延时队列吗？双端队列呢？
飞机拉着坦克的手出门了，还带走了面试官送的一本《面经手册》，坦克对飞机说，基础不牢，地动山摇，我要好好学习。
把我们已经掌握了的数组和链表立起来，就是栈和队列了！
如图，这一章节的数据结构的知识点并不难，只要已经学习过数组和链表，那么对于掌握其他数据结构就已经有了基础，只不过对于数据的存放、读取加了一些限定规则。尤其像链表这样的数据结构，只操作头尾的效率是非常高的。
有时候不会反而不会犯错误！怕就怕在只知道一知半解。
抛弃的不是栈这种数据结构，而是Stack实现类，如果你还不了解就用到业务开发中，就很可能会影响系统性能。其实Stack这个栈已经是不建议使用了，但是为什么不建议使用，我们可以通过使用和源码分析了解下根本原因。
在学习之前先大概的了解下这样的数据结构，它很像羽毛球的摆放，是一种后进先出队列，如下；
@Test
public void test_stack() {
Stack<String> s = new Stack<String>();
s.push("aaa");
s.push("bbb");
s.push("ccc");
System.out.println("获取最后一个元素：" + s.peek());
System.out.println("获取最后一个元素：" + s.lastElement());
System.out.println("获取最先放置元素：" + s.firstElement());
System.out.println("弹出一个元素[LIFO]：" + s.pop());
System.out.println("弹出一个元素[LIFO]：" + s.pop());
System.out.println("弹出一个元素[LIFO]：" + s.pop());
}例子是对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、offerFirst、addFirst，头插方法，效果一致、offerLast、addLast，尾插方法，这样两端都满足后进先出。- 整体来看，双端队列，就是一个环形。所以扩容后继续插入元素也满足后进先出。
@Test
public void test_ArrayDeque() {
Deque<String> deque = new ArrayDeque<String>(1);
deque.push("a");
deque.push("b");
deque.push("c");
deque.push("d");
deque.offerLast("e");
deque.offerLast("f");
deque.offerLast("g");
deque.offerLast("h"); // 这时候扩容了
deque.push("i");
deque.offerLast("j");
System.out.println("数据出栈：");
while (!deque.isEmpty()) {
System.out.print(deque.pop() + " ");
}
}以上这部分代码就是与上图的展现是一致的，按照图中的分析我们看下输出结果，如下；
数据出栈：
i d c b a e f g h j
Process finished with exit code 0i 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
- ...
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}其实以上这部分源码，就是进行两倍*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，数据结构：
@Test
public void test_Deque_LinkedList(){
Deque<String> deque = new LinkedList<>();
deque.push("a");
deque.push("b");
deque.push("c");
deque.push("d");
deque.offerLast("e");
deque.offerLast("f");
deque.offerLast("g");
deque.offerLast("h");
deque.push("i");
deque.offerLast("j");
System.out.println("数据出栈：");
while (!deque.isEmpty()) {
System.out.print(deque.pop() + " ");
}
}测试结果：
数据出栈：
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时，总是等待最先休眠完成的元素。 - 这里会最小化的空等时间，提高线程利用率。数据结构讲完后，后面会有专门章节介绍
| 类型 | 实现 | 描述 |
|---|---|---|
| Queue | LinkedBlockingQueue | 由链表结构组成的有界阻塞队列 |
| Queue | ArrayBlockingQueue | 由数组结构组成的有界阻塞队列 |
| Queue | PriorityBlockingQueue | 支持优先级排序的无界阻塞队列 |
| Queue | SynchronousQueue | 不存储元素的阻塞队列 |
| Queue | LinkedTransferQueue | 由链表结构组成的无界阻塞队列 |
| Deque | LinkedBlockingDeque | 由链表结构组成的双向阻塞队列 |
| Deque | ConcurrentLinkedDeque | 由链表结构组成的线程安全的双向阻塞队列 |
- 除了我们已经讲过的队列以外，剩余的基本都是阻塞队列，也就是上面这些。
- 在数据结构方面基本没有差异，只不过添加了相应的阻塞功能和锁的机制。
public class DataQueueStack {
private BlockingQueue<DataBean> dataQueue = null;
public DataQueueStack(){
//实例化队列
dataQueue = new LinkedBlockingQueue<DataBean>(100);
}
/**
* 添加数据到队列
* @param dataBean
* @return
*/
public boolean doOfferData(DataBean dataBean){
try {
return dataQueue.offer(dataBean, 2, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
return false;
}
}
/**
* 弹出队列数据
* @return
*/
public DataBean doPollData(){
try {
return dataQueue.poll(2, TimeUnit.SECONDS);
} catch (InterruptedException e) {
e.printStackTrace();
return null;
}
}
/**
* 获得队列数据个数
* @return
*/
public int doGetQueueCount(){
return dataQueue.size();
}
}- 这是一个
LinkedBlockingQueue队列使用案例，一方面存储数据，一方面从队列中获取进行消费。 - 因为这是一个阻塞队列，所以在获取元素的时候，如果队列为空，会进行阻塞。
LinkedBlockingQueue是一个阻塞队列，内部由两个ReentrantLock来实现出入队列的线程安全，由各自的Condition对象的await和signal来实现等待和唤醒功能。
- 关于栈和队列的数据结构方面到这里就介绍完了，另外这里还有一些关于阻塞队列锁🔒的应用过程，到我们后面讲锁相关知识点，再重点介绍。
- 队列结构的设计非常适合某些需要
LIFO或者FIFO的应用场景，同时在队列的数据结构中也有双端、延时和组合的功能类，使用起来也非常方便。 - 数据结构方面的知识到本章节算是告一段落，如果有优秀的内容，后面还会继续补充。再下一章节小傅哥(bugstack.cn)准备给大家介绍，关于数据结构中涉及的算法部分，这些主要来自于
Collections类的实现部分。