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: 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.