Stack -- Lecture notes

Stack: basic ideas

A Stack is a data structure with which you can perform the following operations (their conventional names are in bold):

• Add data, one item at a time, Push
• Access the data item on the top (other data items are hidden from view), Top
• Remove and discard the data item on the top, thus exposing the next item which now becomes the top item, Pop.

Stacks can be implemented based on arrays or linked lists. If the implementation is based on a statically allocated array, the stack has a limit on the number of elements you can push into it, which is the size of the array. Consider the following example of a stack of integers:

const int MAX_STACK_SIZE = 10;

class IntStack {
private:
  int arr[ MAX_STACK_SIZE ];
  int index;  // the index of the last added (pushed) item
public:
  IntStack() : index(-1) {}  // a stack is initially empty,
                             //   no valid entries
  void Push( int item ){
    if( index >= MAX_STACK_SIZE-1 ){
      cerr << "Warning: IntStack overflow, push failed!\n";
      return;
    }
    index++;
    arr[index]=item;
  }  
  
  int Top(){
    if( index == -1 ){
      cerr << "Warning: IntStack is empty.\n";
      return 0;
    }  
    return arr[index];  // show the last pushed element 
  }

  void Pop(){
    if( index == -1 ){
      cerr << "Warning: IntStack underflow, nothing to pop!\n";
      return;
    }     
    index--;
  }

  bool isEmpty(){ return (index >= 0); }   
};

A possible test:

int main(){
  IntStack a;

  for(int i=0; i < MAX_STACK_SIZE; i++ )
    a.Push( i*10 );
  
  for(int j=0; j < MAX_STACK_SIZE; j++ ){
    cout << a.Top() << " ";
    a.Pop();
  }
  return 0;
}

In reality, the array for an array-based stack should be allocated dynamically (its initial size can be an argument to its constrctor). The code above will read

class IntStack {
private:
  int capacity; // capacity of the stack
  int * arr;    // pointer "hook" for a dynmically allocated array 
  int index;    // the index of the last added (pushed) item
public:
  IntStack( int cap ) : 
    capacity( cap ), 
    arr( new int[capacity] ), // allocate memory dynamically at creation time  
    index(-1) {}              
  
    void Push( int item ){
    if( index >= capacity-1 ){
      cerr << "Warning: IntStack overflow, push failed!\n";
      return;
    }
    index++;
    arr[index]=item;
  }  
  // ... the rest as before
};

Exercises:
(1) Make this work in your favorite compiler.
(2) Write a StringStack that accepts strings and test it.
(3) Write a PointStack of struct Point, and test it with some graphics.

Stack via Linked List

A Linked List is a data structure that consists of "nodes", such that each node knows about the next node in the chain (singly linked list) or both the next and the previous nodes (doubly linked list). In RL, "knowing" means containing a pointer to the next node. Here is a node for a (signly linked) list of strings:

struct StringNode {
  string       data;
  StringNode * next;

  StringNode( const string & d, StringNode * n ) :
    data(d), next(n) {} 
};

Nodes are usually allocated dynamically with new, which is the main strength of linked lists: you can create new nodes on the fly and link them onto the existing chain. In terms of memory, this is better than creating dynamic arrays (a part of an array may go unused if we don't know exactly what capacity we need, while a linked list always uses no more memory than is currently needed). Another big strength of linked lists is that they don't require a contiguous chunk of memory (because each node keeps a pointer to the next one, no matter where allocated) -- dynamic allocation of an array may fail even if the total amount of free memory bytes is sufficient, but they are not in one contiguous chunk.

Traditionally, the last node in the chain has its "next" pointer set to NULL (the standard name for a zero pointer). To operate with such a list, we need to know the pointer to the first node in the chain. Hence a class StringList may look as follows. Recall that ptr->field_name is shorthand for (*ptr).field_name.

class StringList {
  StringNode * first;
public:
  StringList() : first(NULL) {} // the list is initially empty, no nodes
 
  void AddFront( const string & str ){ // add as the new first node
    StringNode * ptr = new StringNode( str, first ); // create a new node
    first = ptr;                       // the new node is now the first one
  }     
  
  void Display(){  // go through the list, print all nodes
    StringNode * ptr = first;
    while( ptr != NULL ){  // when ptr==NULL, we are at the last node
      cout << ptr->data << " ";
      ptr = ptr->next;     // the current node's "next" member points
    }                      // to the next node in the chain, where we want
  }                        // to go. If the current node is the last one, we
                           // will exit the while loop on the next iteration. 
  void DeleteFront(){  // delete the first node, if any
    if( first == NULL ) 
      return;  // no nodes, nothing to do
    // else there are nodes
    StringNode * doomed = first;
    first = first->next;  
    delete doomed;         // Since nodes are allocated with new, they
  }                        // must be deleted with delete. See below.

  // The destructor must remove all nodes manually.
  ~StringNode(){  // go down the chain of nodes, delete each one 
    StringNode * ptr = first;
    StringNode * doomed;
    while( ptr != NULL ){
      doomed = ptr;        // remember this node
      ptr = ptr->next;     // advance ptr along the chain
      delete doomed;       // _now_ delete the current node 
    }
  }
};

Exercises:
(1) Test this with your favorite complier -- write a main() that adds a few strings to the list, removes them etc.
(2) Add a member function int CountOccurances( const string & str ) that counts and returns the number of times str occurs in the list.
(3) Add a member functiion string First() that returns the first (front) element in the list.

There are many uses for lists besides the obvious one (to keep lists of names, numbers or whatever). In particular, once we have a linked list, we can easily implement a stack based on it, using AddFront() for Push() and DeleteFront() for Pop() (one more function for Top() will be needed). This is done in my labyrinth walker program.

Solving a Labyrinth: Ariadne's thread

OK, Ariadne was a daughter of King Minos of Crete. King Minos kept a pet monster called the Minotaur in a labyrinth built specifically for that purpose. At the time Athens was paying a human tribute to Crete, the luckless victims that were thrown to the monster. Theseus of Athens finally killed the beast, with the help of Ariadne, who is credited with the first algorithm for navigating a labyrinth.

The key to finding something in a labyrinth (and then getting out) is maintaining a complete linked list of already visited rooms, in the order they were visited. Thus the hero can retrace his steps when he comes to a dead end, back to the last fork, to take a previously unexplored direction from there. Ariadne gave Theseus a ball of thread, one end of which he fastened as the entrance to the labyrinth ("first" pointer), thus implementing an RL linked list of rooms, with the thread playing the role of pointers. Notice that retracing one's steps means that the rooms are processed in LIFO order. Thus the RL data structure that Ariadne designed for Theseus was essentially a stack (of rooms in the labyrinth, joined by thread).

We will use a stack of Points (a Point has two coordinates and so is well suited for keeping coordinates of a room), implemented as a linked list. class PointStack in the file theseus.h contains the implementation. It is composed of nodes,

struct PointNode {
  Point       data;
  PointNode * next;
  
  PointNode( Point d, PointNode * n ) : data(d), next(n) {}
};

Before we look at the code for PointStack, let us describe the algorithm iself:

In a room:
  1. Check if the room contains the Minotaur or is the initial room. 
             If the Minotaur:  Process it.
             If initial room:  Exit labyrinth.
  2. Mark the current room as visited, if not already marked.  
  3. Look if there are any unvisited rooms adjacent to the current
     room. (Let's say we always look and advance in some fixed order, 
     say, south, west, north, east). 
     If yes:
             Push the current room on the stack.
             Advance to the next room. 
             Goto 1.
     If no:
             Pop the top room of the stack (that is the room
             from which we just came). Move back there.
             Goto 1. 

Now for the code that implements the stack of rooms (more exactly, of room coordinates, which are kept at pairs of integers, i.e. Points).

class PointStack {
  PointNode * first;
public:
  PointStack() : first(NULL) {} // initially empty
  
  void Push( Point p ){
    PointNode * ptr = new PointNode( p, first );
    first = ptr;
  }

  void Pop(){
    if( first == NULL ) 
      return;           // nothing to pop
    // else there is at least one node
    PointNode * ptr = first;
    first = first->next;
    delete ptr;        // remove the popped node
  }

  Point Top(){  // return the top Point on the stack
    if( first == NULL ){
      cerr << "PointStack underflow\n";
      exit(-1);
    }
    // else the node on top is valid
    return first->data;
  }

  bool isEmpty(){
    return first == NULL;
  }

  ~PointStack(){  // we need to deallocate all nodes one by one
    PointNode * ptr = first;
    PointNode * doomed;
    while( ptr != NULL ){
      doomed = ptr;
      ptr = ptr->next;
      delete doomed;
    }
  }
};

The description of the labyrinth is kept in the class Labyrinth, see labyrinth.h and labyrinth.cpp. An instance of class Labyrinth reads its data from a file, in which it is represented in a human-readable manner, into a double array int lbr[ LBR_SIZE ][ LBR_SIZE ]. A labyrinth has mathods to answer questions such as bool Labyrinth::isFree( int x, int y ), is the cell at (x,y) "free" (no wall, no thread or mark from a previous visit). This solves one pesky technical problem: the algorithm need not check if the x, y are "inside" the screen, which would be necessary if we were accessing int lbr[ LBR_SIZE ][ LBR_SIZE ] directly ("array index out of bounds"). Instead, this check is made inside isFree(..).

The labyrinth also takes respnsibility for updating the drawing. Its code is hopefully self-documenting. You also have the ability to edit a loaded labyrinth via Labyrinth::Edit().