Course contentsShow
← Computer Science
Lesson 384 of 2,8729. Stacks and QueuesFree lesson

Queue Size and IsEmpty Operations

Implementing auxiliary operations to check queue size and empty status efficiently.

Queue Size and IsEmpty Operations

What you'll learn: How to efficiently check if a queue is empty and retrieve its current size without disrupting the queue structure.

Why These Operations Matter

Just like you'd want to know if there's a line at the coffee shop before joining it, or how many people are ahead of you, programs often need to check if a queue is empty or get its current size before performing operations. These auxiliary operations provide essential information without changing the queue's contents.

The IsEmpty Operation

The isEmpty() operation returns true if the queue has no elements, false otherwise.

Array-based circular queue:

isEmpty() {
    return front == -1  // or check if size == 0
}

Linked list-based queue:

isEmpty() {
    return front == NULL  // or check if size == 0
}

Time complexity: O(1) — just checking a condition.

The Size Operation

The size() operation returns the number of elements currently in the queue.

Best approach: Maintain a size counter variable that:

  • Increments during enqueue
  • Decrements during dequeue
  • Returns instantly when requested
size() {
    return size
}

Time complexity: O(1) when using a counter.

Why Not Count On-Demand?

You could traverse the queue and count elements each time, but that would be O(n). By maintaining a size counter as part of the queue structure and updating it with every insertion/deletion, you get instant access to this information.

Key Takeaway: The isEmpty() and size() operations are O(1) auxiliary operations that provide crucial queue state information by checking flags or maintaining counters, without modifying the queue itself.