Design Circular Deque

Med

#0595Time: 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.

Patterns

Design

Data structures

Array Linked List Queue

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class MyCircularDeque {2    private class Node {3        int val;4        Node prev;5        Node next;6        Node(int val) {7            this.val = val;8        }9    }10 11    private Node head;12    private Node tail;13    private int size;14    private final int capacity;15 16    public MyCircularDeque(int k) {17        this.capacity = k;18        this.size = 0;19        this.head = null;20        this.tail = null;21    }22 23    public boolean insertFront(int value) {24        if (isFull()) {25            return false;26        }27        Node newNode = new Node(value);28        if (isEmpty()) {29            head = tail = newNode;30        } else {31            newNode.next = head;32            head.prev = newNode;33            head = newNode;34        }35        size++;36        return true;37    }38 39    public boolean insertLast(int value) {40        if (isFull()) {41            return false;42        }43        Node newNode = new Node(value);44        if (isEmpty()) {45            head = tail = newNode;46        } else {47            tail.next = newNode;48            newNode.prev = tail;49            tail = newNode;50        }51        size++;52        return true;53    }54 55    public boolean deleteFront() {56        if (isEmpty()) {57            return false;58        }59        if (size == 1) {60            head = tail = null;61        } else {62            head = head.next;63            head.prev = null;64        }65        size--;66        return true;67    }68 69    public boolean deleteLast() {70        if (isEmpty()) {71            return false;72        }73        if (size == 1) {74            head = tail = null;75        } else {76            tail = tail.prev;77            tail.next = null;78        }79        size--;80        return true;81    }82 83    public int getFront() {84        if (isEmpty()) {85            return -1;86        }87        return head.val;88    }89 90    public int getRear() {91        if (isEmpty()) {92            return -1;93        }94        return tail.val;95    }96 97    public boolean isEmpty() {98        return size == 0;99    }100 101    public boolean isFull() {102        return size == capacity;103    }104}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class MyCircularDeque {2    private final int[] data;3    private int front;4    private int rear;5    private int count;6    private final int capacity;7 8    public MyCircularDeque(int k) {9        this.data = new int[k];10        this.capacity = k;11        this.front = 0;12        this.rear = 0; // Points to the next available slot13        this.count = 0;14    }15 16    public boolean insertFront(int value) {17        if (isFull()) {18            return false;19        }20        // Move front pointer backwards circularly21        front = (front - 1 + capacity) % capacity;22        data[front] = value;23        count++;24        return true;25    }26 27    public boolean insertLast(int value) {28        if (isFull()) {29            return false;30        }31        data[rear] = value;32        // Move rear pointer forwards circularly33        rear = (rear + 1) % capacity;34        count++;35        return true;36    }37 38    public boolean deleteFront() {39        if (isEmpty()) {40            return false;41        }42        // Move front pointer forwards circularly43        front = (front + 1) % capacity;44        count--;45        return true;46    }47 48    public boolean deleteLast() {49        if (isEmpty()) {50            return false;51        }52        // Move rear pointer backwards circularly53        rear = (rear - 1 + capacity) % capacity;54        count--;55        return true;56    }57 58    public int getFront() {59        if (isEmpty()) {60            return -1;61        }62        return data[front];63    }64 65    public int getRear() {66        if (isEmpty()) {67            return -1;68        }69        // The last element is at the index before rear70        int lastElementIndex = (rear - 1 + capacity) % capacity;71        return data[lastElementIndex];72    }73 74    public boolean isEmpty() {75        return count == 0;76    }77 78    public boolean isFull() {79        return count == capacity;80    }81}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1public 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(); */

1class 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()

1// 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 ; } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem