CP164 Study Guide - Final Guide: Backtracking, Parsing
Notes - The Stack ADT
A Simple Stack
The Stack ADT represents a Last-In-First-Out (LIFO) data structure. Data items are pushed
on top of the stack and popped from the top of the stack meaning that the last item added
to the stack is always the first item removed from the stack. (Think of a stack of dishes or of
cafeteria trays.)
Stack Methods
The basic stack methods are:
initialize: create an empty stack
push: push a new value onto the top of the stack
pop: removes and returns the value on the top of the stack, if one exists
peek: return a copy of the value at the top of the stack without removing it, if one exists
is empty: returns True if the stack is empty, False otherwise
Any implementation of a stack must define these methods.
Uses for a Stack
Other than simple real-life uses such as stacking dishes or the output from a printer or
copier, stacks have a number of uses in algorithms.
Memory Management
Certain types of computer memory are stack-oriented: memory is treated as stack of
memory locations that are allocated to variables as functions as requested.
Arguments to a function are pushed onto the memory stack and popped off it after
the function has completed. The function may return values on the stack. Such
stacks are a key part of the implementation of a recursive algorithm - you can think
of each call to a recursive function as pushing the function information to the top of
the stack while the recursive calls are being made, and popping the results of the
calls off the top of memory as the recursion finishes.
Document Summary
The stack adt represents a last-in-first-out (lifo) data structure. The basic stack methods are: initialize: create an empty stack. Push: push a new value onto the top of the stack. Pop: removes and returns the value on the top of the stack, if one exists. Peek: return a copy of the value at the top of the stack without removing it, if one exists is empty: returns true if the stack is empty, false otherwise. Any implementation of a stack must define these methods. Other than simple real-life uses such as stacking dishes or the output from a printer or copier, stacks have a number of uses in algorithms. Certain types of computer memory are stack-oriented: memory is treated as stack of memory locations that are allocated to variables as functions as requested. Arguments to a function are pushed onto the memory stack and popped off it after the function has completed. The function may return values on the stack.
