Stack: array implementation
P.J. Drongowski
2 October 2004

Stacks

  * We've seen stacks in action with PostScript (operand stack,
    execution stack, dictionary stack, graphics state stack)
  * Stacks are used in many applications in computing
    + Language parsing
    + Expression evaluation (PostScript, stack machines)
    + Runtime execution stack (function/procedure call stack)
    + Operating system interrupt stack
    + Search / backtracking
  * Last in, first out (LIFO) access ("the last shall be first")
  * Stacks are good when you need to remember where you are so that you
    can return to the same point later
    + We exploit this stack property when displaying a scene graph

Illustrate use of stack for backtracking

  * Show picture of a simple maze
  * Label decision points (A, B, C, ...)
  * Run the maze using the stack to remember the previous sequence of
    decision points
  * Backtrack on failure, that is, when we run into a dead-end
    + Go back to previous decision point
    + Choose the next unexplored path or direction
    + If no unexplored path at last decision point, pop and go to the
      next decision point back in the stack
  * The final contents of the stack should be the path from start to finish
  * Show how maze can be represented as a tree from start to finish
    via decision points

* Stack implementations (that we will discuss in this course)

  + Stack data items in array, select TOS using integer index
  + Stack data items in array, select TOS using pointer to integer
  + Stack items in linked list of nodes, select TOS using pointer to list

Stack: array implementation

  * Start with arrays (review) and implement stack
  * What are the limitations of the array implementation?
    + Size of array
    + Type of individual array elements
  * How can limitations be removed?
    + Dynamic allocation of individual stack elements
    + structs and unions
    + Templates

Stack: Compiled code for array implementation

  * Stacks
    + Engineers need to know representation of pointers, structs and unions
      for system programming tasks
    + Show simple stack implementation using array and TOS index
    + Show array layout in memory; explain concept of "array base address"
    + Use pointer to array elements instead of TOS index; indicate how
      stack can be implemented using TOS pointer
  * Structs and unions
    + What are structs?
    + What are unions?
    + Why and when would you use a struct or a union?
    + Explain sizeof operator
    + How are structs/unions laid down in memory?

****************************************************
array_stack.h
****************************************************

#ifndef ARRAY_STACK_H
#define ARRAY_STACK_H

class Stack
{
 public:
  Stack() ;                 // Create a stack
  void clear() ;            // Reset the stack
  void push(int value) ;    // Push item on stack
  int pop() ;               // Pop and return top of stack
  int getTop() ;            // Return top item without popping
  bool isEmpty() ;          // Return true if stack is empty
  void showAll() ;          // Shows all items in stack
  void showTop() ;          // Shows top item on stack
 private:
  static const int STACK_SIZE = 128 ;
  int topOfStack ;
  int stackValues[STACK_SIZE] ;
  bool checkUnderflow(const char *method) ;
  bool checkOverflow(const char *method) ;
} ;

#endif