1 双端队列介绍
既能头出也能头入，既能尾出也能尾入。
2 双链表实现双端队列
我自己预先写了一个解法：
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
class MyCircularDeque {
class Node {
int val;
Node prev;
Node next;
public Node(int val, Node prev, Node next) {
this.val = val;
this.prev = prev;
this.next = next;
}
}
Node head;
Node tail;
int size;
int maxN;
public MyCircularDeque(int k) {
size = 0;
maxN = k;
}
public boolean insertFront(int value) {
if (isFull()) return false;
Node n = new Node(value, null, null);
if (head == null) {
head = n;
tail = n;
} else {
n.next = head;
head.prev = n;
head = n;
}
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
Node n = new Node(value, null, null);
if (tail == null) {
head = tail = n;
} else {
tail.next = n;
n.prev = tail;
tail = n;
}
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
Node cur = head.next;
if (cur != null) {
head.next.prev = null;
head = cur;
} else {
head = null;
tail = null;
}
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
Node newLast = tail.prev;
if (newLast != null) {
tail.prev.next = null;
tail = newLast;
} else {
head = null;
tail = null;
}
size--;
return true;
}
public int getFront() {
if (isEmpty()) return -1;
return head.val;
}
public int getRear() {
if (isEmpty()) return -1;
return tail.val;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == maxN;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
可以直接用LinkedList实现的，下面是代码：
注：其实LinkedList底部就是Node
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
class MyCircularDeque {
private Deque<Integer> queue;
int size;
int limit;
public MyCircularDeque(int k) {
queue = new LinkedList<>();
size = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) return false;
queue.offerFirst(value);
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
queue.offerLast(value);
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
queue.pollFirst();
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
queue.pollLast();
size--;
return true;
}
public int getFront() {
if (isEmpty()) return -1;
return queue.peekFirst();
}
public int getRear() {
if (isEmpty()) return -1;
return queue.peekLast();
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
可见在这道题的测试用例上，不如自己实现Node更快。
但是这种直接用内部API的方法写起来不需要费什么脑子。
3 固定数组实现双端队列
题目一般会说清楚双端队列的大小，或者同时在这个队列中上限会有多少个，或者说明某一些操作会有至多多少次。
此时就可以用动态数组实现。
下面计算位置我用了取模运算，不用这个也可以，就用下面的逻辑：
头插：
l = l == 0 ? (limit - 1) : (l - 1);尾插：
r = r == limit - 1 ? 0 : (r + 1);头删：
l = (l == limit - 1) ? 0 : (l + 1);尾删：
r = r == 0 ? (limit - 1) : (r - 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
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
class MyCircularDeque {
private int[] deque;
int size, l, r, limit;
public MyCircularDeque(int k) {
deque = new int[k];
size = l = r = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) return false;
if (isEmpty()) {
l = r = 0;
} else {
l = (l + limit - 1) % limit;
}
deque[l] = value;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
if (isEmpty()) {
l = r = 0;
} else {
r = (r + 1) % limit;
}
deque[r] = value;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
l = (l + 1) % limit;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
r = (r + limit - 1) % limit;
size--;
return true;
}
public int getFront() {
if (isEmpty()) return -1;
return deque[l];
}
public int getRear() {
if (isEmpty()) return -1;
return deque[r];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque obj = new MyCircularDeque(k);
* boolean param_1 = obj.insertFront(value);
* boolean param_2 = obj.insertLast(value);
* boolean param_3 = obj.deleteFront();
* boolean param_4 = obj.deleteLast();
* int param_5 = obj.getFront();
* int param_6 = obj.getRear();
* boolean param_7 = obj.isEmpty();
* boolean param_8 = obj.isFull();
*/
