双向队列（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