Advanced

Stacks & queues

Use ordered containers that follow strict rules: last-in-first-out for stacks, first-in-first-out for queues.

What you will see

A B

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

A stack lets you add and remove at only one end, while a queue adds at one end and removes at the other. I pop a stack and drain a queue to watch the order each one enforces.

A stack has one open end, so pop always takes the top, the last thing pushed. I pop once and peek at the new top to confirm last in, first out.

stack = [1, 2, 3] print(stack.pop()) print(stack[-1])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

3 2

Stacks power the back button, undo history, and the call stack of a program. Every item comes from the same open end.

I push three plates one at a time, then pop two and watch them come off in last-in, first-out order, exactly like a real stack of plates.

plate_stack = [] plate_stack.append(1) plate_stack.append(2) plate_stack.append(3) print(plate_stack.pop(), plate_stack.pop())

Before you run it, say out loud what it will print. Then open the answer.

What it prints

3 2

push appends and pop removes from the same end. There is no way to take a plate from the middle of a real stack.

A queue removes from the front and adds at the back, first in, first out. I peek the front, dequeue it, then peek the new front to confirm the order.

line = ["A", "B", "C"] print(line[0]) line.pop(0) print(line[0])

Before you run it, say out loud what it will print. Then open the answer.

What it prints

A B

A queue needs one pointer for the open back end and one for the restricted front end. Mixing the ends up is the common mistake.

Put it in order

Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.

Data Flow

A stack and a queue each allow insertion and removal at only one or two fixed ends, enforcing an order.

1 Push or enqueue items at the open end

↓

2 Remove from the restricted end

↓

3 Stack: top last; Queue: front first

↓

4 Each removal follows the fixed rule

Line by line

Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.

stack = [1, 2, 3] sets nothing on screen

print(stack.pop()) 3

print(stack[-1]) 2

Why this works

Stack operations: push and pop

A stack has two main actions:

**push*: put an item on top.
**pop*: take the top item off.

push(1)  ->  [1]
push(2)  ->  [1][2]
pop()    ->  returns 2, leaves [1]

Stacks power things like the "back" button in a browser, undo history in editors, and function calls in a program.

Queue operations: enqueue and dequeue

A queue has two ends:

**enqueue*: add at the back.
**dequeue*: remove from the front.

enqueue(1)  ->  [1]
enqueue(2)  ->  [1][2]
dequeue()   ->  returns 1, leaves [2]

Queues model real waiting lines: print jobs, task lists, and how your computer handles requests in order.

Examples

A stack of plates

Last in, first out

Add:  [1] [2] [3]
Top -> [3]

Remove: pop 3, then 2, then 1

You can only take plates from the top. That is a **stack*: Last In, First Out (LIFO).

Why it works: every stack has one open end; everything goes and comes from there.

A line at the store

First in, first out

Join:   [A] [B] [C]
Front -> [A]

Serve:  A first, then B, then C

People leave from the front and join at the back. That is a **queue*: First In, First Out (FIFO).

Watch out: don't confuse which end is open.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Arrays & lists

Previous Lesson

Arrays & lists

Next Lesson

Linked lists

Linked lists →