Design Circular Deque Python Solution

LeetCode 641, Medium. Topics: Array, Linked List, Design, Queue. View on LeetCode. Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 641   # by problem number
lcpy gen -s design_circular_deque   # by problem name

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.

Examples

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.

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class MyCircularDeque:
    # Fixed-size ring buffer: head is the front slot, size tracks occupancy.
    # All operations are O(1) time and the buffer holds at most k ints.
    def __init__(self, k: int) -> None:
        self.buf: list[int] = [-1] * k
        self.capacity = k
        self.size = 0
        self.head = 0

    def insert_front(self, value: int) -> bool:
        if self.is_full():
            return False
        self.head = (self.head - 1) % self.capacity
        self.buf[self.head] = value
        self.size += 1
        return True

    def insert_last(self, value: int) -> bool:
        if self.is_full():
            return False
        self.buf[(self.head + self.size) % self.capacity] = value
        self.size += 1
        return True

    def delete_front(self) -> bool:
        if self.is_empty():
            return False
        self.head = (self.head + 1) % self.capacity
        self.size -= 1
        return True

    def delete_last(self) -> bool:
        if self.is_empty():
            return False
        self.size -= 1
        return True

    def get_front(self) -> int:
        if self.is_empty():
            return -1
        return self.buf[self.head]

    def get_rear(self) -> int:
        if self.is_empty():
            return -1
        return self.buf[(self.head + self.size - 1) % self.capacity]

    def is_empty(self) -> bool:
        return self.size == 0

    def is_full(self) -> bool:
        return self.size == self.capacity

Complexity

Time	Space
-	-

Welcome

Getting Started

Practice

CLI

Catalog

Contributing

Troubleshooting

Design Circular Deque Python Solution

Problem

Examples

Constraints

Solution

Complexity

Tags

​Problem

​Examples

​Constraints

​Solution

​Complexity

​Tags

Problem

Examples

Constraints

Solution

Complexity

Tags