# Design Circular Deque **Difficulty:** MEDIUM [External](https://leetcode.com/problems/design-circular-deque) Canonical: https://scaleengineer.com/dsa/problems/design-circular-deque **Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design) **Data structures:** Array, Linked List, Queue --- ## Problem 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 <= 1000` * `0 <= value <= 1000` * At most `2000` calls will be made to `insertFront`, `insertLast`, `deleteFront`, `deleteLast`, `getFront`, `getRear`, `isEmpty`, `isFull`. # Approaches ## Doubly Linked List Implementation This approach uses a doubly linked list to store the deque elements. A custom `Node` class is created with `val`, `prev`, and `next` pointers. The `MyCircularDeque` class maintains pointers to the `head` and `tail` of the list, along with the current `size` and the maximum `capacity`. **Time:** O(1) for all operations. Each operation (insert, delete, get) involves a constant number of pointer manipulations, independent of the deque's size. · **Space:** O(k), where `k` is the capacity. In the worst case, we store `k` nodes, and each node requires constant extra space for its value and two pointers. **Pros:** Conceptually straightforward for insertions and deletions at both ends.; Memory is allocated on-demand, so no space is wasted if the deque is not full (unlike a pre-allocated array). **Cons:** Higher memory overhead per element due to storing two pointers (`prev`, `next`) in each node.; Can be slower in practice due to the cost of dynamic memory allocation/deallocation for each node and poor cache locality, as nodes are not stored contiguously in memory. ### Explanation In this implementation, each element of the deque is a `Node` object in a doubly linked list. This allows for efficient additions and removals from both ends (head and tail) by simply manipulating pointers. We keep track of the current number of elements with a `size` variable to check against the `capacity` for `isFull()` and `isEmpty()` conditions. All operations like insertion, deletion, and retrieval from either end take constant time because they only involve a few pointer reassignments, regardless of the deque's size. ```java class MyCircularDeque { private class Node { int val; Node prev; Node next; Node(int val) { this.val = val; } } private Node head; private Node tail; private int size; private final int capacity; public MyCircularDeque(int k) { this.capacity = k; this.size = 0; this.head = null; this.tail = null; } public boolean insertFront(int value) { if (isFull()) { return false; } Node newNode = new Node(value); if (isEmpty()) { head = tail = newNode; } else { newNode.next = head; head.prev = newNode; head = newNode; } size++; return true; } public boolean insertLast(int value) { if (isFull()) { return false; } Node newNode = new Node(value); if (isEmpty()) { head = tail = newNode; } else { tail.next = newNode; newNode.prev = tail; tail = newNode; } size++; return true; } public boolean deleteFront() { if (isEmpty()) { return false; } if (size == 1) { head = tail = null; } else { head = head.next; head.prev = null; } size--; return true; } public boolean deleteLast() { if (isEmpty()) { return false; } if (size == 1) { head = tail = null; } else { tail = tail.prev; tail.next = null; } size--; return true; } public int getFront() { if (isEmpty()) { return -1; } return head.val; } public int getRear() { if (isEmpty()) { return -1; } return tail.val; } public boolean isEmpty() { return size == 0; } public boolean isFull() { return size == capacity; } } ``` ### Algorithm - Define a private `Node` class containing an integer `val`, and two pointers, `prev` and `next`. - The `MyCircularDeque` class will maintain `head` and `tail` node pointers, a `size` counter, and the `capacity`. - **Constructor `MyCircularDeque(k)`**: Initializes `capacity` to `k`, `size` to 0, and `head` and `tail` to `null`. - **`insertFront(value)`**: - If `isFull()`, return `false`. - Create a new `Node` with the given `value`. - If `isEmpty()`, set both `head` and `tail` to the new node. - Otherwise, set the new node's `next` to the current `head`, the current `head`'s `prev` to the new node, and update `head` to be the new node. - Increment `size` and return `true`. - **`insertLast(value)`**: - If `isFull()`, return `false`. - Create a new `Node`. - If `isEmpty()`, set both `head` and `tail` to the new node. - Otherwise, link the new node after the current `tail` and update `tail`. - Increment `size` and return `true`. - **`deleteFront()`**: - If `isEmpty()`, return `false`. - If `size` is 1, set `head` and `tail` to `null`. - Otherwise, move `head` to `head.next` and set the new `head`'s `prev` to `null`. - Decrement `size` and return `true`. - **`deleteLast()`**: - If `isEmpty()`, return `false`. - If `size` is 1, set `head` and `tail` to `null`. - Otherwise, move `tail` to `tail.prev` and set the new `tail`'s `next` to `null`. - Decrement `size` and return `true`. - **`getFront()`**: If `isEmpty()`, return -1; otherwise, return `head.val`. - **`getRear()`**: If `isEmpty()`, return -1; otherwise, return `tail.val`. - **`isEmpty()`**: Return `true` if `size == 0`. - **`isFull()`**: Return `true` if `size == capacity`. ## Array with Two Pointers (Circular Buffer) This is the most common and efficient approach, often called a circular buffer. It uses a fixed-size array to store the elements. Two pointers, `front` and `rear`, are used to keep track of the start and end of the deque. The circular nature is achieved by using the modulo operator for pointer arithmetic, which allows the pointers to wrap around the array. **Time:** O(1) for all operations. Each operation consists of a few arithmetic calculations and array accesses, which take constant time. · **Space:** O(k), where `k` is the capacity. The space is used for the underlying array, which is allocated at initialization. **Pros:** Extremely fast due to direct indexing and contiguous memory layout, which leads to excellent cache performance.; Lower memory overhead per element compared to the linked list approach.; No dynamic memory allocation/deallocation is needed during operations (after the initial setup). **Cons:** The size of the deque is fixed at initialization.; Space is pre-allocated and might be wasted if the deque consistently holds fewer elements than its capacity. ### Explanation This implementation uses a fixed-size array and two pointers, `front` and `rear`, to manage the elements. The `front` pointer indicates the index of the first element, and the `rear` pointer indicates the index of the next available slot for an insertion at the end. A `count` variable is used to track the number of elements, which simplifies checking for empty and full conditions. The key to this approach is the use of the modulo operator (`%`) to wrap the pointers around the array, creating a circular effect. This avoids the need to shift elements on insertion or deletion, making all operations highly efficient. ```java class MyCircularDeque { private final int[] data; private int front; private int rear; private int count; private final int capacity; public MyCircularDeque(int k) { this.data = new int[k]; this.capacity = k; this.front = 0; this.rear = 0; // Points to the next available slot this.count = 0; } public boolean insertFront(int value) { if (isFull()) { return false; } // Move front pointer backwards circularly front = (front - 1 + capacity) % capacity; data[front] = value; count++; return true; } public boolean insertLast(int value) { if (isFull()) { return false; } data[rear] = value; // Move rear pointer forwards circularly rear = (rear + 1) % capacity; count++; return true; } public boolean deleteFront() { if (isEmpty()) { return false; } // Move front pointer forwards circularly front = (front + 1) % capacity; count--; return true; } public boolean deleteLast() { if (isEmpty()) { return false; } // Move rear pointer backwards circularly rear = (rear - 1 + capacity) % capacity; count--; return true; } public int getFront() { if (isEmpty()) { return -1; } return data[front]; } public int getRear() { if (isEmpty()) { return -1; } // The last element is at the index before rear int lastElementIndex = (rear - 1 + capacity) % capacity; return data[lastElementIndex]; } public boolean isEmpty() { return count == 0; } public boolean isFull() { return count == capacity; } } ``` ### Algorithm - Initialize an integer array `data` of size `k`, and three integer variables: `front = 0`, `rear = 0`, and `count = 0`. - **`insertFront(value)`**: - If `isFull()` (`count == capacity`), return `false`. - Calculate the new front index: `front = (front - 1 + capacity) % capacity`. - Place the `value` at `data[front]`. - Increment `count` and return `true`. - **`insertLast(value)`**: - If `isFull()`, return `false`. - Place the `value` at `data[rear]`. - Update the rear index: `rear = (rear + 1) % capacity`. - Increment `count` and return `true`. - **`deleteFront()`**: - If `isEmpty()` (`count == 0`), return `false`. - Update the front index: `front = (front + 1) % capacity`. - Decrement `count` and return `true`. - **`deleteLast()`**: - If `isEmpty()`, return `false`. - Update the rear index: `rear = (rear - 1 + capacity) % capacity`. - Decrement `count` and return `true`. - **`getFront()`**: If `isEmpty()`, return -1; otherwise, return `data[front]`. - **`getRear()`**: If `isEmpty()`, return -1; otherwise, return the element at the index before `rear`: `data[(rear - 1 + capacity) % capacity]`. - **`isEmpty()`**: Return `true` if `count == 0`. - **`isFull()`**: Return `true` if `count == capacity`. # Solutions ### Java ```java public class Design_Circular_Deque { // ref: https://www.cnblogs.com/Dylan-Java-NYC/p/12079440.html class MyCircularDeque { int [] arr ; int start ; int end ; int len ; int k ; /** Initialize your data structure here. Set the size of the deque to be k. */ public MyCircularDeque ( int k ) { arr = new int [ k ]; start = - 1 ; end = - 1 ; len = 0 ; this . k = 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 ( start == - 1 ){ start = 0 ; } else { start = ( start - 1 + k ) % k ; } arr [ start ] = value ; if ( end == - 1 ){ end = start ; } len ++; 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 ; } end = ( end + 1 ) % k ; arr [ end ] = value ; if ( start == - 1 ){ start = end ; } len ++; return true ; } /** Deletes an item from the front of Deque. Return true if the operation is successful. */ public boolean deleteFront () { if ( isEmpty ()){ return false ; } start = ( start + 1 ) % k ; len --; return true ; } /** Deletes an item from the rear of Deque. Return true if the operation is successful. */ public boolean deleteLast () { if ( isEmpty ()){ return false ; } end = ( end - 1 + k ) % k ; len --; return true ; } /** Get the front item from the deque. */ public int getFront () { return isEmpty () ? - 1 : arr [ start ]; } /** Get the last item from the deque. */ public int getRear () { return isEmpty () ? - 1 : arr [ end ]; } /** Checks whether the circular deque is empty or not. */ public boolean isEmpty () { return len == 0 ; } /** Checks whether the circular deque is full or not. */ public boolean isFull () { return len == k ; } } /** * 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(); */ } ############ 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(); */ ``` ### Python ```python 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 # basically, welcome to overwirte it behind frond 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 # basically, welcome to overwirte 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() ############ class MyCircularDeque ( object ): def __init__ ( self , k ): """ Initialize your data structure here. Set the size of the deque to be k. :type k: int """ self . queue = [] self . size = k self . front = 0 self . rear = 0 def insertFront ( self , value ): """ Adds an item at the front of Deque. Return true if the operation is successful. :type value: int :rtype: bool """ if not self . isFull (): self . queue . insert ( 0 , value ) self . rear += 1 return True else : return False def insertLast ( self , value ): """ Adds an item at the rear of Deque. Return true if the operation is successful. :type value: int :rtype: bool """ if not self . isFull (): self . queue . append ( value ) self . rear += 1 return True else : return False def deleteFront ( self ): """ Deletes an item from the front of Deque. Return true if the operation is successful. :rtype: bool """ if not self . isEmpty (): self . queue . pop ( 0 ) self . rear -= 1 return True else : return False def deleteLast ( self ): """ Deletes an item from the rear of Deque. Return true if the operation is successful. :rtype: bool """ if not self . isEmpty (): self . queue . pop () self . rear -= 1 return True else : return False def getFront ( self ): """ Get the front item from the deque. :rtype: int """ if self . isEmpty (): return - 1 else : return self . queue [ self . front ] def getRear ( self ): """ Get the last item from the deque. :rtype: int """ if self . isEmpty (): return - 1 else : return self . queue [ self . rear - 1 ] def isEmpty ( self ): """ Checks whether the circular deque is empty or not. :rtype: bool """ return self . front == self . rear def isFull ( self ): """ Checks whether the circular deque is full or not. :rtype: bool """ return self . rear - self . front == self . size # 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() ``` ### CPP ```cpp // OJ: https://leetcode.com/problems/design-circular-deque/ // Time: O(1) for all // Space: O(K) class MyCircularDeque { vector < int > q ; int begin = 0 , end = 0 , k , cnt = 0 ; public: MyCircularDeque ( int k ) : q ( k ), k ( k ) {} bool insertFront ( int value ) { if ( cnt == k ) return false ; begin = ( begin - 1 + k ) % k ; q [ begin ] = value ; ++ cnt ; return true ; } bool insertLast ( int value ) { if ( cnt == k ) return false ; q [ end ] = value ; end = ( end + 1 ) % k ; ++ cnt ; return true ; } bool deleteFront () { if ( cnt == 0 ) return false ; begin = ( begin + 1 ) % k ; -- cnt ; return true ; } bool deleteLast () { if ( cnt == 0 ) return false ; end = ( end - 1 + k ) % k ; -- cnt ; return true ; } int getFront () { if ( cnt == 0 ) return - 1 ; return q [ begin ]; } int getRear () { if ( cnt == 0 ) return - 1 ; return q [( end - 1 + k ) % k ]; } bool isEmpty () { return cnt == 0 ; } bool isFull () { return cnt == k ; } }; ```