4.1. Stacks (Sections 3.3, 3.5 & 4.3)
We specified and implemented stacks in the first few weeks of the
course. To complete the discussion of them, I will briefly outline the
main uses of stacks in computing.
Function Calls
When a function is called all local storage for the function is
allocated on the system ``stack'', and the return address (within the
calling function) is also pushed onto the system stack. For example,
suppose there are 2 functions:
- function Q with local variables Q1 and Q2.
- function P with local variables P1, P2
and that the body of P includes a call to Q.
When function P is entered, P1 and P2 are allocated on the stack
and the body of P begins executing. When Q is called, the address of
the statement following the call is pushed onto the stack - this is
the return address. Memory for Q1 and Q2 is allocated on the stack,
essentially by pushing `undefined' onto the stack once for each of
them. The system stack does not operate perfectly like a true stack
because Q1, which is not on the top of the stack, is directly
accessible. When Q finishes Q1 and Q2 are popped off the stack. Then
the return address is popped off and execution resumes there.
Implementing Recursion
In fact, the function calling mechanism just described naturally
permits recursive function calls. If you are ever using a language
that does not support recursion - e.g. FORTRAN, most Assembly
Languages - then you can use stacks to ``fake'' recursion.
Interrupt Handling
A program, for a real-time system that can be interrupted, must attend
to interrupts immediately, before proceeding with whatever it was
doing when the interrupt occurred. A stack is the natural structure to
keep track of what the program was doing when the interrupt occurred.
(if different interrupts have different ``priorities'' a stack is not
the appropriate data structure; instead a ``priority queue'' should be
used).
Parsing
In assignment #1 you have seen the use of stacks for evaluating
expressions in POSTFIX form. Similar techniques can be used to
evaluate expressions containing brackets and operations that have
different precedence. In fact, similar techniques are used in
compilers in order to check the syntax of your program (PARSING), and
then to generate executable code.