Back to July Calendar 

Previous Entry Next Entry→

September 15, 2005

The kind of linked list I looked at yesterday is called a "linear singly linked list" because the list begins with a pointer to the first node, and each node contains a pointer to the next node “in sequence,”  proceeding only in the forward direction.

A circular, singly linked list begins with a pointer to the first node, and each node contains a pointer to the next node. The “last node” does not contain a 0 pointer; rather, the pointer in the last node points back to the first node, thus closing the “circle.”

A doubly linked list allows searching both to and fro.  This can be implemented with two start pointers—one that points to the first element of the list to allow forward search and one that points to the last element of the list to allow backward search.  Each node has both a forward pointer to the next node in the list in the forward direction and a backward pointer to the next node in the list in the backward direction.

But the data structure that most interests me now, in terms of getting this gad blossard parser thing happening, is the stack.

Stacks

A stack data structure allows objects to be added to or removed from the "top" stack.  It's a so-called LIFO (last-in, first-out) data structure. One way to implement a stack is as a constrained version of a linked list. In such an implementation, the link member in the last node of the stack is set to null (zero) to indicate the bottom (most inaccessible element) of the stack.

The obvious stack operations are push on and pop off: push a new node from input to the top of the stack or pop a node from the top of the stack to output...and may even return true if successful (or false otherwise).

Stacks are the way to accumulate data that you want record/access to in a LIFO way, such as providing the memory for, and storing the values of, automatic variables involved in a function call.  When the function returns to its caller or throws an exception, the destructor (if any) for each local object is called, the space for that function’s automatic variables is popped off the stack and those variables are freed for other memory.

Parsers and compilers rely on stacks for evaluating expressions and generating machine language code.

Slight variation and/or reusing of the list class from yesterday ought to get us to a nice Stack class, meybe even by inheritance?

Deitel describes the two variations of the example presented here this way: "We use two different forms of reusability. First, we implement the stack class through private inheritance of the list class. Then we implement an identically performing stack class through composition by including a list object as a private member of a stack class."  The whole idea of templates is to encourage further reusability.

 
Deitel's Stack class template works primarily through private inheritance of the List class template of yesterday.  Stack's member functions: push, pop, isStackEmpty and printStack are essentially the insertAtFront, removeFromFront, isEmpty and print functions of the List class template. The Stack class template doesn't need insertAtBack and removeFromBack so the Stack class template inherits from the List class through private inheritance--note the word "private" in the line declaring class Stack.  This makes all the List class template’s member functions private in the Stack class template, as you would want them to be, and even though they're listed under "public" in stack.h. When we implement the Stack’s member functions, we then have each of these call the appropriate member function of the List class.
 
The stack class template is used in main to instantiate integer stack intStack of type Stack<int>.  Integers 0 through 3 are pushed onto intStack, then popped off intStack. The program uses the Stack class template to create doubleStack of type Stack<double>. Values 1.1, 2.2, 3.3 and 4.4 are pushed onto doubleStack, then popped off doubleStack.

Another way to implement a Stack class template is by reusing the List class template through composition. Figure 17.12 is a new implementation of the Stack class template that contains a List<STACKTYPE> object called stackList. This version of the Stack class template uses class List. To test this class, use the driver program in Fig. 17.11, but include the new header file—stackcomposition.h. The output of the program is identical for both versions of class Stack

// Fig. 17.10: stack.h
// Template Stack class definition derived from class List.

#ifndef STACK_H
#define STACK_H
#include "list.h" // List class definition
   template< class STACKTYPE >
   class Stack :
private List< STACKTYPE > {
   public:
      // push calls List function insertAtFront
      void push( const STACKTYPE &data )  {
        
insertAtFront( data );
      } // end function push
      // pop calls List function removeFromFront
      bool pop( STACKTYPE &data )   {
         return
removeFromFront( data );
      } // end function pop
      // isStackEmpty calls List function isEmpty
      bool isStackEmpty() const {
         return
isEmpty();
      } // end function isStackEmpty
      // printStack calls List function print
      void printStack() const {
        
print();
      }
// end function print

   }; // end class Stack
#endif

 

// Fig. 17.11: fig17_11.cpp
// Template Stack class test program.
#include <iostream>
using
std::endl;
#include
"stack.h" // Stack class definition
int
main()  {
   
Stack< int > intStack; // create Stack of ints
    cout << "processing an integer Stack" << endl;
    // push integers onto intStack
    for ( int i = 0; i < 4; i++ ) {
       
intStack.push( i );
       
intStack.printStack();
    }
// end for
    // pop integers from intStack
    int popInteger;
    while (
!intStack.isStackEmpty() ) {
       
intStack.pop( popInteger );
        cout << popInteger << " popped from stack" << endl;
       
intStack.printStack();

    } // end while
   
Stack< double > doubleStack; // create Stack of doubles
    double value = 1.1;
    cout << "processing a double Stack" << endl;
   
// push floating-point values onto doubleStack
    for ( int j = 0; j < 4; j++ ) {
       
doubleStack.push( value );
       
doubleStack.printStack();
        value += 1.1;
    }
// end for
    // pop floating-point values from doubleStack
    double popDouble;
    while (
!doubleStack.isStackEmpty() ) {
       
doubleStack.pop( popDouble );
        cout << popDouble << " popped from stack" << endl;
        doubleStack.printStack();

    } // end while
    return 0;
} // end main

 

// Fig. 17.12: stackcomposition.h
// Template Stack class definition with composed List object.
#ifndef STACKCOMPOSITION
#define STACKCOMPOSITION
#include "list.h" // List class definition
template< class STACKTYPE >
class Stack {
  public:
    // no constructor; List constructor does initialization
    // push calls stackList object's insertAtFront function
    void push( const STACKTYPE &data )   {
       
stackList.insertAtFront( data );
    } // end function push
    // pop calls stackList object's removeFromFront function
    bool pop( STACKTYPE &data )  {
        return
stackList.removeFromFront( data );
    } // end function pop
    // isStackEmpty calls stackList object's isEmpty function
    bool isStackEmpty() const  {
        return
stackList.isEmpty();
    } // end function isStackEmpty
    // printStack calls stackList object's print function
    void printStack() const   {
       
stackList.print();
    } // end function printStack
  private:
   
List< STACKTYPE > stackList; // composed List object
}; // end class Stack
#endif

 

Here's some output:

processing an integer Stack
The list is: 0

The list is: 1 0

The list is: 2 1 0

The list is: 3 2 1 0

3 popped from stack
The list is: 2 1 0

2 popped from stack
The list is: 1 0

1 popped from stack
The list is: 0

0 popped from stack
The list is empty

processing a double Stack
The list is: 1.1

The list is: 2.2 1.1

The list is: 3.3 2.2 1.1

The list is: 4.4 3.3 2.2 1.1

4.4 popped from stack
The list is: 3.3 2.2 1.1

3.3 popped from stack
The list is: 2.2 1.1

2.2 popped from stack
The list is: 1.1

1.1 popped from stack
The list is empty