Section 10.5
10 Data Structures
10.5 Stacks
New items are added to a stack by placing then on top of the stack (called
pushing).
Items are also removed from the top of the stack.
This is an example of a Last-In-First-Out (LIFO) data structure.
A stack can be impressed by means of an array and two variables.
Stacks are used in calculations and translating from one computer language
to another.
Example - Interpreting Scopes
For the purposes of this example:
() - These are parenthesis
[] - These are brackets
{} - These are braces
Rule - Scope openers must match scope closers.
A stack is used to keep track of the scopes encountered. This works by going
left to right and:
- whenever an opening scope is encountered it is pushed onto the
stack.
- whenever a closing scope is encountered the stack is popped and a
comparison is made.
So for p + (q × [x - y] - {s - t} / q)
The comparisons were valid each time the stack was popped and the stack ended
up empty so there were no errors.
Example
Each instruction in the program has an address. When a subprogram is called, the
return address (the next line) is placed on the stack. When the sub is exited the
stack is popped and program flow continues at the next line.
