队列 Queue

  • 队列也是一种线性结构
  • 相比数组，队列对应的操作是数组的子集
  • 只能从一端（队尾）添加元素，只能从另一端（队首）取出元素
  • 队列是一种先进先出的数据结构（先到先得 First In First Out FIFO）

image-20210314014025294

其实队列⾮常好理解，我们将队列可以看成⼩朋友排队

  • 队尾的⼩朋友到指定的地点了–>出队
  • 有新的⼩朋友加⼊了–>⼊队

相对于栈⽽⾔，队列的特性是：先进先出

  • 先排队的⼩朋友肯定能先打到饭！

队列的基本实现

  • Interface Queue<E> — ArrayQueue<E>
    • void enqueue(E)
    • E dequeue()
    • E getFront()
    • int getSize()
    • boolean isEmpty()
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
package demo.structure.queue;

/**
 * 队列的基本实现--接口
 *
 * @author jingLv
 * @date 2020/12/03
 */
public interface Queue<E> {

    /**
     * 队列中元素的个数
     *
     * @return 元素的个数
     */
    int getSize();

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

    /**
     * 队列中添加元素
     *
     * @param e 添加的元素
     */
    void enqueue(E e);

    /**
     * 队列中删除数据
     *
     * @return 删除的元素
     */
    E dequeue();

    /**
     * 获取队列队头的元素
     *
     * @return 队头的元素
     */
    E getFront();
}

队列的应用

  • 网络数据包的排队，程序运行任务的排队……
  • 广度优先遍历

数组实现线性队列

image-20210314015631232

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
package demo.structure.queue;

import demo.structure.array.Array;

/**
 * 数组实现线性队列
 *
 * @author jingLv
 * @date 2020/12/03
 */
public class ArrayQueue<E> implements Queue<E> {
    /**
     * 定义数组
     */
    Array<E> array;

    /**
     * 构造函数--初始化数组
     *
     * @param capacity 数组容量
     */
    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    /**
     * 无参构造函数
     */
    public ArrayQueue() {
        array = new Array<>();
    }

    /**
     * 获取栈中元素的个数
     *
     * @return 元素的个数
     */
    @Override
    public int getSize() {
        return array.getSize();
    }

    /**
     * 判断队列是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return array.isEmpty();
    }

    /**
     * 获取队列数组的容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return array.getCapacity();
    }

    /**
     * 队列中添加元素
     *
     * @param e 添加的元素
     */
    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    /**
     * 队列删除元素
     *
     * @return 删除的元素
     */
    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    /**
     * 获取队列的队头的元素
     *
     * @return 队头的元素
     */
    @Override
    public E getFront() {
        return array.getFirst();
    }

    /**
     * 格式化输出队列
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        result.append("Queue:");
        result.append("front [");
        for (int i = 0; i < array.getSize(); i++) {
            result.append(array.get(i));
            if (i != array.getSize() - 1) {
                result.append(",");
            }
        }
        result.append("] tail");
        return result.toString();
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package demo.structure.queue;

/**
 * @author jingLv
 * @date 2020/12/03
 */
public class ArrayQueueMain {

    public static void main(String[] args) {
        ArrayQueue<Integer> queue = new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

执行结果

image-20210314020430421

线性队列的复杂度分析

  • ArrayQueue<E>
    • void enqueue(E) – O(1) 均摊
    • E dequeue() – O(n)
    • E getFront() – O(1)
    • int getSize() – O(1)
    • boolean isEmpty() – O(1)

数组实现循环队列

image-20210314014336364

做成循环队列的好处是不浪费内存资源！

front == tail 队列为空

(tail+1) % c == front 队列满

capacity中，浪费一个空间

image-20210314184753066

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
package demo.structure.queue;

/**
 * 数组实现循环队列
 *
 * @author jingLv
 * @date 2020/12/03
 */
public class LoopQueue<E> implements Queue<E> {
    /**
     * 队列元素
     */
    private E[] data;
    /**
     * front 队头
     * tail 队尾
     */
    private int front, tail;
    /**
     * 队列存储元素的数量
     */
    private int size;

    /**
     * 构造函数--初始化队列
     * front=tail为空数组
     *
     * @param capacity 数组的容量
     */
    public LoopQueue(int capacity) {
        // 循环队列，有意识的浪费一个单位
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 无参构造函数--默认初始化数组容量为10
     */
    public LoopQueue() {
        this(10);
    }

    /**
     * 获取数组队列的数组容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 获取队列中元素个数
     *
     * @return 元素个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 判断队列是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 队列中添加元素（入队）
     *
     * @param e 添加的元素
     */
    @Override
    public void enqueue(E e) {
        // 入队查询队列是否是满的
        if ((tail + 1) % data.length == front) {
            // 队列是满的则进行2倍扩容
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 队列中删除数据(出队)
     *
     * @return 删除队列的元素
     */
    @Override
    public E dequeue() {
        // 判断队列是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        // 出队的低于队列长度的四分之一，则进缩容
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    /**
     * 获取队列的队头元素
     *
     * @return 队头元素
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[front];
    }

    /**
     * 队列的扩容
     *
     * @param newCapacity 新的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 格式化输出循环队列
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue:size = %d, capacity = %d \n", size, getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            // 指向不是最后一个元素
            if ((i + 1) % data.length != tail) {
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }
}

测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package demo.structure.queue;

/**
 * @author jingLv
 * @date 2020/12/03
 */
public class LoopQueueMain {
    public static void main(String[] args) {
        LoopQueue<Integer> queue = new LoopQueue<>();
        for (int i = 0; i < 10; i++) {
            // 入队
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                // 出队
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

执行结果

image-20210314184929910

循环队列的复杂度分析

  • LoopQueue<E>
    • void enqueue(E) – O(1) 均摊
    • E dequeue() – O(1) 均摊
    • E getFront() – O(1)
    • int getSize() – O(1)
    • boolean isEmpty() – O(1)

数组线性队列和数组循环队列的比较

测试代码：

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
package demo.structure.queue;

import java.util.Random;

/**
 * 测试数组队列与循环队列的差别
 *
 * @author jingLv
 * @date 2020/12/03
 */
public class Main {

    public static void main(String[] args) {
        int opCount = 100000;
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        double time1 = testQueue(arrayQueue, opCount);
        System.out.println("ArrayQueue, time:" + time1 + " s");

        LoopQueue<Integer> loopQueue = new LoopQueue<>();
        double time2 = testQueue(loopQueue, opCount);
        System.out.println("LoopQueue, time:" + time2 + " s");
    }

    /**
     * 测试使用q运行OpCount个enqueue和dequeue操作所需要的时间，单位秒
     *
     * @param q       队列
     * @param opCount 队列的元素
     * @return 时间（秒）
     */
    private static double testQueue(Queue<Integer> q, int opCount) {
        long startTime = System.nanoTime();
        Random random = new Random();
        // 入队
        for (int i = 0; i < opCount; i++) {
            q.enqueue(random.nextInt(Integer.MAX_VALUE));
        }
        // 出队
        for (int i = 0; i < opCount; i++) {
            q.dequeue();
        }
        long endTime = System.nanoTime();
        return (endTime - startTime) / 1000000000.0;
    }
}

执行结果：

image-20210314185629320

换个方式实现队列

  • 使用size，不浪费一个空间
  • 不使用size，浪费一个空间

不浪费一个空间实现队列

实际上，如果我们想要实现一个队列，使用size记录了队列中有多少元素，完全可以不浪费那一个空间。

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
package demo.structure.queue;

/**
 * 使用size，不浪费一个空间
 *
 * @author jinglv
 * @date 2021/03/15
 */
public class LoopQueueSize<E> implements Queue<E> {
    /**
     * 队列的数组
     */
    private E[] data;
    /**
     * front队头
     * tail队尾
     */
    private int front, tail;
    /**
     * 队列存储元素的数量
     */
    private int size;

    /**
     * 构造函数，初始化队列
     *
     * @param capacity 数组的容量
     */
    public LoopQueueSize(int capacity) {
        // 由于不浪费空间，所以data静态数组的大小是capacity，而不是capacity+1
        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 构造函数，初始化队列，默认容量为10
     */
    public LoopQueueSize() {
        this(10);
    }

    /**
     * 获取队列中元素的个数
     *
     * @return 元素个数
     */
    @Override
    public int getSize() {
        return size;
    }

    /**
     * 获取数组队列的数组容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return data.length;
    }

    /**
     * 判断队列是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        // 不再使用front和tail之间的关系来判断队列是否为空，而是直接使用size
        return size == 0;
    }

    /**
     * 队列中添加元素
     *
     * @param e 添加的元素
     */
    @Override
    public void enqueue(E e) {
        // 使用size判断队列是否已满
        if (size == getCapacity()) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    /**
     * 删除队列中的元素
     *
     * @return 删除的元素
     */
    @Override
    public E dequeue() {
        // 判断队列是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        // 出队的低于队列长度的四分之一，则进缩容
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    /**
     * 获取队列的队头元素
     *
     * @return 队头元素
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[front];
    }

    /**
     * 队列的扩容
     *
     * @param newCapacity 新的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 格式化输出循环队列
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue:size = %d, capacity = %d \n", size, getCapacity()));
        res.append("front [");
        for (int i = 0; i < size; i++) {
            res.append(data[(front + 1) % data.length]);
            // 指向不是最后一个元素
            if ((i + front + 1) % data.length != tail) {
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueueSize<Integer> queue = new LoopQueueSize<>();
        for (int i = 0; i < 10; i++) {
            // 入队
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                // 出队
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

使用size实现队列，会浪费一个空间

如果我们不使用size，也完全可以实现整个队列，但是，相应的，我们需要浪费一个空间

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
package demo.structure.queue;

/**
 * 使用size实现队列，会浪费一个空间
 *
 * @author jinglv
 * @date 2021/03/15
 */
public class LoopQueueNoSize<E> implements Queue<E> {
    /**
     * 队列的数组
     */
    private E[] data;
    /**
     * front队头
     * tail队尾
     */
    private int front, tail;

    /**
     * 构造函数，初始化队列
     *
     * @param capacity 数组的容量
     */
    public LoopQueueNoSize(int capacity) {
        // 由于不浪费空间，所以data静态数组的大小是capacity，而不是capacity+1
        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
    }

    /**
     * 构造函数，初始化队列，默认容量为10
     */
    public LoopQueueNoSize() {
        this(10);
    }

    @Override
    public int getSize() {
        // 此时的getSize的逻辑
        // 如果tail>=front，非常简单，队列中的元素个数就是tail-front
        // 如果tail<front，说明我们的循环队列"循环"起来了，此时队列中的元素个数为：tail-front+data.length
        // 也可以理解成，此时，data中没有元素的数目为front-tail
        // 整体元素个数就是data.length-(front-tail)=data.length+tail-front
        return tail >= front ? tail - front : tail - front + data.length;
    }

    /**
     * 获取数组队列的数组容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return data.length - 1;
    }

    /**
     * 判断队列是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    /**
     * 队列中添加元素
     *
     * @param e 添加的元素
     */
    @Override
    public void enqueue(E e) {
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
    }

    /**
     * 队列中删除数据(出队)
     *
     * @return 删除队列的元素
     */
    @Override
    public E dequeue() {
        // 判断队列是否为空
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        // 出队的低于队列长度的四分之一，则进缩容
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    /**
     * 获取队列的队头元素
     *
     * @return 队头元素
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty");
        }
        return data[front];
    }

    /**
     * 队列的扩容
     *
     * @param newCapacity 新的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity + 1];
        int sz = getSize();
        for (int i = 0; i < sz; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = sz;
    }

    /**
     * 格式化输出循环队列
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        res.append(String.format("Queue:size = %d, capacity = %d \n", getSize(), getCapacity()));
        res.append("front [");
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            res.append(data[i]);
            // 指向不是最后一个元素
            if ((i + 1) % data.length != tail) {
                res.append(",");
            }
        }
        res.append("] tail");
        return res.toString();
    }

    public static void main(String[] args) {
        LoopQueueNoSize<Integer> queue = new LoopQueueNoSize<>();
        for (int i = 0; i < 10; i++) {
            // 入队
            queue.enqueue(i);
            System.out.println(queue);
            if (i % 3 == 2) {
                // 出队
                queue.dequeue();
                System.out.println(queue);
            }
        }
    }
}

双端队列 Deque

  • 可以在队列的两端添加元素，addFront、addLast
  • 可以在队列的两端删除元素，removeFront，removeLast

双端队列的实现

对于双端队列，其实removeFront和队列中dequeue是一样的；addLast和队列enqueue是一样的。关键是实现addFront和removeLast两个方法，做出添加和删除操作以后，front和last。

使用size来表示双端队列中的元素个数，于此同时，我们的双端队列不浪费空间。

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
package demo.structure.queue;

/**
 * 双端队列
 *
 * @author jinglv
 * @date 2021/03/16
 */
public class Deque<E> {
    /**
     * 队列中的元素数据
     */
    private E[] data;
    /**
     * front 队首
     * tail 队尾
     */
    private int front, tail;
    /**
     * 队列中元素的个数
     */
    private int size;

    /**
     * 构造函数--队列初始化
     *
     * @param capacity 容量
     */
    public Deque(int capacity) {
        // 使用size，Deque实现不浪费空间
        data = (E[]) new Object[capacity];
        front = 0;
        tail = 0;
        size = 0;
    }

    /**
     * 构造函数--队列初始化
     */
    public Deque() {
        this(10);
    }

    /**
     * 获取队列的容量
     *
     * @return 容量
     */
    public int getCapacity() {
        return data.length;
    }

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

    /**
     * 获取队列中元素的个数
     *
     * @return 元素的个数
     */
    public int getSize() {
        return size;
    }

    /**
     * 队列队尾添加元素
     *
     * @param e 添加匀速
     */
    public void addLast(E e) {
        // 判断队列是否已满
        if (size == getCapacity()) {
            resize(getCapacity() * 2);
        }
        // 将元素添加到队尾
        data[tail] = e;
        // 队尾指针向后移
        tail = (tail + 1) % data.length;
        // 队列元素个数增加
        size++;
    }

    /**
     * 队列队首添加元素
     *
     * @param e 添加元素
     */
    public void addFront(E e) {
        // 判断队列是否已满
        if (size == getCapacity()) {
            resize(getCapacity() * 2);
        }
        // 我们首先要确定添加新元素的索引的位置，这个位置是front-1的地方
        // 但是要注意，如果front==0，新的位置是data.length-1的位置
        front = front == 0 ? data.length - 1 : front - 1;
        data[front] = e;
        size++;
    }

    /**
     * 队列队首删除元素
     *
     * @return 删除元素
     */
    public E removeFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        // 获取删除的元素
        E ret = data[front];
        // 将队首的元素置为null
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    /**
     * 队列队尾删除元素
     *
     * @return 删除元素
     */
    public E removeLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        // 计算删除掉队尾元素以后，新的tail位置
        tail = tail == 0 ? data.length - 1 : tail - 1;
        // 获取删除的元素
        E ret = data[tail];
        data[tail] = null;
        size--;
        if (getSize() == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    /**
     * 获取队首的元素
     *
     * @return 队首元素
     */
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        return data[front];
    }

    /**
     * 获取队尾的元素
     *
     * @return 队尾元素
     */
    public E getLast() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue");
        }
        // 因为tail指向的是队尾的下一个位置，我们需要计算下一个真正队尾元素的索引
        int index = tail == 0 ? data.length - 1 : tail - 1;
        return data[index];
    }

    /**
     * 队列扩容
     *
     * @param newCapacity 新的容量
     */
    private void resize(int newCapacity) {
        E[] newData = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newData[i] = data[(i + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    /**
     * 格式化输出队列
     *
     * @return String
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Queue:size=%d,capacity=%d", getSize(), getCapacity()));
        builder.append("front [");
        for (int i = 0; i < size; i++) {
            builder.append(data[(i + front) % data.length]);
            if (i != size - 1) {
                builder.append(",");
            }
        }
        builder.append("] tail");
        return builder.toString();
    }

    public static void main(String[] args) {
        // 双端队列测试红，偶数从队尾加入，奇数从队首加入
        Deque<Integer> dq = new Deque<>();
        for (int i = 0; i < 16; i++) {
            if (i % 2 == 0) {
                dq.addLast(i);
            } else {
                dq.addFront(i);
            }
            System.out.println(dq);
        }
        // 之后，我们依次从队首和队尾轮流删除元素
        System.out.println();
        for (int i = 0; !dq.isEmpty(); i++) {
            if (i % 2 == 0) {
                dq.removeFront();
            } else {
                dq.removeLast();
            }
            System.out.println(dq);
        }
    }
}