Theory
Why this matters
You have just spent a unit on the stack, where the newest item leaves first. Now picture the ration shop, the railway ticket counter, or five print jobs waiting on one office printer. If any of them served the newest arrival first, there would be an argument within a minute.
Most real systems need the opposite rule, and that rule has its own data structure: the queue.
Theory
The token line at the counter
You walk into a bank, take token 47, and stand at the back of the line. The clerk calls the front of the line. Never the middle, never the back.
New people join at the rear, served people leave from the front. Two different ends, each with exactly one job. Whoever arrived first is served first: FIFO, First In, First Out.
Theory
The core idea
A queue is a linear list with two restrictions:
- Insertion is allowed only at one end, called the rear.
- Deletion is allowed only at the other end, called the front.
That single difference separates it from a stack. A stack works at one end, so it is LIFO. A queue works at two ends, so it is FIFO.
Theory
See it
A queue of size 5 holding three tokens, drawn as an array:
front rear
↓ ↓
[ 10 ][ 20 ][ 30 ][ ][ ]
0 1 2 3 4
Delete once and front steps right to index 1, so 20 becomes the front. Insert once and rear steps right to index 3. The two ends move independently, and both only ever move to the right.
Theory
The basic operations
Your syllabus names three, and the exam expects their synonyms too.
- Insert, also called enqueue: add an item at the rear.
- Delete, also called dequeue: remove the item at the front.
- Display, also called traverse: read from front to rear without removing anything.
Three helpers ride along: peek reads the front item without removing it, isEmpty asks whether there is nothing to serve, and isFull asks whether there is no room at the rear.
At a glance
Stack vs Queue, the question you will almost certainly be asked
| Aspect | Stack | Queue |
|---|---|---|
| Order | LIFO, last in first out | FIFO, first in first out |
| Ends used | One, the top | Two, front and rear |
| Insert | push, at the top | insert or enqueue, at the rear |
| Delete | pop, from the top | delete or dequeue, from the front |
| Everyday example | Undo, browser back | Ticket counter, printer |
Think first
Trace the line
Start with an empty queue. Insert 10, insert 20, insert 30. Now delete twice, then insert 40. Take five seconds: what sits at the front now, and what sits at the rear?
Show the answer
The two deletions removed 10 and then 20, the two oldest items, because a delete always takes from the front.
What remains is 30 and 40, so the front is 30 and the rear is 40. If you answered that 30 and 20 came out, you traced it as a stack: a stack removes from the same end it adds to, a queue never does.
Watch out
Overflow and underflow
Overflow is an insert into a queue with no room at the rear. Underflow is a delete from an empty queue, and it is the one students forget to guard.
Before every delete, ask whether the queue is empty. Before every insert, ask whether it is full. In code these become the isEmpty() and isFull() checks, and leaving them out is where both marks and programs fall over.
Quiz
A queue holds 10, 20, 30 from front to rear. You perform one delete, then one insert of 40. What does the queue hold, front to rear?
- 20, 30, 40
- 10, 20, 40
- 40, 20, 30
- 10, 20, 30, 40
Show the answer
20, 30, 40
The delete takes from the front, so 10 leaves. The insert adds at the rear, so 40 follows 30. Front to rear, that is 20, 30, 40. "10, 20, 40" is what you get by deleting from the rear, which is a stack's habit. "40, 20, 30" inserts at the wrong end. "10, 20, 30, 40" forgets the delete happened at all.
Formula
Where queues show up
Print jobs waiting on one printer, processes waiting for the CPU under round robin scheduling, keystrokes held in the keyboard buffer, requests waiting at a web server, and breadth first search in graphs. Carry at least three of those into the exam.
Next you build this with an array and two indexes, and you meet its flaw: once rear reaches the last slot the queue calls itself full even though deleted slots sit empty at the front. The circular queue exists to fix exactly that.
Summary
Key takeaways
- A queue is a linear list with two ends: insert at the rear, delete from the front.
- That gives FIFO order, first in first out, the opposite of a stack's LIFO.
- Basic operations: insert (enqueue), delete (dequeue) and display (traverse), plus peek, isEmpty and isFull.
- Overflow is inserting into a full queue; underflow is deleting from an empty one.
- Uses: printer spooling, CPU scheduling, keyboard buffer, web server requests, breadth first search.
- Memory hook: join at the rear, leave from the front.