Computer science
Stacks & queues
Two simple ways to order data: last in goes out first, or first in gets served first.
What you need first
When you stand in line at the checkout, you know exactly who is next: the person who has waited longest. When you stack plates, you always take the top one, the one that arrived last. Programs use exactly these two orders all the time, and they have names: queue and stack.
The stack: last in, first out
A stack works like a pile of plates: you put new elements on top, which is called push. You can only remove the top element, which is called pop. Whatever came in last comes out first. The back button in your browser works exactly like this: when you click onward, the page you leave is pushed onto a stack, and back pops the top one, the page you visited before.
Counting starts at 0.
The queue: first in, first out
A queue is the exact opposite: new elements join at the back, and elements are removed from the front. First come, first served, just like at the supermarket checkout. For you that means: if you are at position 5, positions 1 to 4 go before you, so four people, and only after them is it your turn. A printer uses a queue: if three people send something to print one after another, it prints the jobs in exactly that order, nobody cuts in line.
Where programs need this
Stacks appear wherever you want to undo steps: undo in a text editor, the back button, and even function calls in land on a stack. Queues appear wherever fairness matters: print jobs, downloads, messages that a server works through in order. The question is always the same: should the newest item go first, or the oldest?
Exercises
0 of 6 solvedTime to try it yourself. You can't break anything, every attempt counts.
You push A, B and C onto a stack one after another. Which element do you get with the first pop?
Three print jobs arrive one after another: first from Emma, then from Ben, then from Lea. Whose job does the printer print first?
You push 5 elements onto a stack and then remove 2 with pop. How many elements are still on the stack?
Match each term to its meaning.
There are 6 people in a queue. 2 get served and leave. How many are still waiting?
A printer works through the jobs like a …: first come, first served.
Where this leads