devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

7、双端队列

作者：小蓝xlanll | 2024-04-23 01:25:51

赞

踩

双端队列

一、什么是双端队列

   双端队列（Double-ended Queue，简称deque）是一种线性数据结构，它允许在两端进行插入和删除操作。这意味着与普通队列（FIFO，先进先出）或栈（LIFO，后进先出）不同，双端队列的使用者不仅可以从队列的一端（通常称为“尾”端）添加元素（enqueue），也可以从这一端删除元素（dequeue）。同时，双端队列还支持在另一端（通常称为“头”端）执行相同的操作，即在队列头部添加（enqueue at head）和删除（dequeue at head）元素。

因此，双端队列的特点包括：

  1. 可以在队列头部进行入队和出队操作。
  2. 可以在队列尾部进行入队和出队操作。
  3. 具有动态调整大小的能力（取决于具体实现）。
  4. 既可以作为栈使用（在一端进行插入和删除），又可以作为普通队列使用，还可以用于其他更复杂的数据处理场景，如回文检测、滑动窗口算法等。

二、解决了什么问题

  1. 普通队列（FIFO）只允许在一端（尾部）插入元素，在另一端（头部）删除元素。而在某些情况下，我们可能需要在两端都能进行插入和删除操作。例如，在处理具有“历史”和“未来”概念的场景时，可能既要关注最新的数据也要能随时访问或移除最早的数据。
  2. 栈（LIFO）只能在一端进行插入和删除操作，而双端队列则可以同时作为栈来使用，但更为灵活，因为它可以在两端都执行入栈和出栈操作。
  3. 在算法实现中，双端队列常用于解决一些复杂问题，如滑动窗口最大值、回文串检测、动态规划中的边界更新等，这些场景下往往要求既能向后添加元素，也能向前移除元素。
  4. 双端队列还支持高效地在任意位置插入和删除元素（时间复杂度为O(1)），这使得它非常适合于需要频繁修改序列中间部分的操作。

综上所述，双端队列提供了一种更灵活、功能更强大的线性数据结构，能够适应更多样化的数据处理需求。

三、实现的方式

  双端队列的实现方式主要有两种：数组存储和链表存储

1、数组存储

基本思想：

  • 使用一个动态大小的数组来存储元素，通过维护两个指针（头指针和尾指针）分别记录队列头部和尾部的位置。
  • 当需要在头部插入或删除元素时，只需更新头指针；当在尾部插入或删除元素时，更新尾指针，并可能涉及到数组元素的移动以保持队列连续。

优点：

  • 插入和删除尾部元素的时间复杂度为O(1)。
  • 在某些实现中，在头部插入或删除元素的平均时间复杂度也为O(1)（通过预分配多余空间并适时调整容量实现）。

缺点：

  • 如果频繁在头部插入或删除元素且未预先分配足够的空间，可能导致大量元素移动，此时时间复杂度会退化到O(n)。

2、链表存储

基本思想：

  • 使用双向链表作为底层数据结构，每个节点包含元素以及指向前后节点的指针。
  • 头指针指向队列的第一个元素，尾指针指向队列的最后一个元素。
  • 在头部或尾部插入、删除元素时，只需改变相应指针的指向即可。

优点：

  • 不论是在头部还是尾部进行插入或删除操作，时间复杂度均为O(1)。

缺点：

  • 相对于数组实现，链式存储通常占用更多的内存空间（额外的指针开销）。
  • 随机访问某个元素的效率较低（时间复杂度为O(n)）。

在实际应用中，选择何种实现方式取决于具体需求，包括对内存使用、插入/删除效率、随机访问性能等因素的权衡。

四、代码案例

创建一个双端队列公共接口

package deque;

/**
 * 双端队列
 */
public interface Deque<E> {


    /**
     * 在队列开头添加元素
     *
     * @param e
     * @return
     */
    boolean offerFirst(E e);

    /**
     * 在队列结尾添加元素
     *
     * @param e
     * @return
     */
    boolean offerLast(E e);

    /**
     * 在队列开头读取元素，并删除该元素
     *
     * @return
     */
    E pollFirst();

    /**
     * 在队列尾部读取元素，并删除该元素
     *
     * @return
     */
    E pollLast();

    /**
     * 在队列开头查询元素，但不删除
     *
     * @return
     */
    E peekFirst();

    /**
     * 在队列尾部查询元素，但不删除
     *
     * @return
     */
    E peekLast();

    /**
     * 判断队列是否为空
     *
     * @return
     */
    boolean isEmpty();

    /**
     * 检查队列是否已满
     *
     * @return
     */
    boolean isFull();

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

1、链表案例,基于双向循环链表实现

package deque;

/**
 * 使用双向循环链表实现双端队列
 *
 * @param <E>
 */
public class DequeLinkedList<E> implements Deque<E> {

    /**
     * 哨兵
     */
    private Node<E> sentinel = new Node<>(null, null, null);

    /**
     * 队列长度
     */
    private int dequeLength;

    /**
     * 队列值的个数
     */
    private int size;

    /**
     * @param dequeLength 设置队列长度
     */
    public DequeLinkedList(int dequeLength) {
        this.sentinel.prev = sentinel;
        this.sentinel.next = sentinel;
        this.dequeLength = dequeLength;
        this.size = 0;
    }

    /**
     * 节点类
     *
     * @param <E>
     */
    static class Node<E> {

        Node<E> prev;//前节点

        E value;//节点值

        Node<E> next;//后节点

        public Node(Node<E> prev, E value, Node<E> next) {
            this.prev = prev;
            this.value = value;
            this.next = next;
        }
    }

    /**
     * 在队列开头添加元素
     *
     * @param e
     * @return
     */
    @Override
    public boolean offerFirst(E e) {
        //判断队列是否已满
        if (isFull()) {
            return false;
        }
        Node<E> a = sentinel;
        Node<E> b = sentinel.next;
        Node<E> offered = new Node<>(a, e, b);
        a.next = offered;
        b.prev = offered;
        size++;
        return true;
    }

    /**
     * 在队列结尾添加元素
     *
     * @param e
     * @return
     */
    @Override
    public boolean offerLast(E e) {
        //判断队列是否已满
        if (isFull()) {
            return false;
        }
        Node<E> a = sentinel.prev;
        Node<E> b = sentinel;
        Node<E> offered = new Node<>(a, e, b);
        a.next = offered;
        b.prev = offered;
        size++;
        return true;
    }

    /**
     * 在队列开头读取元素，并删除该元素
     *
     * @return
     */
    @Override
    public E pollFirst() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        Node<E> data = sentinel.next;
        Node<E> next = data.next;
        sentinel.next = next;
        next.prev = sentinel;
        size--;
        return data.value;
    }

    /**
     * 在队列尾部读取元素，并删除该元素
     *
     * @return
     */
    @Override
    public E pollLast() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        Node<E> data = sentinel.prev;
        Node<E> prev = data.prev;
        prev.next = sentinel;
        sentinel.prev = prev;
        size--;
        return data.value;
    }

    /**
     * 在队列开头查询元素，但不删除
     *
     * @return
     */
    @Override
    public E peekFirst() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        return sentinel.next.value;
    }

    /**
     * 在队列尾部查询元素，但不删除
     *
     * @return
     */
    @Override
    public E peekLast() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        return sentinel.prev.value;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        //队列值个数等于=0则队列为空！
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        //队列值个数等于队列长度则表示队列已满。
        return size == dequeLength;
    }

}


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186

2、数组案例,基于双向循环链表实现

思路：

1、数组初始化：
  • 初始化一个空数组，容量可以预设一个初始值或动态调整。
  • 通常设置两个索引变量：head（指向队列头部）和tail（指向队列尾部）。当队列为空时，它们都指向数组的第一个位置。
2、插入操作：

  • 在头部插入元素：
    判断队列是否已满。没有则，将head索引后退一步（-1）。让后在该索引位置插入值。

  • 在尾部插入元素：
    判断队列是否已满。没有则，直接在tail索引位置后添加新元素，并更新tail索引前进一步（+1）。

3、删除操作：

  • 从头部获取元素：
    先获取head索引位置的元素，再将head索引位置的元素清空（垃圾回收），最后将head索引前移一位（+1）。

  • 从尾部删除元素：
    先将tail索引位置后移一位（-1）；再获取 tail索引位置的元素，最后将tail索引位置的元素清空（垃圾回收)；

代码：

package deque;

/**
 * 使用循环数组实现双端队列
 *
 * @param <E>
 */
public class DequeArray<E> implements Deque<E> {

    /**
     * 队列数组
     */
    private E[] dequeArray;

    /**
     * 队列长度
     */
    private int dequeLength;

    /**
     * 头指针
     */
    private int head;

    /**
     * 尾指针
     */
    private int tail;

    /**
     * 队列值个数
     */
    private int size;

    /**
     * @param dequeLength 设置队列长度
     */
    public DequeArray(int dequeLength) {
        this.dequeArray = (E[]) new Object[dequeLength];
        this.dequeLength = dequeLength;
        this.head = 0;
        this.tail = 0;
        this.size = 0;
    }

    /**
     * 获取增长索引位置
     *
     * @return
     */
    private int increase(int index) {
        //如果索引位置加1大于数组的下表，那么返回索引0；
        if (index + 1 > dequeLength - 1) {
            return 0;
        }
        return index + 1;
    }

    /**
     * 获取下降索引位置
     *
     * @return
     */
    private int decline(int index) {
        if (index - 1 < 0) {
            return dequeLength - 1;
        }
        return index - 1;
    }

    /**
     * 在队列开头添加元素
     *
     * @param e
     * @return
     */
    @Override
    public boolean offerFirst(E e) {
        //检查队列是否已满
        if (isFull()) {
            return false;
        }
        head = decline(head);//头部添加队列要先获取索引值。(索引位置先-1)
        dequeArray[head] = e; //赋值
        size++;
        return true;
    }

    /**
     * 在队列结尾添加元素
     *
     * @param e
     * @return
     */
    @Override
    public boolean offerLast(E e) {
        //检查队列是否已满
        if (isFull()) {
            return false;
        }
        dequeArray[tail] = e; //先赋值
        tail = increase(tail);//再更新索引
        size++;
        return true;
    }

    /**
     * 在队列开头读取元素，并删除该元素
     *
     * @return
     */
    @Override
    public E pollFirst() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        E e = dequeArray[head];
        dequeArray[head] = null;//将取出的值清空。回收垃圾；
        head = increase(head);
        size--;
        return e;
    }

    /**
     * 在队列尾部读取元素，并删除该元素
     *
     * @return
     */
    @Override
    public E pollLast() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        int tail = decline(this.tail);
        E e = dequeArray[tail];
        dequeArray[tail] = null;//将取出的值清空。回收垃圾；
        size--;
        return e;
    }

    /**
     * 在队列开头查询元素，但不删除
     *
     * @return
     */
    @Override
    public E peekFirst() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        return dequeArray[head];
    }

    /**
     * 在队列尾部查询元素，但不删除
     *
     * @return
     */
    @Override
    public E peekLast() {
        //判断队列是否为空
        if (isEmpty()) {
            return null;
        }
        return dequeArray[decline(tail)];
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        //队列值个数等于0
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        //队列值个数等于队列长度；
        return size == dequeLength;
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192

测试结果：

在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/471471
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号