What is a Stack?
Put a plate on a pile, then another, then another. When you want a plate back, you take the one on top — the last one you put down. You cannot pull one out from the bottom without the whole pile falling over. That pile is a stack, and this chapter is that one rule, written in Python.
1The definition
A stack is a linear data structure in which items are added and removed at one end only. That end is called the top.
Linear means the items sit one after another — here, one on top of another. One end only is the important part. A list has a front, a back and a middle, and you can work at all of them. A stack has a single opening.
2Try to break the rule
Add plates, take plates, and try to pull one out from the middle.
Tap the top plate to take it off. Then try tapping one lower down.
Take all the plates off and look at the two rows. Whatever order the plates went on, they come off in the reverse order. Nobody arranges that. It is simply what happens when there is only one open end.
3LIFO — Last In, First Out
The item added most recently is the first one to be removed.
Some books say FILO — First In, Last Out. It is the same rule seen from the other end: the first item put on is the last to come off, because everything else is sitting on top of it. Either name can appear in an exam, and both describe a stack.
4Stacks you already use
The clean plate put down last is the first one picked up.
Ctrl+Z undoes your most recent change first, then the one before it, and so on backwards.
It takes you to the page you visited most recently, not the first page you opened.
The tube is closed at the bottom, so the ball dropped in last is the first to come out.
The notebook put on the pile last is the one on top, so it gets picked up first.
The bangle put on last is nearest the hand, so it has to come off first.
5Six words to know
The one end where items go on and come off. The item sitting there is the top item.
Putting a new item on top of the stack.
Taking the top item off the stack.
Looking at the top item without taking it off. Also called peep, or top.
A stack with no items on it. There is nothing to pop.
Trying to pop from an empty stack, and trying to push onto a full one.
Push and pop get the next lesson to themselves, with a stack you can drive.
6Is there a stack in Python?
No. Python has list, tuple and dict, but there is no stack type. A stack is an idea — a rule about how items go in and come out.
To use one in a program, you take an ordinary list and only ever use it by that rule. That is what the syllabus means by implementation of stack using list, and it has a group of lessons of its own, straight after push and pop.
7Recap
Items are added and removed only at the top.
Last In, First Out. FILO is the same rule said the other way round.
A, B, C in means C, B, A out.
In Python, a stack is a list used by the stack's rule.
A, B, C and D are pushed onto an empty stack in that order. Which item comes off first?
What does LIFO stand for?
Which of these does NOT behave like a stack?
A stack holds five items. Which of them can be removed right now?