一、双向队列Deque
Queue除了前面介绍的实现外,还有一种双向的Queue实现Deque。这种队列允许在队列头和尾部进行入队出队操作,因此在功能上比Queue显然要更复杂。下图描述的是Deque的完整体系图。需要说明的是LinkedList也已经加入了Deque的一部分(LinkedList是从jdk1.2 开始就存在数据结构)。
Deque在Queue的基础上增加了更多的操作方法。
从上图可以看到,Deque不仅具有FIFO的Queue实现,也有FILO的实现,也就是不仅可以实现队列,也可以实现一个堆栈。
同时在Deque的体系结构图中可以看到,实现一个Deque可以使用数组(ArrayDeque),同时也可以使用链表(LinkedList),还可以同实现一个支持阻塞的线程安全版本队列LinkedBlockingDeque。
1、ArrayDeque实现Deque
对于数组实现的Deque来说,数据结构上比较简单,只需要一个存储数据的数组以及头尾两个索引即可。由于数组是固定长度的,所以很容易就得到数组的头和尾,那么对于数组的操作只需要移动头和尾的索引即可。
特别说明的是ArrayDeque并不是一个固定大小的队列,每次队列满了以后就将队列容量扩大一倍(doubleCapacity()),因此加入一个元素总是能成功,而且也不会抛出一个异常。也就是说ArrayDeque是一个没有容量限制的队列。
同样继续性能的考虑,使用System.arraycopy复制一个数组比循环设置要高效得多。
1.1、ArrayDeque的源码解析
- //数组双端队列ArrayDeque的源码解析
- public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{
- /**
- * 存放队列元素的数组,数组的长度为“2的指数”
- */
- private transient E[] elements;
- /**
- *队列的头部索引位置,(被remove()或pop()操作的位置),当为空队列时,首尾index相同
- */
- private transient int head;
- /**
- * 队列的尾部索引位置,(被 addLast(E), add(E), 或 push(E)操作的位置).
- */
- private transient int tail;
- /**
- * 队列的最小容量(大小必须为“2的指数”)
- */
- private static final int MIN_INITIAL_CAPACITY = 8;
- // ****** Array allocation and resizing utilities ******
- /**
- * 根据所给的数组长度,得到一个比该长度大的最小的2^p的真实长度,并建立真实长度的空数组
- */
- private void allocateElements(int numElements) {
- int initialCapacity = MIN_INITIAL_CAPACITY;
- 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 elements
- }
- elements = (E[]) new Object[initialCapacity];
- }
- /**
- * 当队列首尾指向同一个引用时,扩充队列的容量为原来的两倍,并对元素重新定位到新数组中
- */
- 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 = (E[])a;
- head = 0;
- tail = n;
- }
- /**
- * 拷贝队列中的元素到新数组中
- */
- private <T> T[] copyElements(T[] a) {
- if (head < tail) {
- System.arraycopy(elements, head, a, 0, size());
- } else if (head > tail) {
- int headPortionLen = elements.length - head;
- System.arraycopy(elements, head, a, 0, headPortionLen);
- System.arraycopy(elements, 0, a, headPortionLen, tail);
- }
- return a;
- }
- /**
- * 默认构造队列,初始化一个长度为16的数组
- */
- public ArrayDeque() {
- elements = (E[]) new Object[16];
- }
- /**
- * 指定元素个数的构造方法
- */
- public ArrayDeque(int numElements) {
- allocateElements(numElements);
- }
- /**
- * 用一个集合作为参数的构造方法
- */
- public ArrayDeque(Collection<? extends E> c) {
- allocateElements(c.size());
- addAll(c);
- }
- //插入和删除的方法主要是: addFirst(),addLast(), pollFirst(), pollLast()。
- //其他的方法依赖于这些实现。
- /**
- * 在双端队列的前端插入元素,元素为null抛异常
- */
- public void addFirst(E e) {
- if (e == null)
- throw new NullPointerException();
- elements[head = (head - 1) & (elements.length - 1)] = e;
- if (head == tail)
- doubleCapacity();
- }
- /**
- *在双端队列的末端插入元素,元素为null抛异常
- */
- public void addLast(E e) {
- if (e == null)
- throw new NullPointerException();
- elements[tail] = e;
- if ( (tail = (tail + 1) & (elements.length - 1)) == head)
- doubleCapacity();
- }
- /**
- * 在前端插入,调用addFirst实现,返回boolean类型
- */
- public boolean offerFirst(E e) {
- addFirst(e);
- return true;
- }
- /**
- * 在末端插入,调用addLast实现,返回boolean类型
- */
- public boolean offerLast(E e) {
- addLast(e);
- return true;
- }
- /**
- * 删除前端,调用pollFirst实现
- */
- public E removeFirst() {
- E x = pollFirst();
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- /**
- * 删除后端,调用pollLast实现
- */
- public E removeLast() {
- E x = pollLast();
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- //前端出对(删除前端)
- public E pollFirst() {
- int h = head;
- E result = elements[h]; // Element is null if deque empty
- if (result == null)
- return null;
- elements[h] = null; // Must null out slot
- head = (h + 1) & (elements.length - 1);
- return result;
- }
- //后端出对(删除后端)
- public E pollLast() {
- int t = (tail - 1) & (elements.length - 1);
- E result = elements[t];
- if (result == null)
- return null;
- elements[t] = null;
- tail = t;
- return result;
- }
- /**
- * 得到前端头元素
- */
- public E getFirst() {
- E x = elements[head];
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- /**
- * 得到末端尾元素
- */
- public E getLast() {
- E x = elements[(tail - 1) & (elements.length - 1)];
- if (x == null)
- throw new NoSuchElementException();
- return x;
- }
- public E peekFirst() {
- return elements[head]; // elements[head] is null if deque empty
- }
- public E peekLast() {
- return elements[(tail - 1) & (elements.length - 1)];
- }
- /**
- * 移除此双端队列中第一次出现的指定元素(当从头部到尾部遍历双端队列时)。
- */
- public boolean removeFirstOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = head;
- E x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
- i = (i + 1) & mask;
- }
- return false;
- }
- /**
- * 移除此双端队列中最后一次出现的指定元素(当从头部到尾部遍历双端队列时)。
- */
- public boolean removeLastOccurrence(Object o) {
- if (o == null)
- return false;
- int mask = elements.length - 1;
- int i = (tail - 1) & mask;
- E x;
- while ( (x = elements[i]) != null) {
- if (o.equals(x)) {
- delete(i);
- return true;
- }
- i = (i - 1) & mask;
- }
- return false;
- }
- // *** 队列方法(Queue methods) ***
- /**
- * add方法,添加到队列末端
- */
- public boolean add(E e) {
- addLast(e);
- return true;
- }
- /**
- * 同上
- */
- public boolean offer(E e) {
- return offerLast(e);
- }
- /**
- * remove元素,删除队列前端
- */
- public E remove() {
- return removeFirst();
- }
- /**
- * 弹出前端(出对,删除前端)
- */
- public E poll() {
- return pollFirst();
- }
- public E element() {
- return getFirst();
- }
- public E peek() {
- return peekFirst();
- }
- // *** 栈 方法(Stack methods) ***
- public void push(E e) {
- addFirst(e);
- }
- public E pop() {
- return removeFirst();
- }
- private void checkInvariants() { …… }
- private boolean delete(int i) { …… }
- // *** 集合方法(Collection Methods) ***
- ……
- // *** Object methods ***
- ……
- }
- 整体来说:1个数组,2个index(head 索引和tail索引)。实现比较简单,容易理解。
2、LinkedList实现Deque
对于LinkedList本身而言,数据结构就更简单了,除了一个size用来记录大小外,只有head一个元素Entry。对比Map和Queue的其它数据结构可以看到这里的Entry有两个引用,是双向的队列。
在示意图中,LinkedList总是有一个“傀儡”节点,用来描述队列“头部”,但是并不表示头部元素,它是一个执行null的空节点。
队列一开始只有head一个空元素,然后从尾部加入E1(add/addLast),head和E1之间建立双向链接。然后继续从尾部加入E2,E2就在head和E1之间建立双向链接。最后从队列的头部加入E3(push/addFirst),于是E3就在E1和head之间链接双向链接。
双向链表的数据结构比较简单,操作起来也比较容易,从事从“傀儡”节点开始,“傀儡”节点的下一个元素就是队列的头部,前一个元素是队列的尾部,换句话说,“傀儡”节点在头部和尾部之间建立了一个通道,是整个队列形成一个循环,这样就可以从任意一个节点的任意一个方向能遍历完整的队列。
同样LinkedList也是一个没有容量限制的队列,因此入队列(不管是从头部还是尾部)总能成功。
3、小结
上面描述的ArrayDeque和LinkedList是两种不同方式的实现,通常在遍历和节省内存上ArrayDeque更高效(索引更快,另外不需要Entry对象),但是在队列扩容下LinkedList更灵活,因为不需要复制原始的队列,某些情况下可能更高效。
同样需要注意的上述两个实现都不是线程安全的,因此只适合在单线程环境下使用,下面章节要介绍的LinkedBlockingDeque就是线程安全的可阻塞的Deque。事实上也应该是功能最强大的Queue实现,当然了实现起来也许会复杂一点。
二、双向并发阻塞队列 LinkedBlockingDeque
1、LinkedBlockingDeque数据结构
双向并发阻塞队列。所谓双向是指可以从队列的头和尾同时操作,并发只是线程安全的实现,阻塞允许在入队出队不满足条件时挂起线程,这里说的队列是指支持FIFO/FILO实现的链表。
首先看下LinkedBlockingDeque的数据结构。通常情况下从数据结构上就能看出这种实现的优缺点,这样就知道如何更好的使用工具了。
从数据结构和功能需求上可以得到以下结论:
- 要想支持阻塞功能,队列的容量一定是固定的,否则无法在入队的时候挂起线程。也就是capacity是final类型的。
- 既然是双向链表,每一个结点就需要前后两个引用,这样才能将所有元素串联起来,支持双向遍历。也即需要prev/next两个引用。
- 双向链表需要头尾同时操作,所以需要first/last两个节点,当然可以参考LinkedList那样采用一个节点的双向来完成,那样实现起来就稍微麻烦点。
- 既然要支持阻塞功能,就需要锁和条件变量来挂起线程。这里使用一个锁两个条件变量来完成此功能。
2、LinkedBlockingDeque源码分析
- public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements BlockingDeque<E>, java.io.Serializable {
- /** 包含前驱和后继节点的双向链式结构 */
- static final class Node<E> {
- E item;
- Node<E> prev;
- Node<E> next;
- Node(E x, Node<E> p, Node<E> n) {
- item = x;
- prev = p;
- next = n;
- }
- }
- /** 头节点 */
- private transient Node<E> first;
- /** 尾节点 */
- private transient Node<E> last;
- /** 元素个数*/
- private transient int count;
- /** 队列容量 */
- private final int capacity;
- /** 锁 */
- private final ReentrantLock lock = new ReentrantLock();
- /** notEmpty条件 */
- private final Condition notEmpty = lock.newCondition();
- /** notFull条件 */
- private final Condition notFull = lock.newCondition();
- /** 构造方法 */
- public LinkedBlockingDeque() {
- this(Integer.MAX_VALUE);
- }
- public LinkedBlockingDeque(int capacity) {
- if (capacity <= 0) throw new IllegalArgumentException();
- this.capacity = capacity;
- }
- public LinkedBlockingDeque(Collection<? extends E> c) {
- this(Integer.MAX_VALUE);
- for (E e : c)
- add(e);
- }
- /**
- * 添加元素作为新的头节点
- */
- private boolean linkFirst(E e) {
- if (count >= capacity)
- return false;
- ++count;
- Node<E> f = first;
- Node<E> x = new Node<E>(e, null, f);
- first = x;
- if (last == null)
- last = x;
- else
- f.prev = x;
- notEmpty.signal();
- return true;
- }
- /**
- * 添加尾元素
- */
- private boolean linkLast(E e) {
- if (count >= capacity)
- return false;
- ++count;
- Node<E> l = last;
- Node<E> x = new Node<E>(e, l, null);
- last = x;
- if (first == null)
- first = x;
- else
- l.next = x;
- notEmpty.signal();
- return true;
- }
- /**
- * 返回并移除头节点
- */
- private E unlinkFirst() {
- Node<E> f = first;
- if (f == null)
- return null;
- Node<E> n = f.next;
- first = n;
- if (n == null)
- last = null;
- else
- n.prev = null;
- --count;
- notFull.signal();
- return f.item;
- }
- /**
- * 返回并移除尾节点
- */
- private E unlinkLast() {
- Node<E> l = last;
- if (l == null)
- return null;
- Node<E> p = l.prev;
- last = p;
- if (p == null)
- first = null;
- else
- p.next = null;
- --count;
- notFull.signal();
- return l.item;
- }
- /**
- * 移除节点x
- */
- private void unlink(Node<E> x) {
- Node<E> p = x.prev;
- Node<E> n = x.next;
- if (p == null) {//x是头的情况
- if (n == null)
- first = last = null;
- else {
- n.prev = null;
- first = n;
- }
- } else if (n == null) {//x是尾的情况
- p.next = null;
- last = p;
- } else {//x是中间的情况
- p.next = n;
- n.prev = p;
- }
- --count;
- notFull.signalAll();
- }
- //--------------------------------- BlockingDeque 双端阻塞队列方法实现
- public void addFirst(E e) {
- if (!offerFirst(e))
- throw new IllegalStateException("Deque full");
- }
- public void addLast(E e) {
- if (!offerLast(e))
- throw new IllegalStateException("Deque full");
- }
- public boolean offerFirst(E e) {
- if (e == null) throw new NullPointerException();
- lock.lock();
- try {
- return linkFirst(e);
- } finally {
- lock.unlock();
- }
- }
- public boolean offerLast(E e) {
- if (e == null) throw new NullPointerException();
- lock.lock();
- try {
- return linkLast(e);
- } finally {
- lock.unlock();
- }
- }
- public void putFirst(E e) throws InterruptedException {
- if (e == null) throw new NullPointerException();
- lock.lock();
- try {
- while (!linkFirst(e))
- notFull.await();
- } finally {
- lock.unlock();
- }
- }
- public void putLast(E e) throws InterruptedException {
- if (e == null) throw new NullPointerException();
- lock.lock();
- try {
- while (!linkLast(e))
- notFull.await();
- } finally {
- lock.unlock();
- }
- }
- public boolean offerFirst(E e, long timeout, TimeUnit unit)
- throws InterruptedException {
- if (e == null) throw new NullPointerException();
- long nanos = unit.toNanos(timeout);
- lock.lockInterruptibly();
- try {
- for (;;) {
- if (linkFirst(e))
- return true;
- if (nanos <= 0)
- return false;
- nanos = notFull.awaitNanos(nanos);
- }
- } finally {
- lock.unlock();
- }
- }
- public boolean offerLast(E e, long timeout, TimeUnit unit)
- throws InterruptedException {
- if (e == null) throw new NullPointerException();
- long nanos = unit.toNanos(timeout);
- lock.lockInterruptibly();
- try {
- for (;;) {
- if (linkLast(e))
- return true;
- if (nanos <= 0)
- return false;
- nanos = notFull.awaitNanos(nanos);
- }
- } finally {
- lock.unlock();
- }
- }
- public E removeFirst() {
- E x = pollFirst();
- if (x == null) throw new NoSuchElementException();
- return x;
- }
- public E removeLast() {
- E x = pollLast();
- if (x == null) throw new NoSuchElementException();
- return x;
- }
- public E pollFirst() {
- lock.lock();
- try {
- return unlinkFirst();
- } finally {
- lock.unlock();
- }
- }
- public E pollLast() {
- lock.lock();
- try {
- return unlinkLast();
- } finally {
- lock.unlock();
- }
- }
- public E takeFirst() throws InterruptedException {
- lock.lock();
- try {
- E x;
- while ( (x = unlinkFirst()) == null)
- notEmpty.await();
- return x;
- } finally {
- lock.unlock();
- }
- }
- public E takeLast() throws InterruptedException {
- lock.lock();
- try {
- E x;
- while ( (x = unlinkLast()) == null)
- notEmpty.await();
- return x;
- } finally {
- lock.unlock();
- }
- }
- public E pollFirst(long timeout, TimeUnit unit)
- throws InterruptedException {
- long nanos = unit.toNanos(timeout);
- lock.lockInterruptibly();
- try {
- for (;;) {
- E x = unlinkFirst();
- if (x != null)
- return x;
- if (nanos <= 0)
- return null;
- nanos = notEmpty.awaitNanos(nanos);
- }
- } finally {
- lock.unlock();
- }
- }
- public E pollLast(long timeout, TimeUnit unit)
- throws InterruptedException {
- long nanos = unit.toNanos(timeout);
- lock.lockInterruptibly();
- try {
- for (;;) {
- E x = unlinkLast();
- if (x != null)
- return x;
- if (nanos <= 0)
- return null;
- nanos = notEmpty.awaitNanos(nanos);
- }
- } finally {
- lock.unlock();
- }
- }
- public E getFirst() {
- E x = peekFirst();
- if (x == null) throw new NoSuchElementException();
- return x;
- }
- public E getLast() {
- E x = peekLast();
- if (x == null) throw new NoSuchElementException();
- return x;
- }
- public E peekFirst() {
- lock.lock();
- try {
- return (first == null) ? null : first.item;
- } finally {
- lock.unlock();
- }
- }
- public E peekLast() {
- lock.lock();
- try {
- return (last == null) ? null : last.item;
- } finally {
- lock.unlock();
- }
- }
- public boolean removeFirstOccurrence(Object o) {
- if (o == null) return false;
- lock.lock();
- try {
- for (Node<E> p = first; p != null; p = p.next) {
- if (o.equals(p.item)) {
- unlink(p);
- return true;
- }
- }
- return false;
- } finally {
- lock.unlock();
- }
- }
- public boolean removeLastOccurrence(Object o) {
- if (o == null) return false;
- lock.lock();
- try {
- for (Node<E> p = last; p != null; p = p.prev) {
- if (o.equals(p.item)) {
- unlink(p);
- return true;
- }
- }
- return false;
- } finally {
- lock.unlock();
- }
- }
- //---------------------------------- BlockingQueue阻塞队列 方法实现
- public boolean add(E e) {
- addLast(e);
- return true;
- }
- public boolean offer(E e) {
- return offerLast(e);
- }
- public void put(E e) throws InterruptedException {
- putLast(e);
- }
- public boolean offer(E e, long timeout, TimeUnit unit)
- throws InterruptedException {
- return offerLast(e, timeout, unit);
- }
- public E remove() {
- return removeFirst();
- }
- public E poll() {
- return pollFirst();
- }
- public E take() throws InterruptedException {
- return takeFirst();
- }
- public E poll(long timeout, TimeUnit unit) throws InterruptedException {
- return pollFirst(timeout, unit);
- }
- public E element() {
- return getFirst();
- }
- public E peek() {
- return peekFirst();
- }
- //------------------------------------------- Stack 方法实现
- public void push(E e) {
- addFirst(e);
- }
- public E pop() {
- return removeFirst();
- }
- //------------------------------------------- Collection 方法实现
- public boolean remove(Object o) {
- return removeFirstOccurrence(o);
- }
- public int size() {
- lock.lock();
- try {
- return count;
- } finally {
- lock.unlock();
- }
- }
- public boolean contains(Object o) {
- if (o == null) return false;
- lock.lock();
- try {
- for (Node<E> p = first; p != null; p = p.next)
- if (o.equals(p.item))
- return true;
- return false;
- } finally {
- lock.unlock();
- }
- }
- boolean removeNode(Node<E> e) {
- lock.lock();
- try {
- for (Node<E> p = first; p != null; p = p.next) {
- if (p == e) {
- unlink(p);
- return true;
- }
- }
- return false;
- } finally {
- lock.unlock();
- }
- }
- ……
- }
3、LinkedBlockingDeque的优缺点
有了上面的结论再来研究LinkedBlockingDeque的优缺点。
优点当然是功能足够强大,同时由于采用一个独占锁,因此实现起来也比较简单。所有对队列的操作都加锁就可以完成。同时独占锁也能够很好的支持双向阻塞的特性。
凡事有利必有弊。缺点就是由于独占锁,所以不能同时进行两个操作,这样性能上就大打折扣。从性能的角度讲LinkedBlockingDeque要比LinkedBlockingQueue要低很多,比CocurrentLinkedQueue就低更多了,这在高并发情况下就比较明显了。
前面分析足够多的Queue实现后,LinkedBlockingDeque的原理和实现就不值得一提了,无非是在独占锁下对一个链表的普通操作。
4、LinkedBlockingDeque的序列化、反序列化
有趣的是此类支持序列化,但是Node并不支持序列化,因此fist/last就不能序列化,那么如何完成序列化/反序列化过程呢?
清单4 LinkedBlockingDeque的序列化、反序列化
- <span style="font-size:14px;">private void writeObject(java.io.ObjectOutputStream s)
- throws java.io.IOException {
- lock.lock();
- try {
- // Write out capacity and any hidden stuff
- s.defaultWriteObject();
- // Write out all elements in the proper order.
- for (Node<E> p = first; p != null; p = p.next)
- s.writeObject(p.item);
- // Use trailing null as sentinel
- s.writeObject(null);
- } finally {
- lock.unlock();
- }
- }
- private void readObject(java.io.ObjectInputStream s)
- throws java.io.IOException, ClassNotFoundException {
- s.defaultReadObject();
- count = 0;
- first = null;
- last = null;
- // Read in all elements and place in queue
- for (;;) {
- E item = (E)s.readObject();
- if (item == null)
- break;
- add(item);
- }
- }
- </span>
清单4 描述的是LinkedBlockingDeque序列化/反序列化的过程。序列化时将真正的元素写入输出流,最后还写入了一个null。读取的时候将所有对象列表读出来,如果读取到一个null就表示结束。这就是为什么写入的时候写入一个null的原因,因为没有将count写入流,所以就靠null来表示结束,省一个整数空间。
相关推荐
本话题将深入探讨如何利用Java的多线程特性来实现消息的压入栈和从栈中取出,以及其在访问网络等实际应用场景中的运用。 首先,我们需要理解栈(Stack)这一数据结构。栈是一种后进先出(LIFO)的数据结构,它允许...
Java线程是多任务编程中的核心概念,它允许程序同时执行多个不同的任务,极大地提高了程序的效率和响应性。在Java中,线程是通过Java.lang.Thread类或实现Runnable接口来创建和管理的。这份“java线程文档大全”包含...
Java 容器类源码详解 Deque 与 ArrayDeque Java 容器类源码详解 Deque 与 ArrayDeque 主要介绍了 Java 容器类源码详解 Deque 与 ArrayDeque,Deque 接口继承自 Queue 接口,但 Deque 支持同时从两端添加或移除元素...
以下是对“C++多线程编程的十个例子”的详细讲解,这些例子将帮助你在Windows环境下深入理解和应用多线程。 1. **创建线程** C++11引入了`std::thread`库来创建和管理线程。例如,你可以通过传递函数或成员函数...
- 在多线程环境中,由于deque的内部结构,它更适合用于线程间的同步,如消息队列。 ### VC6.0环境下的使用 虽然VC6.0是一个较旧的编译器,但它仍然支持STL。在VC6.0中使用deque,需要包含`<deque>`头文件,并确保...
`std::deque`和`std::vector`虽然在使用上有很多相似之处,但在底层实现机制上有本质区别。`std::vector`是一个连续的内存块,而`std::deque`则是由多个连续的内存块组成的一个链表。这种设计使得`std::deque`在处理...
这确保了在多线程环境下,一个线程在添加或删除任务时不会与其他线程产生冲突。 2. **非阻塞操作**:为了优化性能,队列的读写操作应该尽可能地减少阻塞。例如,当队列为空时,消费者线程不应无限等待,而是应该被...
1. **动态大小调整**:与数组不同,deque可以在运行时改变其大小,无需预先确定固定容量。 2. **随机访问**:deque支持随机访问,可以通过索引直接访问任何元素,其时间复杂度为O(1)。 3. **高效插入和删除**:在...
Deque(双端队列)不仅可以作为堆栈使用,还能作为队列,提供了更多的操作方法。 `Deque`接口继承自`Queue`接口,提供了在两端添加和移除元素的能力。在Java中,`ArrayDeque`是`Deque`的一个高效实现,它是无界的,...
本文将深入探讨Java多线程的相关知识点,帮助开发者理解并掌握如何在Java环境中实现高效的并发处理。 ### 一、多线程简介 多线程(Multithreading)是现代计算机技术中的一种关键特性,它允许程序在同一时刻执行多...
C++实现STL容器之deque
在《Java算法实战设计与分析》中,我们深入探讨了计算机科学中的核心概念——算法,以及如何使用Java语言实现它们。这些算法是编程基础的重要组成部分,对于任何希望提升软件开发技能的程序员来说都是必不可少的。在...
本文将深入探讨如何创建一个多线程安全的消息队列模板,并介绍其在C++中的实现和应用。 首先,理解多线程安全意味着代码可以在多个线程同时访问时保持正确性,不会引发数据竞争或死锁等问题。在C++中,我们通常利用...
本章将深入探讨Java集合框架的核心概念、接口和类,以及它们在实际编程中的应用。 首先,集合框架的基础是接口,这些接口定义了各种集合行为。其中最基础的两个接口是`List`和`Set`。`List`接口代表了一个有序的...
(1)利用python多进程程或多线程实时读取远程IP摄像头视频 (2)Pyhon cv2.VideoWriter 保存视频 整合成如下代码,可以对多路网络摄像头图像实时采集并分别保存视频。或者自己改写代码,直接保存每路的实时图像也...
这篇深入研究C++中的STL `deque`容器的文章旨在探讨在什么情况下`deque`比`vector`更合适,并分析两者在内存管理和性能上的差异。 首先,`deque`和`vector`都允许动态存储和访问元素。然而,它们在内存分配上有显著...
STL中的deque模板包括迭代器等接口
与`vector`类似,`deque`内部也是通过动态分配内存来存储元素,但与`vector`不同的是,`deque`的数据不是连续存储的,而是分成多个块(chunk)存放,每个块内部元素是连续的。这样的设计使得在两端进行插入和删除...
然而,同步操作通常会降低并发性能,因此在多线程环境下,可以考虑使用`Concurrent`集合,如`ConcurrentHashMap`和`CopyOnWriteArrayList`,它们提供了更高效的并发操作。 最后,为了确保代码的健壮性和可维护性,...
Java 6.0 API包含了大量核心类库,如集合框架、I/O流、网络编程、多线程、反射机制、异常处理、数据库连接(JDBC)、XML处理等关键模块。 1. 集合框架:Java 6.0引入了泛型,提高了集合类型的类型安全性和代码...