Design Circular Queue

Medium · Linked List · Explanation and code example

Singly Linked List

How it works

A singly linked list can also work, using less memory per node than a doubly linked list. We maintain a dummy head node and a pointer to the actual tail. New elements are added at the tail, and elements are removed from the front (after the dummy head). The only complication is updating the tail pointer when the queue becomes empty.

Steps

  1. Initialize a dummy node left, set right = left, and set space = k.
  2. For enQueue(value): If full, return false. Create a new node. If empty, set it as left.next and right. Otherwise, link it after right and update right. Decrement space and return true.
  3. For deQueue(): If empty, return false. Remove left.next by updating left.next to left.next.next. If left.next becomes null, reset right = left. Increment space and return true.
  4. For Front(): If empty, return -1. Otherwise, return left.next.val.
  5. For Rear(): If empty, return -1. Otherwise, return right.val.
  6. For isEmpty(): Return true if left.next is null.
  7. For isFull(): Return true if space equals 0.

Complexity

  • Time complexity:
    • O(n) time for initialization.
    • O(1) time for each enQueue(), deQueue(), Front(), Rear(), isEmpty() and isFull() function calls.
  • Space complexity: O(n)

Where n is the size of the queue.

Things to watch for

Incorrect Modulo Arithmetic for Wrap-Around

The circular nature requires careful modulo operations. A common mistake is forgetting to apply modulo when updating pointers, causing index out of bounds errors.

Confusing Empty and Full States

When using only front and rear pointers without a separate size variable, distinguishing between empty and full queue becomes ambiguous since both states can have front == rear.

Off-By-One Errors in Rear Initialization

Initializing rear to 0 instead of -1 causes the first element to be placed at index 1, wasting space and causing incorrect behavior.

Python code example

class ListNode:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

class MyCircularQueue:
    def __init__(self, k: int):
        self.space = k
        self.left = ListNode(0)
        self.right = self.left

    def enQueue(self, value: int) -> bool:
        if self.isFull(): return False

        cur = ListNode(value)
        if self.isEmpty():
            self.left.next = cur
            self.right = cur
        else:
            self.right.next = cur
            self.right = cur

        self.space -= 1
        return True

    def deQueue(self) -> bool:
        if self.isEmpty(): return False

        self.left.next = self.left.next.next
        if self.left.next is None:
            self.right = self.left

        self.space += 1
        return True

    def Front(self) -> int:
        if self.isEmpty(): return -1
        return self.left.next.val

    def Rear(self) -> int:
        if self.isEmpty(): return -1
        return self.right.val

    def isEmpty(self) -> bool:
        return self.left.next is None

    def isFull(self) -> bool:
        return self.space == 0

C++ code example

class MyCircularQueue {
private:
    struct ListNode {
        int val;
        ListNode* next;
        ListNode(int v) : val(v), next(nullptr) {}
    };

    int space;
    ListNode* left;
    ListNode* right;

public:
    MyCircularQueue(int k) {
        space = k;
        left = new ListNode(0);
        right = left;
    }

    bool enQueue(int value) {
        if (isFull()) return false;

        ListNode* cur = new ListNode(value);
        if (isEmpty()) {
            left->next = cur;
            right = cur;
        } else {
            right->next = cur;
            right = cur;
        }

        space--;
        return true;
    }

    bool deQueue() {
        if (isEmpty()) return false;

        ListNode* tmp = left->next;
        left->next = left->next->next;
        delete tmp;
        if (!left->next) {
            right = left;
        }

        space++;
        return true;
    }

    int Front() {
        return isEmpty() ? -1 : left->next->val;
    }

    int Rear() {
        return isEmpty() ? -1 : right->val;
    }

    bool isEmpty() {
        return left->next == nullptr;
    }

    bool isFull() {
        return space == 0;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations