forked from algorithmzuo/algorithm-journey
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCircularDeque.java
More file actions
181 lines (154 loc) · 2.97 KB
/
CircularDeque.java
File metadata and controls
181 lines (154 loc) · 2.97 KB
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
package class016;
import java.util.Deque;
import java.util.LinkedList;
// 设计循环双端队列
// 测试链接 : https://leetcode.cn/problems/design-circular-deque/
public class CircularDeque {
// 提交时把类名、构造方法改成 : MyCircularDeque
// 其实内部就是双向链表
// 常数操作慢，但是leetcode数据量太小了，所以看不出劣势
class MyCircularDeque1 {
public Deque<Integer> deque = new LinkedList<>();
public int size;
public int limit;
public MyCircularDeque1(int k) {
size = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
} else {
deque.offerFirst(value);
size++;
return true;
}
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
} else {
deque.offerLast(value);
size++;
return true;
}
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
} else {
size--;
deque.pollFirst();
return true;
}
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
} else {
size--;
deque.pollLast();
return true;
}
}
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return deque.peekFirst();
}
}
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return deque.peekLast();
}
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
// 提交时把类名、构造方法改成 : MyCircularDeque
// 自己用数组实现，常数操作快，但是leetcode数据量太小了，看不出优势
class MyCircularDeque2 {
public int[] deque;
public int l, r, size, limit;
public MyCircularDeque2(int k) {
deque = new int[k];
l = r = size = 0;
limit = k;
}
public boolean insertFront(int value) {
if (isFull()) {
return false;
} else {
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
l = l == 0 ? (limit - 1) : (l - 1);
deque[l] = value;
}
size++;
return true;
}
}
public boolean insertLast(int value) {
if (isFull()) {
return false;
} else {
if (isEmpty()) {
l = r = 0;
deque[0] = value;
} else {
r = r == limit - 1 ? 0 : (r + 1);
deque[r] = value;
}
size++;
return true;
}
}
public boolean deleteFront() {
if (isEmpty()) {
return false;
} else {
l = (l == limit - 1) ? 0 : (l + 1);
size--;
return true;
}
}
public boolean deleteLast() {
if (isEmpty()) {
return false;
} else {
r = r == 0 ? (limit - 1) : (r - 1);
size--;
return true;
}
}
public int getFront() {
if (isEmpty()) {
return -1;
} else {
return deque[l];
}
}
public int getRear() {
if (isEmpty()) {
return -1;
} else {
return deque[r];
}
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == limit;
}
}
}