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
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
{
items = new Type [stacksize];
}
template
Stack
{
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
{
if (top < stacksize)
{
items[top++] = item;
return true;
}
else
return false;
}
template
bool Stack
{
if (top > 0)
{
item = items[--top];
return true;
}
else
return false;
}
template
Stack
{
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 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
