←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