Space Complexity of Queue Operations

Space complexity refers to the amount of extra memory used by an operation relative to the input size. In queues, most operations are performed in-place, which means they operate directly within the existing structure without requiring additional memory. Below, we explore the space complexity of key queue operations: Enqueue, Dequeue, Peek, isEmpty, and Size.

Summary Table

Operation	Space Complexity	Why?
Enqueue	O(1)	Element is added to the rear using constant space
Dequeue	O(1)	Element is removed from the front without new memory
Peek	O(1)	Accesses the front element directly
isEmpty	O(1)	Checks size or front/rear pointer
Size	O(1)	Returns a maintained count variable

1. Enqueue

The enqueue operation inserts a new element at the rear of the queue.

• Space Complexity: O(1)
• Why: The new element is stored directly in the next available slot. No additional structures or temporary space are required.

2. Dequeue

The dequeue operation removes the element from the front of the queue.

• Space Complexity: O(1)
• Why: The operation only involves shifting a pointer or index. The removed value is simply overwritten or ignored.

3. Peek

The peek operation retrieves the front element without removing it.

• Space Complexity: O(1)
• Why: Directly accesses the front position in the queue without creating new memory.

4. isEmpty

The isEmpty operation checks if the queue is empty.

• Space Complexity: O(1)
• Why: This operation typically checks a size counter or compares front and rear pointers, both of which are constant-space variables.

5. Size

The size operation returns the number of elements in the queue.

• Space Complexity: O(1)
• Why: Most implementations maintain a counter that tracks the current number of elements. Returning this count uses constant space.