Lecture 14

Stacks and Queues

Stacks

A stack is a special case of the list data structure. In a list, items may be added or removed from any point in the list; in a stack items may only be added or removed from the head of the list. The head of the list is often called the top of stack (TOS). The item on the top of the stack will always be the last item to have been put onto the stack. For this reason a stack is also called a last-in-first-out data structure (LIFO).

The term used for adding an element to the stack is push and for removing an element it is pop.

Here are push and pop functions for our example:

Stacks are very important in computer science because they allow a context to be saved. Stacks are so important that most instruction sets include simple stack operations. For example consider the following program:
void functionB()  {
....
  functionC();
....
  functionD();
....
}

void functionA() {
....
  functionB();
....
}
Here .... means that the program is filled out with more C statements. When A calls B then the variables that are active in A must be remembered, this is easily done using a stack frame. A stack frame is a number of stack items used to hold the context for a function while it calls another one. The use of stack frames allows a program to be recursive (i.e. functions may call themselves).