The Queue Data Structure
Overview
- A queue is a collection data type that is best visualized as a “line” of elements.
- It can be described as FIFO (First in, First out).
- Differs from stacks in how objects are removed (in queues, the front entry is removed).
Queue Operations
There are four basic operations1 that can be done on a queue:
- enqueue(): adds an element to the left of the queue if the queue is not full.
- dequeue(): remove the rightmost element of the queue if the queue is not empty.
- front(): return the front item from the queue.
- rear(): return the last item from the queue.
If the queue is finite, the following operation is necessary:
- size(): returns the size of the queue; useful for checking if it is full.
When to Use Queues
- When FIFO processing order matters.
- When data doesn’t need to be processed immediately after being added to the queue1.
Time Complexity
| Operation | Time Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(1) |
| Size | O(n) |
Practice Problems
Check out HackerEarth’s Basics of Queues page for queue-related practice problems.