A ticket queue (first in, first out)
Serve customers at a ticket counter with a queue: new people join at the rear, the person at the front is served first, and front shows who is next. See why a queue is fair, and what happens when nobody is left to serve.
Core concept
A queue keeps items in a line: enqueue adds an item at the rear, dequeue takes the item at the front and front only looks at it, so the first item in is the first one out (FIFO)
Topic: Data structures
A queue is a line, like people waiting at a ticket counter. A new person always joins at the back, called the rear, and the person at the front is always served first. Adding someone at the rear is called enqueue, and serving the person at the front is called dequeue. Front only looks at who is next, without serving them. Because people leave in the same order they came, the first one in is the first one out: FIFO. It is fair: nobody can jump ahead. Computers use queues for jobs waiting their turn, such as pages waiting to be printed, messages waiting to be sent, and players waiting to join an online game.
What you will learn
- Enqueue, dequeue and look at the front of a queue, and say what each one does.
- Predict who is served next after a list of operations.
- Explain first in, first out (FIFO) and how it differs from a stack's LIFO.
- Explain why a dequeue from an empty queue is not allowed.
Before you start
- Know what a list (a row of items in order) is.
Materials
- A notebook to write your predictions
Equipment
- None
Procedure
- Serve the person at the front of the queue.
- Let a new customer join and see where they stand.
- Look at the front to see who is next, without serving them.
- Serve everyone, then try to serve once more.
- Answer the practice challenges.