当前位置:   article > 正文

双向队列(Dqueue)实现详解

dqueue
package com.datastructure;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 双向队列(Double-ended queue):允许在头部和尾部执行元素的添加或删除操作
 *
 * 双向队列常用操作:
 * 方法名                描述                  时间复杂度
 * push_first()    将元素添加到队首             O(1)
 * push_last()     将元素添加到队尾             O(1)
 * pop_first()     删除队首元素                 O(1)
 * pop_last()    删除队尾元素                  O(1)
 * peek_first()    访问队首元素                O(1)
 * peek_last()     访问队尾元素                O(1)
 *
 *
 * 双向队列应用场景:
 * 撤销功能的实现
 *
 *
 */
public class Deque1 {

    public static void main(String[] args) {
        /**
         * 初始化双向队列
         */
        Deque<Integer> deque = new LinkedList<>();

        /**
         * 元素入队
         */
        deque.offerLast(2);//添加到队尾
        deque.offerLast(5);
        deque.offerLast(4);
        deque.offerFirst(3);//添加队首
        deque.offerFirst(1);

        /**
         * 访问元素
         */
        int peekFirst = deque.peekFirst();//队首元素
        System.out.println("peekFirst = " + peekFirst);
        int peekLast = deque.peekLast();
        System.out.println("peekLast = " + peekLast);

        /**
         * 元素出队
         */

        int popFirst = deque.pollFirst();//队首元素出队
        System.out.println(popFirst);
        int popLast = deque.pollLast();//队尾元素出队
        System.out.println("popLast = " + popLast);

        /**
         * 获取双向队列的长度
         */
        int size = deque.size();
        System.out.println("size = " + size);

        /**
         * 判断双向队列是否为空
         */
        boolean isEmpty = deque.isEmpty();
        System.out.println("isEmpty = " + isEmpty);


    }
}

/**
 * 双向队列的实现,可基于链表或数组作为底层数据结构
 */

/**
 * 双向队列的实现: 1.基于双向链表的实现
 */
class LinkedListDeque {
    private DListNode front;//头节点front
    private DListNode rear;//尾结点
    private int queSize = 0;//双向队列长度

    public LinkedListDeque() {
        front = rear = null;
    }

    /**
     * 获取双向队列的长度
     */
    public int size() {
        return queSize;
    }

    /**
     * 判断双向队列是否为空
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * 入队操作
     */
    private void push(int num, boolean isFront) {
        DListNode node = new DListNode(num);
        //链表为空,则令front和rear指向node
        if (isEmpty()) {
            front = rear = node;
        } else if (isFront) {//队首入队操作
            //将node添加至链表头部
            front.prev = node;
            node.next = front;
            front = node;//更新头节点
        } else {//将node添加到链表尾部
            rear.next = node;
            node.prev = rear;
            rear = node;//更新尾结点
        }
        queSize++;//更新队列长度
    }

    /**
     * 队首入队
     *
     * @param num
     */
    public void pushFirst(int num) {
        push(num, true);
    }

    /**
     * 队尾入队
     *
     * @param num
     */
    public void pushLast(int num) {
        push(num, false);
    }

    /**
     * 出队操作
     *
     * @param isFront
     * @return
     */
    private int pop(boolean isFront) {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        int val;
        //队首出队操作
        if (isFront) {
            val = front.val;//暂存头节点值
            //删除头节点
            DListNode fNext = front.next;
            if (fNext != null) {
                fNext.prev = null;
                front.next = null;
            }
            front = fNext;//更新头节点

        } else {//队尾出队操作
            val = rear.val;//暂存尾结点
            //删除尾结点
            DListNode rPrev = rear.prev;
            if (rPrev != null) {
                rPrev.next = null;
                rear.prev = null;
            }
            rear = rPrev;//更新尾结点
        }
        queSize--;//更新队列长度
        return val;
    }

    /**
     * 队首出队
     */
    public int popFirst() {
        return pop(true);
    }

    /**
     * 队尾出队
     */
    public int popLast() {
        return pop(false);
    }

    /**
     * 访问队首元素
     */
    public int peekFirst() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException();
        }
        return front.val;
    }

    /**
     * 访问队尾元素
     */
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return rear.val;
    }

    /**
     * 返回数组用于打印
     */
    public int[] toArray() {
        DListNode node = front;
        int[] res = new int[size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = node.val;
            node = node.next;
        }

        return res;
    }
}

/**
 * 双向链表节点实现
 */
class DListNode {
    int val;//节点值
    DListNode next;//后继节点引用
    DListNode prev;//前驱节点引用

    DListNode(int val) {
        this.val = val;
        prev = next = null;
    }
}


/**
 * 双向队列基于环形数组实现
 */
class ArrayDeque {
    private int[] nums;//用于存储双向队列元素的数组
    private int front;//队首指针,指向队首元素
    private int queSize;//双向队列长度

    public ArrayDeque(int capacity) {
        this.nums = new int[capacity];
        front = queSize = 0;
    }

    /**
     * 获取双向队列的容量
     */
    public int capacity() {
        return nums.length;
    }

    /**
     * 获取双向队列的长度
     */
    public int size() {
        return queSize;
    }

    /**
     * 判断双向队列是否为空
     */
    public boolean isEmpty() {
        return this.size() == 0;
    }

    /**
     * 计算环形数组索引
     */
    private int index(int i) {
        //通过取余操作实现数组首尾相连
        //当i越过数组尾部后,回到头部
        //当i越过数组头部后,回到尾部
        return (i + capacity()) % capacity();
    }

    /**
     * 队首入队
     */
    public void pushFirst(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        //队首指针向左移动一位
        //通过取余操作实现front越过数组头部后回到尾部
        front = index(front - 1);
        //将num添加到队首
        nums[front] = num;
        queSize++;
    }

    /**
     * 队尾入队
     */
    public void pushLast(int num) {
        if (queSize == capacity()) {
            System.out.println("双向队列已满");
            return;
        }
        //计算队尾指针,指向队尾索引+1
        int rear = index(front + queSize);
        //将num添加到队尾
        nums[rear] = num;
        queSize++;
    }

    /**
     * 队首出队
     *
     * @return
     */
    public int popFirst() {
        int num = peekFirst();
        //队首指针向后移动一位
        front = index(front + 1);
        queSize--;
        return num;
    }

    /**
     * 队尾出队
     */
    public int popLast() {
        int num = peekLast();
        queSize--;
        return num;
    }

    /**
     * 访问队首元素
     *
     * @return
     */
    public int peekFirst() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        return nums[front];
    }

    /**
     * 访问队尾元素
     */
    public int peekLast() {
        if (isEmpty())
            throw new IndexOutOfBoundsException();
        //计算尾元素索引
        int last = index(front + queSize - 1);
        return nums[last];
    }

    /**
     * 返回数组用于打印
     */
    public int[] toArray() {
        //仅转换有效长度范围内的列表元素
        int[] res = new int[queSize];
        for (int i = 0, j = front; i < queSize; i++, j++) {
            res[i] = nums[index(j)];
        }
        return res;
    }
}
  • 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
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
  • 328
  • 329
  • 330
  • 331
  • 332
  • 333
  • 334
  • 335
  • 336
  • 337
  • 338
  • 339
  • 340
  • 341
  • 342
  • 343
  • 344
  • 345
  • 346
  • 347
  • 348
  • 349
  • 350
  • 351
  • 352
  • 353
  • 354
  • 355
  • 356
  • 357
  • 358
  • 359
  • 360
  • 361
  • 362
  • 363
  • 364
  • 365
  • 366
  • 367
  • 368
  • 369
  • 370
  • 371
  • 372
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/891752
推荐阅读
相关标签
  

闽ICP备14008679号