美文网首页数据结构与算法程序员
数据结构之「双端队列」

数据结构之「双端队列」

作者: 清尘闲聊 | 来源:发表于2019-03-18 08:47 被阅读27次

什么是双端队列?

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。


双端队列

双端队列怎么实现?

双端队列的存储结构

public class LinkedBlockingDeque<E> {
    //队头
    Node<E> first;
    //队尾
    Node<E> last;
    //元素个数
    int count;
    static final class Node<E> {
        //存储元素
        E item;
        //上一个元素
        Node<E> prev;
        //下一个元素
        Node<E> next;
    }
}

从队头入队

public boolean offerFirst(Node<E> node) {
    //头节点临时变量
    Node<E> f = first;
    //把当前的下一个节点指向头节点
    node.next = f;
    //更新当前节点为头节点
    first = node;
    //假如尾节点为空,则把当前节点设置为尾节点
    if (last == null)
        last = node;
    //就把以前的头节点指向当前节点
    else
        f.prev = node;
    //总数加一
    ++count;
    return true;
}

从队头出队

public E pollFirst() {
     Node<E> f = first;
    //头节点的下一个节点
    Node<E> n = f.next;
    //获取头节点元素
    E item = f.item;
    //置空
    f.item = null;
    //孤立头节点,不指向任何节点
    f.next = f; // help GC
    //重置头节点
    first = n;
    //说明是最后一个节点
    if (n == null)
        last = null;
    //否则把头节点的上一个节点置空
    else
        n.prev = null;
    //总数减一
    --count;
    return item;
}

从队尾入队

public boolean offerLast(Node<E> node) {
    //尾节点临时变量
    Node<E> l = last;
    if (l == null)
        return null;
    //把当前的上一个节点指向尾节点
    node.prev = l;
    //更新当前节点为尾节点
    last = node;
    //假如头节点为空,则把头节点置为当前节点
    if (first == null)
        first = node;
    //否则把临时的尾节点的下一个节点指向当前节点
    else
        l.next = node;
    //总数加一
    ++count;
    return true;
}

从队尾出队

public E pollLast() {
    Node<E> l = last;
    if (l == null)
        return null;
    //最后节点的上一个节点
    Node<E> p = l.prev;
    //获取元素
    E item = l.item;
    //置空
    l.item = null;
    //孤立尾节点
    l.prev = l; // help GC
    //更新尾节点
    last = p;
    //假如是最后一个元素,置空头节点
    if (p == null)
        first = null;
    //否则置空下一个节点指向
    else
        p.next = null;
    //总数减一
    --count;
    return item;
}

总结

双端队列其实和队列差不多的,只是更加灵活了,队头和队尾均可进行入队和出队操作。这里是基于链表的双端队列实现,具体详情可查看 JDK 的 LinkedBlockingDeque 的实现,它还考虑了线程安全相关的东西,这里只是简单的一个实现,了解双端队列的结构和运作方式。

相关文章

  • 数据结构-队列(Queue)-FIFO

    数据结构-队列(Queue)-FIFO 队列的接口设计 双端队列-Deque 循环队列-CircleQueue 双...

  • 4. 数据结构与算法:双端队列-

    双端队列(deque,全名double-ended queue)是一种具有队列和栈性质的线性数据结构。双端队列也拥...

  • 文章列表

    基本数据结构 栈 队列 双端队列 无序链表 有序链表 递归 递归 搜索与排序 搜索

  • 7.双端队列Deque

    目录:1.双端队列的定义2.双端队列的图解3.双端队列定义操作4.双端队列的实现 1.双端队列的定义 2.双端队列...

  • 2.6 数据结构 --1.3 双端队列

    数据结构子目录https://www.jianshu.com/p/a344fa483655 双端队列 什么是双端队...

  • 数据结构之双端队列

    双端队列的特性 大致思路是两端都可以进出队列 Deque的实现API 注意的地方 是双端队列的头部的进队和出队,因...

  • 数据结构之「双端队列」

    什么是双端队列? 双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double...

  • Leetcode-239-Sliding Window Maxi

    太久不复习数据结构,几乎快忘记双端队列这个东西了。。。这道题用双端队列解很自然,且思路也很简单,其他方法做到的复杂...

  • 双端队列

    双端队列 双端队列是与队列类似的项的有序集合。双端队列有两个端部,首部和尾部,并且项在集合中保持不变。双端队不同的...

  • JavaScript数据结构之双端队列

网友评论

    本文标题:数据结构之「双端队列」

    本文链接:https://www.haomeiwen.com/subject/ksiumqtx.html