A Closer Look at the Template Class
You can use a built-in type or a class object as the type for the Stack<Type> class template. What about a pointer? For example, can you use a pointer to a char instead of a string object in Listing 14.14? After all, such pointers are the built-in way for handling C-style strings. The answer is that you can create a stack of pointers, but it won’t work very well without major modifications in the program. The compiler can create the class, but it’s your task to see that it’s used sensibly. Let’s see why such a stack of pointers doesn’t work very well with Listing 14.14, and then let’s look at an example where a stack of pointers is useful.
Using a Stack of Pointers Incorrectly
Let’s quickly look at three simple, but flawed, attempts to adapt Listing 14.14 to use a stack of pointers. These attempts illustrate the lesson that you should keep the design of a template in mind and not just use it blindly. All three examples begin with this perfectly valid invocation of the Stack<Type> template:
Stack<char *> st; // create a stack for pointers-to-char
Version 1 then replaces
string po;
in listing 14.14 with
char * po;
The idea is to use a char pointer instead of a string object to receive the keyboard input. This approach fails immediately because merely creating a pointer doesn’t create space to hold the input strings. (The program would compile, but it would quite possibly crash after cin tried to store input in some inappropriate location.)
Version 2 replaces
string po;
with
char po[40];
This allocates space for an input string. Furthermore, po is of type char *, so it can be placed on the stack. But an array is fundamentally at odds with the assumptions made for the pop() method:
template <class Type>
bool Stack<Type>::pop(Type & item)
{
if (top > 0)
{
item = items[--top];
return true;
}
else
return false;
}
First, the reference variable item has to refer to an lvalue of some sort, not to an array name. Second, the code assumes that you can assign to item. Even if item could refer to an array, you can’t assign to an array name. So this approach fails, too.
Version 3 replaces
string po;
with
char * po = new char[40];
This allocates space for an input string. Furthermore, po is a variable and hence compatible with the code for pop(). Here, however, you come up against the most fundamental problem: There is only one po variable, and it always points to the same memory location. True, the contents of the memory change each time a new string is read, but every push operation puts exactly the same address onto the stack. So when you pop the stack, you always get the same address back, and it always refers to the last string read into memory. In particular, the stack is not storing each new string separately as it comes in, and it serves no useful purpose.
Using a Stack of Pointers Correctly
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<Type> 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.
// stcktp1.h -- modified Stack template
#ifndef STCKTP1_H_
#define STCKTP1_H_
template <class Type>
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 <class Type>
Stack<Type>::Stack(int ss) : stacksize(ss), top(0)
{
items = new Type [stacksize];
}
template <class Type>
Stack<Type>::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 <class Type>
bool Stack<Type>::push(const Type & item)
{
if (top < stacksize)
{
items[top++] = item;
return true;
}
else
return false;
}
template <class Type>
bool Stack<Type>::pop(Type & item)
{
if (top > 0)
{
item = items[--top];
return true;
}
else
return false;
}
template <class Type>
Stack<Type> & Stack<Type>::operator=(const Stack<Type> & 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<Type>. 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<Type> 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.
// stkoptr1.cpp -- testing stack of pointers
#include <iostream>
#include <cstdlib> // for rand(), srand()
#include <ctime> // for time()
#include "stcktp1.h"
const int Num = 10;
int main()
{
std::srand(std::time(0)); // randomize rand()
std::cout << "Please enter stack size: ";
int stacksize;
std::cin >> stacksize;
// create an empty stack with stacksize slots
Stack<const char *> st(stacksize);
// in basket
const char * in[Num] = {
" 1: Hank Gilgamesh", " 2: Kiki Ishtar",
" 3: Betty Rocker", " 4: Ian Flagranti",
" 5: Wolfgang Kibble", " 6: Portia Koop",
" 7: Joy Almondo", " 8: Xaverie Paprika",
" 9: Juan Moore", "10: Misha Mache"
};
// out basket
const char * out[Num];
int processed = 0;
int nextin = 0;
while (processed < Num)
{
if (st.isempty())
st.push(in[nextin++]);
else if (st.isfull())
st.pop(out[processed++]);
else if (std::rand() % 2 && nextin < Num) // 50-50 chance
st.push(in[nextin++]);
else
st.pop(out[processed++]);
}
for (int i = 0; i < Num; i++)
std::cout << out[i] << std::endl;
std::cout << "Bye
";
return 0;
}
Two sample runs of the program in Listing 14.16 follow (note that, thanks to the randomizing feature, the final file ordering can differ quite a bit from one trial to the next, even when the stack size is kept unaltered):
Please enter stack size: 5
2: Kiki Ishtar
1: Hank Gilgamesh
3: Betty Rocker
5: Wolfgang Kibble
4: Ian Flagranti
7: Joy Almondo
9: Juan Moore
8: Xaverie Paprika
6: Portia Koop
10: Misha Mache
Bye
Please enter stack size: 5
3: Betty Rocker
5: Wolfgang Kibble
6: Portia Koop
4: Ian Flagranti
8: Xaverie Paprika
9: Juan Moore
10: Misha Mache
7: Joy Almondo
2: Kiki Ishtar
1: Hank Gilgamesh
Bye
Program Notes
The strings in Listing 14.16 never move. Pushing a string onto the stack really creates a new pointer to an existing string. That is, it creates a pointer whose value is the address of an existing string. And popping a string off the stack copies that address value into the out array.
The program uses const char * as a type because the array of pointers is initialized to a set of string constants.
What effect does the stack destructor have on the strings? None. The class constructor uses new to create an array for holding pointers. The class destructor eliminates that array, not the strings to which the array elements pointed.