作者:小傅哥
博客:https://bugstack.cn
❝沉淀、分享、成长,让自己和他人都能有所收获!😜
❞
一、前言
二、面试题
三、数据结构
四、源码学习
1. 先说一个被抛弃Stack
2. 双端队列ArrayDeque
3. 双端队列LinkedList
4. 延时队列DelayQueue
5. 还有哪些队列?
五、总结
买房子最重要的是房屋格局!
如果买房子能接受地理位置、平米价格外,最重要的就是房屋格局。什么?丈母娘!你🤦🏻♂,出去! 房屋的格局其实对应的就是程序开发的根本,也就是数据结构。有的土豪可以用钱换空间,房间格局更大,那没钱的就只能选经济小空间节省钱。是不是很像不同的数据结构,直接影响着是空间换时间,还是时间换空间。那么,再细看房间,如;客厅沙发坐人像散列表、上卫生间像进栈、厨房不大先进后出像队列、晚上各回各屋子像进数组。所以你能在这个屋子生活的舒服,很大一部分取决于整个房间的布局。也同样你能把程序写好,很大的原因是因为数据结构定义的合理。
那么决定这程序开发基础数据结构有哪些呢?
程序开发中数据结构可以分为这八类;数组
、链表
、栈
、队列
、散列表
、树
、堆
、图
。其中,数组、链表、散列表、树是程序开发直接或者间接用到的最多的。相关的对应实现类可以包括如下;
类型 | 实现 | 文章 |
---|---|---|
数组 | ArrayList | ArrayList也这么多知识?一个指定位置插入就把谢飞机面晕了! |
链表 | LinkedList | LinkedList插入速度比ArrayList快?你确定吗? |
树 | 2-3树、红黑树 | 看图说话,讲解2-3平衡树「红黑树的前身」 红黑树操作原理,解析什么时候染色、怎么进行旋转、与2-3树有什么关联 |
散列表 | HashMap | HashMap核心知识,扰动函数、负载因子、扩容链表拆分,深度学习 HashMap数据插入、查找、删除、遍历,源码分析 |
栈 | Stack | |
队列 | Queue |
本文涉及了较多的代码和实践验证图稿,欢迎关注公众号: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
看到测试结果,与你想的答案是否一致?
ccc
。我们说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
,向头部插入,这样两端都满足后进先出。@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 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;
}
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开始,往上增加。doubleCapacity
。下标计算:head = (head - 1) & (elements.length - 1)
:
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
从测试结果可以看到;
System.arraycopy(elements, p, a, 0, r);
,「d、c、b、a」,落入新数组。System.arraycopy(elements, 0, a, r, p);
,「e、f、g、h」,落入新数组。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
「入栈:」: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
是基于数组实现的,所以可以动态扩容,另外它插入元素的顺序并不影响最终的输出顺序。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
的应用场景,同时在队列的数据结构中也有双端、延时和组合的功能类,使用起来也非常方便。Collections
类的实现部分。bugstack虫洞栈
沉淀、分享、成长,让自己和他人都能有所收获!
联系客服