Sponsored
Sponsored
This approach involves using a fixed-size array to represent the deque. We'll maintain two indices, front and rear, to manage the current front and last positions in the deque. Operations like insertions and deletions are performed by adjusting these indices while ensuring they wrap around using the modulo operation as necessary to remain within the array bounds.
Time Complexity: O(1) for each operation.
Space Complexity: O(k), where k is the capacity of the deque.
1#include <vector>
2using namespace std;
3
4class MyCircularDeque {
5 vector<int> data;
6 int front;
7 int rear;
8 int size;
9 int capacity;
10
11public:
12 MyCircularDeque(int k) : data(k), front(0), rear(0), size(0), capacity(k) {}
13
14 bool insertFront(int value) {
15 if (isFull()) return false;
16 front = (front - 1 + capacity) % capacity;
17 data[front] = value;
18 size++;
19 return true;
20 }
21
22 bool insertLast(int value) {
23 if (isFull()) return false;
24 data[rear] = value;
25 rear = (rear + 1) % capacity;
26 size++;
27 return true;
28 }
29
30 bool deleteFront() {
31 if (isEmpty()) return false;
32 front = (front + 1) % capacity;
33 size--;
34 return true;
35 }
36
37 bool deleteLast() {
38 if (isEmpty()) return false;
39 rear = (rear - 1 + capacity) % capacity;
40 size--;
41 return true;
42 }
43
44 int getFront() {
45 if (isEmpty()) return -1;
46 return data[front];
47 }
48
49 int getRear() {
50 if (isEmpty()) return -1;
51 return data[(rear - 1 + capacity) % capacity];
52 }
53
54 bool isEmpty() {
55 return size == 0;
56 }
57
58 bool isFull() {
59 return size == capacity;
60 }
61};C++ implementation utilizes a vector for the circular array. All deque operations are facilitated using vector functions. Insertions and deletions adjust the front and rear indices while checking the size for fullness or emptiness.
This approach makes use of a doubly linked list to implement the deque. This is particularly effective because it offers dynamic memory usage which can grow or shrink with the number of elements, instead of relying on a pre-allocated fixed-size structure as with arrays.
Time Complexity: O(1) for all operations.
Space Complexity: O(n), where n is the number of elements currently in the deque (potentially more efficient if n is much less than the initial capacity).
1 public int Value;
public Node Next;
public Node Prev;
public Node(int value) {
Value = value;
Next = Prev = null;
}
}
public class MyCircularDeque {
private Node front;
private Node rear;
private int size;
private int capacity;
public MyCircularDeque(int k) {
front = rear = null;
size = 0;
capacity = k;
}
public bool InsertFront(int value) {
if (IsFull()) return false;
Node node = new Node(value);
node.Next = front;
if (front != null) front.Prev = node;
front = node;
if (rear == null) rear = node;
size++;
return true;
}
public bool InsertLast(int value) {
if (IsFull()) return false;
Node node = new Node(value);
node.Prev = rear;
if (rear != null) rear.Next = node;
rear = node;
if (front == null) front = node;
size++;
return true;
}
public bool DeleteFront() {
if (IsEmpty()) return false;
front = front.Next;
if (front != null) front.Prev = null;
else rear = null;
size--;
return true;
}
public bool DeleteLast() {
if (IsEmpty()) return false;
rear = rear.Prev;
if (rear != null) rear.Next = null;
else front = null;
size--;
return true;
}
public int GetFront() {
return IsEmpty() ? -1 : front.Value;
}
public int GetRear() {
return IsEmpty() ? -1 : rear.Value;
}
public bool IsEmpty() {
return size == 0;
}
public bool IsFull() {
return size == capacity;
}
}In C#, the linked list model for the deque supports dynamic sizing, letting each node connect bidirectionally, which allows rapid pointer modifications for diverse operations at both front and end.