Description#
Design your implementation of the circular double-ended queue (deque).
Implement the MyCircularDeque class:
MyCircularDeque(int k) Initializes the deque with a maximum size of k.boolean insertFront() Adds an item at the front of Deque. Returns true if the operation is successful, or false otherwise.boolean insertLast() Adds an item at the rear of Deque. Returns true if the operation is successful, or false otherwise.boolean deleteFront() Deletes an item from the front of Deque. Returns true if the operation is successful, or false otherwise.boolean deleteLast() Deletes an item from the rear of Deque. Returns true if the operation is successful, or false otherwise.int getFront() Returns the front item from the Deque. Returns -1 if the deque is empty.int getRear() Returns the last item from Deque. Returns -1 if the deque is empty.boolean isEmpty() Returns true if the deque is empty, or false otherwise.boolean isFull() Returns true if the deque is full, or false otherwise.
Example 1:
Input
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 2, true, true, true, 4]
Explanation
MyCircularDeque myCircularDeque = new MyCircularDeque(3);
myCircularDeque.insertLast(1); // return True
myCircularDeque.insertLast(2); // return True
myCircularDeque.insertFront(3); // return True
myCircularDeque.insertFront(4); // return False, the queue is full.
myCircularDeque.getRear(); // return 2
myCircularDeque.isFull(); // return True
myCircularDeque.deleteLast(); // return True
myCircularDeque.insertFront(4); // return True
myCircularDeque.getFront(); // return 4
Constraints:
1 <= k <= 10000 <= value <= 1000- At most
2000 calls will be made to insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull.
Solutions#
Solution 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
82
83
84
85
86
87
88
89
90
91
92
| class MyCircularDeque:
def __init__(self, k: int):
"""
Initialize your data structure here. Set the size of the deque to be k.
"""
self.q = [0] * k
self.front = 0
self.size = 0
self.capacity = k
def insertFront(self, value: int) -> bool:
"""
Adds an item at the front of Deque. Return true if the operation is successful.
"""
if self.isFull():
return False
if not self.isEmpty():
self.front = (self.front - 1 + self.capacity) % self.capacity
self.q[self.front] = value
self.size += 1
return True
def insertLast(self, value: int) -> bool:
"""
Adds an item at the rear of Deque. Return true if the operation is successful.
"""
if self.isFull():
return False
idx = (self.front + self.size) % self.capacity
self.q[idx] = value
self.size += 1
return True
def deleteFront(self) -> bool:
"""
Deletes an item from the front of Deque. Return true if the operation is successful.
"""
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def deleteLast(self) -> bool:
"""
Deletes an item from the rear of Deque. Return true if the operation is successful.
"""
if self.isEmpty():
return False
self.size -= 1
return True
def getFront(self) -> int:
"""
Get the front item from the deque.
"""
if self.isEmpty():
return -1
return self.q[self.front]
def getRear(self) -> int:
"""
Get the last item from the deque.
"""
if self.isEmpty():
return -1
idx = (self.front + self.size - 1) % self.capacity
return self.q[idx]
def isEmpty(self) -> bool:
"""
Checks whether the circular deque is empty or not.
"""
return self.size == 0
def isFull(self) -> bool:
"""
Checks whether the circular deque is full or not.
"""
return self.size == self.capacity
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()
|
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
| class MyCircularDeque {
private int[] q;
private int front;
private int size;
private int capacity;
/** Initialize your data structure here. Set the size of the deque to be k. */
public MyCircularDeque(int k) {
q = new int[k];
capacity = k;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
public boolean insertFront(int value) {
if (isFull()) {
return false;
}
if (!isEmpty()) {
front = (front - 1 + capacity) % capacity;
}
q[front] = value;
++size;
return true;
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
public boolean insertLast(int value) {
if (isFull()) {
return false;
}
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
public boolean deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
--size;
return true;
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
public boolean deleteLast() {
if (isEmpty()) {
return false;
}
--size;
return true;
}
/** Get the front item from the deque. */
public int getFront() {
if (isEmpty()) {
return -1;
}
return q[front];
}
/** Get the last item from the deque. */
public int getRear() {
if (isEmpty()) {
return -1;
}
int idx = (front + size - 1) % capacity;
return q[idx];
}
/** Checks whether the circular deque is empty or not. */
public boolean isEmpty() {
return size == 0;
}
/** Checks whether the circular deque is full or not. */
public boolean isFull() {
return size == capacity;
}
}
/**
* 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();
*/
|
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
| class MyCircularDeque {
public:
vector<int> q;
int front = 0;
int size = 0;
int capacity = 0;
MyCircularDeque(int k) {
q.assign(k, 0);
capacity = k;
}
bool insertFront(int value) {
if (isFull()) {
return false;
}
if (!isEmpty()) {
front = (front - 1 + capacity) % capacity;
}
q[front] = value;
++size;
return true;
}
bool insertLast(int value) {
if (isFull()) {
return false;
}
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
bool deleteFront() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
--size;
return true;
}
bool deleteLast() {
if (isEmpty()) {
return false;
}
--size;
return true;
}
int getFront() {
return isEmpty() ? -1 : q[front];
}
int getRear() {
return isEmpty() ? -1 : q[(front + size - 1) % capacity];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};
/**
* Your MyCircularDeque object will be instantiated and called as such:
* MyCircularDeque* obj = new MyCircularDeque(k);
* bool param_1 = obj->insertFront(value);
* bool param_2 = obj->insertLast(value);
* bool param_3 = obj->deleteFront();
* bool param_4 = obj->deleteLast();
* int param_5 = obj->getFront();
* int param_6 = obj->getRear();
* bool param_7 = obj->isEmpty();
* bool param_8 = obj->isFull();
*/
|
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
| type MyCircularDeque struct {
q []int
size int
front int
capacity int
}
func Constructor(k int) MyCircularDeque {
q := make([]int, k)
return MyCircularDeque{q, 0, 0, k}
}
func (this *MyCircularDeque) InsertFront(value int) bool {
if this.IsFull() {
return false
}
if !this.IsEmpty() {
this.front = (this.front - 1 + this.capacity) % this.capacity
}
this.q[this.front] = value
this.size++
return true
}
func (this *MyCircularDeque) InsertLast(value int) bool {
if this.IsFull() {
return false
}
idx := (this.front + this.size) % this.capacity
this.q[idx] = value
this.size++
return true
}
func (this *MyCircularDeque) DeleteFront() bool {
if this.IsEmpty() {
return false
}
this.front = (this.front + 1) % this.capacity
this.size -= 1
return true
}
func (this *MyCircularDeque) DeleteLast() bool {
if this.IsEmpty() {
return false
}
this.size -= 1
return true
}
func (this *MyCircularDeque) GetFront() int {
if this.IsEmpty() {
return -1
}
return this.q[this.front]
}
func (this *MyCircularDeque) GetRear() int {
if this.IsEmpty() {
return -1
}
return this.q[(this.front+this.size-1)%this.capacity]
}
func (this *MyCircularDeque) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularDeque) IsFull() bool {
return this.size == this.capacity
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.InsertFront(value);
* param_2 := obj.InsertLast(value);
* param_3 := obj.DeleteFront();
* param_4 := obj.DeleteLast();
* param_5 := obj.GetFront();
* param_6 := obj.GetRear();
* param_7 := obj.IsEmpty();
* param_8 := obj.IsFull();
*/
|
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
| class MyCircularDeque {
private vals: number[];
private length: number;
private size: number;
private start: number;
private end: number;
constructor(k: number) {
this.vals = new Array(k).fill(0);
this.start = 0;
this.end = 0;
this.length = 0;
this.size = k;
}
insertFront(value: number): boolean {
if (this.isFull()) {
return false;
}
if (this.start === 0) {
this.start = this.size - 1;
} else {
this.start--;
}
this.vals[this.start] = value;
this.length++;
return true;
}
insertLast(value: number): boolean {
if (this.isFull()) {
return false;
}
this.vals[this.end] = value;
this.length++;
if (this.end + 1 === this.size) {
this.end = 0;
} else {
this.end++;
}
return true;
}
deleteFront(): boolean {
if (this.isEmpty()) {
return false;
}
if (this.start + 1 === this.size) {
this.start = 0;
} else {
this.start++;
}
this.length--;
return true;
}
deleteLast(): boolean {
if (this.isEmpty()) {
return false;
}
if (this.end === 0) {
this.end = this.size - 1;
} else {
this.end--;
}
this.length--;
return true;
}
getFront(): number {
if (this.isEmpty()) {
return -1;
}
return this.vals[this.start];
}
getRear(): number {
if (this.isEmpty()) {
return -1;
}
if (this.end === 0) {
return this.vals[this.size - 1];
}
return this.vals[this.end - 1];
}
isEmpty(): boolean {
return this.length === 0;
}
isFull(): boolean {
return this.length === this.size;
}
}
/**
* Your MyCircularDeque object will be instantiated and called as such:
* var obj = new MyCircularDeque(k)
* var param_1 = obj.insertFront(value)
* var param_2 = obj.insertLast(value)
* var param_3 = obj.deleteFront()
* var param_4 = obj.deleteLast()
* var param_5 = obj.getFront()
* var param_6 = obj.getRear()
* var param_7 = obj.isEmpty()
* var param_8 = obj.isFull()
*/
|
