1. Description
Design your implementation of the circular double-ended queue (deque).
Your implementation should support following operations:
- MyCircularDeque(k): Constructor, set the size of the deque to be k.
- insertFront(): Adds an item at the front of Deque. Return true if the operation is successful.
- insertLast(): Adds an item at the rear of Deque. Return true if the operation is successful.
- deleteFront(): Deletes an item from the front of Deque. Return true if the operation is successful.
- deleteLast(): Deletes an item from the rear of Deque. Return true if the operation is successful.
- getFront(): Gets the front item from the Deque. If the deque is empty, return -1.
- getRear(): Gets the last item from Deque. If the deque is empty, return -1.
- isEmpty(): Checks whether Deque is empty or not.
- isFull(): Checks whether Deque is full or not.
2. Example
Example 1
MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
circularDeque.insertLast(1); // return true
circularDeque.insertLast(2); // return true
circularDeque.insertFront(3); // return true
circularDeque.insertFront(4); // return false, the queue is full
circularDeque.getRear(); // return 2
circularDeque.isFull(); // return true
circularDeque.deleteLast(); // return true
circularDeque.insertFront(4); // return true
circularDeque.getFront(); // return 4
3. Note
- All values will be in the range of [0, 1000].
- The number of operations will be in the range of [1, 1000].
- Please do not use the built-in Deque library.
4. Solutions
Doubly Linked List
Time complexity: O(1)
Space complexity: O(k)
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
| // double-linked list
class Node {
public:
int val;
Node* prev;
Node* next;
Node(int value = 0) : val(value), prev(nullptr), next(nullptr) {}
};
class MyCircularDeque {
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) : capacity(k), size(0) {
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (size < capacity) {
++size;
auto node = new Node(value);
node->prev = head;
node->next = head->next;
head->next = node;
node->next->prev = node;
return true;
} else {
return false;
}
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if (size < capacity) {
++size;
auto node = new Node(value);
node->next = tail;
node->prev = tail->prev;
tail->prev = node;
node->prev->next = node;
return true;
} else {
return false;
}
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if (size > 0) {
--size;
auto node = head->next;
node->next->prev = head;
head->next = node->next;
return true;
} else {
return false;
}
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if (size > 0) {
--size;
auto node = tail->prev;
node->prev->next = tail;
tail->prev = node->prev;
return true;
} else {
return false;
}
}
/** Get the front item from the deque. */
int getFront() {
if (size > 0) {
return head->next->val;
} else {
return -1;
}
}
/** Get the last item from the deque. */
int getRear() {
if (size > 0) {
return tail->prev->val;
} else {
return -1;
}
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return size == 0;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
return size == capacity;
}
private:
int capacity;
int size;
Node* head;
Node* tail;
};
|
Time complexity: O(1)
Space complexity: O(k)
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
| // array, so we don't need to create new nodes
class MyCircularDeque {
public:
/** Initialize your data structure here. Set the size of the deque to be k. */
MyCircularDeque(int k) : size(0), capacity(k), headIndex(0), tailIndex(1) {
values = vector<int>(k);
}
/** Adds an item at the front of Deque. Return true if the operation is successful. */
bool insertFront(int value) {
if (isFull()) {
return false;
} else {
++size;
values[headIndex] = value;
headIndex = (headIndex + capacity - 1) % capacity;
return true;
}
}
/** Adds an item at the rear of Deque. Return true if the operation is successful. */
bool insertLast(int value) {
if (isFull()) {
return false;
} else {
++size;
values[tailIndex] = value;
tailIndex = (tailIndex + 1) % capacity;
return true;
}
}
/** Deletes an item from the front of Deque. Return true if the operation is successful. */
bool deleteFront() {
if (isEmpty()) {
return false;
} else {
--size;
headIndex = (headIndex + 1) % values.size();
return true;
}
}
/** Deletes an item from the rear of Deque. Return true if the operation is successful. */
bool deleteLast() {
if (isEmpty()) {
return false;
} else {
--size;
tailIndex = (tailIndex + values.size() - 1) % values.size();
return true;
}
}
/** Get the front item from the deque. */
int getFront() {
return isEmpty() ? -1 : values[(headIndex + 1) % capacity];
}
/** Get the last item from the deque. */
int getRear() {
return isEmpty() ? -1 : values[(tailIndex + capacity - 1) % capacity];
}
/** Checks whether the circular deque is empty or not. */
bool isEmpty() {
return size == 0;
}
/** Checks whether the circular deque is full or not. */
bool isFull() {
return size == capacity;
}
private:
int size;
int capacity;
int headIndex; // headIndex is the index to hold the next front value
int tailIndex; // tailIndex is the index to hold the next back value
vector<int> values;
};
|