Stacking and lining up: stack and queue

Stacking like plates: the stack

Earlier we learned how to lay
data out in a row.
This time, instead of laying it out,
let us pile it up, one on top of another.
Picture a stack of plates.
A new plate always goes on top,
and you take one off the top too.
So the plate you put down last
is the first to reach your hand.

Tap to stack a plate on top, then tap take out. Always the top, the last one you put in, comes out.

Each time you took one out,
the one you just put on came first.
What goes in last comes out first,
that is the one promise of a stack.
Both where you put in and where you take out
are only the single top spot,
so the rule is very simple.
Where this simplicity is useful
we will meet again a little later.

Lining up: the queue

This time, instead of stacking,
let us line them up sideways.
Picture a line waiting for a bus.
A newcomer stands at the very back,
and when the bus comes, the front boards first.
So whoever came first
gets to go in first.
That is the exact opposite of stacking.
This lining up is called a queue.

Tap to add a person at the back of the line, then tap let out. Always the front, the one who came first, leaves.

Each time you let one out,
the one who waited longest left first.
What goes in first comes out first,
that is the promise of a queue.
They enter at the back and leave at the front,
so the order of arrival is kept just as it is.
So with no cutting in line,
a fair turn is guaranteed.
Stacking is last-first, lining up is first-first.

A stack is for undoing

When you slip while writing
and press undo,
what you just did is cancelled first.
What you did before that is cancelled next.
The actions are stacked up in order,
and from the top, the last action,
they are taken off and undone one by one.
That is exactly a stack.
The back button works the same way.

Tap to stack up actions, then tap undo. The last action you did is cancelled first, in order.

Each time you pressed undo,
the most recent action vanished first.
When you need to rewind an order backward,
nothing fits as well as a stack.
Because taking the last one in out first
is itself a rewind.
Then when you must keep the order
not backward but just as it came in,
what should you use?

A queue is for waiting lines

What happens when several people
send prints to one printer?
The document sent first prints first,
and later ones wait behind.
This is a print queue.
A bank's numbered ticket is the same.
The number drawn first is called first.
Fairly, in arrival order.
That is exactly what a queue does.

Tap to add a document to the print queue, then tap print. The one sent first is handled first, in order.

Each time you pressed print,
the document sent earliest came out.
When the order must be kept as is,
nothing beats a queue.
Because taking the first one in out first
is itself fairness.
With the same data, one rule for taking out
changes the use this much.
Now let us line the two up and sum them up.

Let's wrap up

Gathered on one line, it is this.
A stack is stacking plates; the last in comes out first.
A queue is lining up; the first in comes out first.
Undo and the back button are a stack,
waiting lines and numbered tickets are a queue.
A single rule for putting in and taking out
decides the use.
Stacking is last-first, lining up is first-first,
that one line is all you need to keep.

Tap the key points in order to review. (stack = stacking -> queue = lining up -> stack for undo -> queue for waiting)

Now you know two ways
to stack data and to line it up.
Just by choosing where to put in and take out,
it became a wholly different tool.
Next we will meet another way
that is neither a line nor a pile.
A shape where data splits like branches
and spreads from top to bottom,
let us carry that story on in the next lesson.