Queue
Explanations in this animation:
- Enqueue
- Enqueueing adds a value at the rear, and the rear is the only place anything can join. 12, then 27, then 5: each one lines up behind the one before it and none of them can overtake. 12 arrived first, so 12 is at the front and will be the first to leave - the order values arrive in is the order they will go out in.
- Dequeue
- Dequeueing removes the value at the front and returns it. 12 had been waiting longest, so 12 leaves first, and everything behind it moves forward one place - 27 becomes the front and 5 moves up behind it. Nothing overtakes and nothing is skipped: the only value that can leave is the one that has been waiting longest.
- Peek
- Peek returns the value at the front and leaves the queue exactly as it was. It is the operation that separates looking from taking: after a peek all three values are still waiting and 12 is still at the front. Only the front can be read this way - there is no operation that reaches past it to 27 or 5.
- Size
- A queue does not count its values when asked how many are waiting. It keeps a running total, adding one on every enqueue and subtracting one on every dequeue, so size is read rather than walked. Three arrivals take it to three and one departure takes it back to two, and the answer costs the same whether three values are waiting or three million.
Task: Add three values to the queue
Why we need a Queue
Analogy
- Imagine you are standing in a line at a ticket counter. Riya comes first. Then Arjun. Then Sara.
- Riya gets her ticket first and leaves. Arjun is next. Sara waits behind Arjun.
- A person who joins later cannot leave before someone who was already waiting.
- That is the basic idea of a queue: first in, first out.
What is a queue?
Definition
A queue is a data structure that follows the FIFO rule: First In, First Out.
There are two ends. The front is where elements leave, and the rear is where new elements join.
So enqueue goes to the rear, and dequeue takes from the front.
The four basic operations
| Operation | What it does |
|---|---|
| enqueue(x) | Adds x at the rear |
| dequeue() | Removes the element from the front |
| peek() | Shows the front element |
| isEmpty() | Checks if the queue is empty |
Try it yourself
First in, first out
Try dequeue a few times. The front leaves and everyone behind moves up a place, which is the one thing a queue does that a stack never has to.
Queue in one picture
New elements join at the rear. Old elements leave from the front.
That is why the first element added is the first one removed.
A queue using an array
A queue can be stored inside an array.
But a normal array creates a small problem. Suppose the queue reaches the end of the array and some elements at the beginning have already been removed. Those empty spaces are still free, but the rear has reached the end.
We do not want to waste that space.
Circular queue
The solution is a circular queue. Instead of stopping at the last index, the queue goes back to the beginning.
So after index 5, the next position is index 0. This lets us reuse the empty spaces at the beginning.
Note
When the rear reaches the end, it wraps around to the beginning. That is why it is called a circular queue.
Queue vs stack
The easiest way to remember the difference:
- Stack: the last person leaves first.
- Queue: the first person leaves first.
| Queue | Stack | |
|---|---|---|
| Rule | FIFO | LIFO |
| Example | Line of people | Pile of plates |
| Add | enqueue | push |
| Remove | dequeue | pop |
| Main end | Front and rear | Top |
| Common use | Scheduling, BFS | Undo, DFS |
Ask yourself: do I need the newest item first? That is a stack. Do I need the oldest item first? That is a queue.
Where are queues used?
Queues are useful whenever things need to be handled one after another in order.
- Printer jobs: print jobs run in the order they arrive
- CPU scheduling: processes wait for their turn
- BFS: visits nodes level by level
- Customer service: customers are served in order
- Network requests: requests wait in a queue
- Message systems: messages wait to be processed
The common idea is simple: something arrives, waits, then gets processed.
Queue in code
You do not need much code to understand a queue. In Python, deque can be used:
from collections import deque queue = deque() queue.append(10) # enqueuequeue.append(20) queue.popleft() # dequeue -> 10queue[0] # peek -> 20After adding 10 and 20, the queue holds 10, 20 with 10 at the front. The first item added is the first one removed.
Common mistakes
- Adding at the front. A normal queue adds new elements at the rear.
- Removing from the rear. A normal queue removes elements from the front.
- Forgetting the empty case. You cannot dequeue when the queue is empty.
Watch out
In Python, list.pop(0) works, but removing the first element from a normal list takes O(n) time.
Use deque when you need an efficient queue.
Quick recap
A queue is a line of people. FIFO, first in first out.
- Enqueue: add at the rear
- Dequeue: remove from the front
- Peek: see the front element
- isEmpty: check whether the queue is empty
- Circular queue: reuse space by wrapping around
Key takeaway
New things join at the back. Old things leave from the front.