TwiddleLab / Code / Data Structures You Can See

Queues: First In, First Out

Lesson 2 of 10 · 7 min · Free, no account needed

What you will learn

• A queue is a line: items join at the back and leave from the front.
• First in, first out (FIFO): the order out is the order in.
• In Python: q.append(x) joins the back, q.pop(0) takes the front.
• Stack or queue is the same list served from a different end. That one choice decides who waits.

Start the lesson

How the lesson goes

1. A million fans click Buy at the same second. Who gets the ticket first?

   Here is a small ticket line. Press Next and watch who gets served.

2. Make it fair. Move the ticket window.

   Same fans, same order of events. Only the window moves.

   With the window at the back, the newest fan is always next to it. At the front, the fan who has been there longest is next.

3. Stack or queue?

   Each box takes items in and gives some out. Read the order out and name the box.

4. A fair line is a queue.

   A queue is a line: items join at the back and leave from the front.

   First in, first out: FIFO. A stack is LIFO. Same pile of items, served from the other end.

   In Python: q.append(x) joins the back. q.pop(0) takes the item at index 0, the front.

5. Stack or queue? Sort these by how they work.

   Ask: does the newest go first, or the oldest?

6. A queue in Python.

   Step through. Before each pop(0), tap the person who leaves.

7. Take turns: Ana, Ben, Cy, Ana, Ben.

   Build the turn loop. The player whose turn ends goes to the back of the line.

8. Chatbots queue your messages too.

   A busy chatbot server answers one request every 2 seconds, oldest first. You are number 7 in its queue.

   A queue serves in arrival order. Six requests are ahead of you, so yours is the 7th answer: 7 x 2 = 14 s.

9. Your turn loop, with four players and one change.

   One version uses your pop(0), the other pop(). Tap the fair one, then Check.

   append puts the player at the back. pop() takes from the back again, so the same player comes straight out. pop(0) takes from the front, so the player waits behind everyone else.

Previous lesson: Stacks: Last In, First Out · Next lesson: Linked Lists: Chains of Arrows · Part of the course: Data Structures You Can See

Lessons are interactive and need JavaScript. Turn it on to play them.