641. Design Circular Deque
Explanation
To design a circular deque, we can use a doubly linked list where each node represents an element in the deque. We will also maintain pointers to the front and rear of the deque for easy insertion and deletion operations.
For each operation provided in the problem statement, we will implement the necessary functionality to maintain the circular nature of the deque. We will handle edge cases such as checking if the deque is full or empty.
Time Complexity:
- Insertion and deletion operations: O(1)
- Checking if the deque is full or empty: O(1)
Space Complexity:
- O(k) where k is the maximum size of the deque.
class MyCircularDeque {
class Node {
int val;
Node next;
Node prev;
public Node(int val) {
this.val = val;
}
}
Node front;
Node rear;
int capacity;
int size;
public MyCircularDeque(int k) {
capacity = k;
size = 0;
front = new Node(-1);
rear = new Node(-1);
front.next = rear;
rear.prev = front;
}
public boolean insertFront(int value) {
if (isFull()) return false;
Node newNode = new Node(value);
newNode.next = front.next;
newNode.prev = front;
front.next.prev = newNode;
front.next = newNode;
size++;
return true;
}
public boolean insertLast(int value) {
if (isFull()) return false;
Node newNode = new Node(value);
newNode.prev = rear.prev;
newNode.next = rear;
rear.prev.next = newNode;
rear.prev = newNode;
size++;
return true;
}
public boolean deleteFront() {
if (isEmpty()) return false;
Node toDelete = front.next;
front.next = toDelete.next;
toDelete.next.prev = front;
size--;
return true;
}
public boolean deleteLast() {
if (isEmpty()) return false;
Node toDelete = rear.prev;
rear.prev = toDelete.prev;
toDelete.prev.next = rear;
size--;
return true;
}
public int getFront() {
return front.next.val;
}
public int getRear() {
return rear.prev.val;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.