C++ Primer Plus

One way to use a stack of pointers is to have the calling program provide an array of pointers, with each pointer pointing to a different string. Putting these pointers on a stack then makes sense because each pointer will refer to a different string. Note that it is the responsibility of the calling program, not the stack, to create the separate pointers. The stack’s job is to manage the pointers, not create them.

For example, suppose you have to simulate the following situation. Someone has delivered a cart of folders to Plodson. If Plodson’s in-basket is empty, he removes the top folder from the cart and places it in his in-basket. If his in-basket is full, Plodson removes the top file from the basket, processes it, and places it in his out-basket. If the in-basket is neither empty nor full, Plodson may process the top file in the in-basket, or he may take the next file from the cart and put it into his in-basket. In what he secretly regards as a bit of madcap self-expression, he flips a coin to decide which of these actions to take. You’d like to investigate the effects of his method on the original file order.

You can model this with an array of pointers to strings representing the files on the cart. Each string will contain the name of the person described by the file. You can use a stack to represent the in-basket, and you can use a second array of pointers to represent the out-basket. Adding a file to the in-basket is represented by pushing a pointer from the input array onto the stack, and processing a file is represented by popping an item from the stack and adding it to the out-basket.

Given the importance of examining all aspects of this problem, it would be useful to be able to try different stack sizes. Listing 14.15 redefines the Stack class slightly so that the Stack constructor accepts an optional size argument. This involves using a dynamic array internally, so the class now needs a destructor, a copy constructor, and an assignment operator. Also the definition shortens the code by making several of the methods inline.

Listing 14.15. stcktp1.h

// stcktp1.h -- modified Stack template

#ifndef STCKTP1_H_

#define STCKTP1_H_

template

class Stack

{

private:

    enum {SIZE = 10};    // default size

    int stacksize;

    Type * items;       // holds stack items

    int top;            // index for top stack item

public:

    explicit Stack(int ss = SIZE);

    Stack(const Stack & st);

    ~Stack() { delete [] items; }

    bool isempty() { return top == 0; }

    bool isfull() { return top == stacksize; }

    bool push(const Type & item);   // add item to stack

    bool pop(Type & item);          // pop top into item

    Stack & operator=(const Stack & st);

};

template

Stack::Stack(int ss) : stacksize(ss), top(0)

{

    items = new Type [stacksize];

}

template

Stack::Stack(const Stack & st)

{

    stacksize = st.stacksize;

    top = st.top;

    items = new Type [stacksize];

    for (int i = 0; i < top; i++)

        items[i] = st.items[i];

}

template

bool Stack::push(const Type & item)

{

    if (top < stacksize)

    {

        items[top++] = item;

        return true;

    }

    else

        return false;

}

template

bool Stack::pop(Type & item)

{

    if (top > 0)

    {

        item = items[--top];

        return true;

    }

    else

        return false;

}

template

Stack & Stack::operator=(const Stack & st)

{

    if (this == &st)

        return *this;

    delete [] items;

    stacksize = st.stacksize;

    top = st.top;

    items = new Type [stacksize];

    for (int i = 0; i < top; i++)

        items[i] = st.items[i];

    return *this;

}

#endif

Notice that the prototype declares the return type for the assignment operator function to be a reference to Stack, and the actual template function definition identifies the type as Stack. The former is an abbreviation for the latter, but it can be used only within the class scope. That is, you can use Stack inside the template declaration and inside the template function definitions, but outside the class, as when identifying return types and when using the scope-resolution operator, you need to use the full Stack form.

The program in Listing 14.16 uses the new stack template to implement the Plodson simulation. It uses rand(), srand(), and time() in the same way previous simulations have used them to generate random numbers. In this case, randomly generating a 0 or a 1 simulates the coin toss.

Listing 14.16. stkoptr1.cpp