Time Complexity of Enqueue and Dequeue in Queues
💡 Concept Name
Queue Time Complexity – The speed of adding (enqueue) and removing (dequeue) elements from a queue depends on its underlying structure—like array, linked list, or circular array.
📘 Quick Intro
In queues, the first-in element is always the first out (FIFO). How fast this happens (enqueue/dequeue) relies on whether you use a basic array, pointers, linked lists, or a circular buffer for your queue.
🧠 Analogy / Short Story
Think of people queuing at a ticket window. If everyone must step forward one spot when the first person leaves (like shifting in an array), things slow down. But if there’s a marker for the front/rear and people just step up in place (like using pointers or a circular queue), the line moves instantly!
🔧 Technical Explanation
- 📦 Naive Array: Enqueue is O(1) (insert at end), but Dequeue is O(n) because every remaining item must shift forward.
- ⏩ Array with Pointers: By tracking front/rear, both enqueue and dequeue are O(1) (no shifting needed).
- 🔗 Linked List: Adding to rear and removing from front are both O(1) operations.
- ♻️ Circular Array: Enqueue and dequeue are both O(1), as the structure "wraps around" and reuses space.
| Implementation | Enqueue | Dequeue |
|---|---|---|
| Naive Array | O(1) | O(n) |
| Array (with front/rear pointers) | O(1) | O(1) |
| Linked List | O(1) | O(1) |
| Circular Array | O(1) | O(1) |
🎯 Purpose & Use Case
- ✅ Use circular queues for fast, space-efficient buffering (e.g., printer job queues, network packets).
- ✅ Use linked lists when queue size needs to grow or shrink dynamically.
- ✅ Use array with pointers for simple, fixed-size fast queues.
💻 Real Code Example
// Queue using LinkedList (C#)
Queue<int> queue = new Queue<int>();
queue.Enqueue(10);
queue.Enqueue(20);
Console.WriteLine(queue.Dequeue()); // Output: 10
// Queue using Naive Array
int[] arr = new int[5];
int front = 0, rear = 0;
arr[rear++] = 5;
// To dequeue, you must shift elements forward, so dequeue is O(n)
❓ Interview Q&A
Q1: What is the time complexity of enqueue operation in a queue?
A: O(1), since elements are added at the rear.
Q2: What is the time complexity of dequeue operation?
A: O(1), as elements are removed from the front.
Q3: What is the time complexity to check if a queue is empty?
A: O(1).
Q4: What is the time complexity to check if a queue is full?
A: O(1) in fixed-size queues.
Q5: What is the time complexity to access the front element?
A: O(1).
Q6: What is the time complexity of searching an element in a queue?
A: O(n), since it may require traversing all elements.
Q7: Does the time complexity differ between array and linked list implementations?
A: No, basic queue operations like enqueue and dequeue remain O(1).
Q8: What is the overhead of circular queue over linear queue in time complexity?
A: None, both have O(1) for enqueue and dequeue.
Q9: What is the time complexity of resizing a dynamic queue?
A: O(n) when resizing occurs.
Q10: What is the amortized time complexity of enqueue in a dynamic array-based queue?
A: O(1).
📝 MCQs
Q1. Time complexity of enqueue in a queue?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q2. Time complexity of dequeue in a queue?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q3. Time complexity to check if queue is empty?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q4. Time complexity to check if fixed-size queue is full?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q5. Time complexity to access front element?
- O(n)
- O(1)
- O(log n)
- O(n log n)
Q6. Time complexity to search element in queue?
- O(1)
- O(n)
- O(log n)
- O(n log n)
Q7. Does implementation affect enqueue/dequeue time complexity?
- Yes
- No
- Sometimes
- Depends
Q8. Time overhead of circular queue over linear queue?
- O(n)
- None
- O(log n)
- O(1)
Q9. Time complexity of resizing dynamic queue?
- O(1)
- O(n)
- O(log n)
- O(n log n)
Q10. Amortized time complexity of enqueue in dynamic queue?
- O(n)
- O(1)
- O(log n)
- O(n log n)
💡 Bonus Insight
Most operating systems and device drivers use circular queues for managing job buffers, because it avoids resizing and keeps operations lightning fast. It’s a trick every developer should know!
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!