The C++Course provides a general introduction to programming in C++. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

The Pstack Class

Although we have the pclasses that provide for a class called pstack that implements the Stack ADT. You should make some effort to keep these two things---the ADT and the pclass implementation---straight.

Then the syntax for constructing a new pstack is

    pstack stack;

Initially the stack is empty, as we can confirm with the empty method, which returns a boolean:

    cout << stack.empty ();

A stack is a generic data structure, which means that we can add any type of item to it. In the pclass implementation, though, we can only add object types. For our first example, we'll use Node objects, as defined in the previous chapter. Let's start by creating and printing a short list.

    LinkedList list;
    list.addFirst (3);
    list.addFirst (2);
    list.addFirst (1);
    list.print ();

The output is (1, 2, 3). To put a Node object onto the stack, use the push method:

    pstack.push (node);

The following loop traverses the list and pushes all the nodes onto the stack:

    for (Node *node = list.head; node != null; node = node->next) {
        pstack.push (node);

We can remove an element from the stack with the overloaded pop method.

    pstack.pop ();
    //  or
    pstack.pop (itemType &item);

The return type from pop is void. That's because the stack implementation doesn't need to keep the item around because it is to be removed from the stack.

The following loop is a common idiom for popping all the elements from a stack, stopping when it is empty:

    while (!pstack.empty ()) {
        cout << << ' ';

The output is 3 2 1. In other words, we just used a stack to print the elements of a list backwards! Granted, it's not the standard format for printing a list, but using a stack it was remarkably easy to do.

You should compare this code to the implementations of printBackward in the previous chapter. There is a natural parallel between the recursive version of printBackward and the stack algorithm here. The difference is that printBackward uses the run-time stack to keep track of the nodes while it traverses the list, and then prints them on the way back from the recursion. The stack algorithm does the same thing, just using a pstack object instead of the run-time stack.

Last Update: 2005-12-05