A stack is an algorithm for storing data. Data can be put in the stack using a push operation. The pop operation removes the data. Data is stored in last-in-first-out (LIFO) order.

You can think of a stack as a stack of papers. When you perform a push operation, you put a new paper on top of the stack. You can push as many times as you want; each time the new data goes on top of the stack. You get data out of a stack using the pop operation, which takes the top paper off the stack and gives it to the caller.

Suppose you start with an empty stack and put three elements on it, 4, 5, and 8, using three push operations. The first pop would return the top element, 8. The elements 4 and 5 remain in the stack. Popping again gives you 5. You then push another value, 9, on the stack. Popping twice gives you the numbers 9 and 4, in that order. This is illustrated by Table 13-1.

const int STACK_SIZE = 100;     // Maximum size of a stack 

// The stack itself 
struct stack { 
   int count;                   // Number of items in the stack 
   int data[STACK_SIZE];        // The items themselves 
};

inline void stack_push(struct stack& the_stack, const int item)
{
    assert((the_stack.count >= 0) && 
           (the_stack.count <
                  sizeof(the_stack.data)/sizeof(the_stack.data[0])));

    the_stack.data[the_stack.count] = item;
    ++the_stack.count;
}

inline int stack_pop(struct stack& the_stack) 
{ 
    // Stack goes down by one 
    --the_stack.count;

    assert((the_stack.count >= 0) && 
           (the_stack.count <
                  sizeof(the_stack.data)/sizeof(the_stack.data[0])));
    // Then we return the top value 
    return (the_stack.data[the_stack.count]); 
}

inline void stack_init(struct stack& the_stack) 
{ 
    the_stack.count = 0;        // Zero the stack 
}

    stack a_stack;    // Declare the stack

    stack_init(a_stack);     // Initialize the stack
    // Stack is ready for use

/********************************************************
 * Stack                                                *
 *      A set of routines to implement a simple integer *
 *      stack.                                          *
 *                                                      *
 * Procedures                                           *
 *      stack_init -- initalize the stack.              *
 *      stack_push -- put an item on the stack.         *
 *      stack_pop -- remove an item from the stack.     *
 ********************************************************/
#include <cassert>
#include <cstdlib>
#include <iostream>

const int STACK_SIZE = 100;     // Maximum size of a stack

// The stack itself
struct stack {
   int count;                   // Number of items in the stack
   int data[STACK_SIZE];        // The items themselves
};

/********************************************************
 * stack_init -- initialize the stack.                  *
 *                                                      *
 * Parameters                                           *
 *      the_stack -- stack to initalize                 *
 ********************************************************/
inline void stack_init(struct stack& the_stack)
{
    the_stack.count = 0;        // Zero the stack
}
/********************************************************
 * stack_push -- push an item on the stack.             *
 *                                                      *
 * Warning: We do not check for overflow.               *
 *                                                      *
 * Parameters                                           *
 *      the_stack -- stack to use for storing the item  *
 *      item -- item to put in the stack                *
 ********************************************************/
inline void stack_push(struct stack& the_stack,
                       const int item)
{
    assert((the_stack.count >= 0) &&
           (the_stack.count < 
             sizeof(the_stack.data)/sizeof(the_stack.data[0])));

    the_stack.data[the_stack.count] = item;
    ++the_stack.count;
}
/********************************************************
 * stack_pop -- get an item off the stack.              *
 *                                                      *
 * Warning: We do not check for stack underflow.        *
 *                                                      *
 * Parameters                                           *
 *      the_stack -- stack to get the item from         *
 *                                                      *
 * Returns                                              *
 *      The top item from the stack.                    *
 ********************************************************/
inline int stack_pop(struct stack& the_stack)
{
    // Stack goes down by one
    --the_stack.count;

    assert((the_stack.count >= 0) &&
           (the_stack.count < 
             sizeof(the_stack.data)/sizeof(the_stack.data[0])));

    // Then we return the top value
    return (the_stack.data[the_stack.count]);
}

// A short routine to test the stack
int main(  )
{
    struct stack a_stack;       // Stack we want to use

    stack_init(a_stack);

    // Push three value on the stack
    stack_push(a_stack, 1);
    stack_push(a_stack, 2);
    stack_push(a_stack, 3);

    // Pop the item from the stack
    std::cout << "Expect a 3 ->" << stack_pop(a_stack) << '
';
    std::cout << "Expect a 2 ->" << stack_pop(a_stack) << '
';
    std::cout << "Expect a 1 ->" << stack_pop(a_stack) << '
';

    return (0);
}

The structure version of the stack works but has a few drawbacks. The first is that the data and the functions are defined separately, forcing you to pass a struct stack variable into each procedure.

There is also the problem of data protection. The fields data and count are accessible to anyone. The design states that only the stack functions should have access to these fields, but there is nothing to prevent rogue code from modifying them.

A C++ struct is a mixed collection of data. The C++classnot only holds data like a structure, but also adds a set of functions for manipulating the data and access protection.

Turning the struct stack into a class you get:

class stack {
    private:
        int count;              // Number of items in the stack
        int data[STACK_SIZE];   // The items themselves
    public:
        // Initialize the stack
        void init(  );

        // Push an item on the stack
        void push(const int item);

        // Pop an item from the stack
        int pop(  );
};

Let’s go into this class declaration in more detail. The beginning looks much like a structure definition, except that you’re using the word class instead of struct:

class stack {
    private:
        int count;              // Number of items in the stack
        int data[STACK_SIZE];   // The items themselves

This declares two fields: count and data. In a class these items are not called fields; they are called member variables. The keyword private indicates the access privileges associated with these two member variables.

There are three levels of access privileges: public, private, and protected. Class members, both data and functions, marked private cannot be used outside the class. They can be accessed only by functions within the class. The opposite of private is public, which indicates members that anyone can access.

Finally, protected is similar to private except that it allows access by derived classes. (We discuss derived classes in Chapter 21.)

You’ve finished defining the data for this class. Now you need to define the functions that manipulate the data:

    public:
        // Initialize the stack
        void init(  );

        // Push an item on the stack
        void push(const int item);

        // Pop an item from the stack
        int pop(  );
};

This section starts with the keyword public. This tells C++ that you want all these member functions to be available to the outside. In this case, you just define the function prototypes. The code for the functions will be defined later.

Next comes the body of the init function. Since this function belongs to the stack class, you prefix the name of the procedure with stack::. (We discuss the scope operator :: in more detail in Chapter 14.)

The definition of the init function looks like this:

inline void stack::init(  )
{
    count = 0;  // Zero the stack
}

This procedure zeroes the stack’s count. In the structure version of the stack_init function, you must pass the stack in as a parameter. Since this function is part of the stack class, that’s unnecessary. This also means that you can access the member variables directly. In other words, instead of having to say the_stack.count, you just say count.

The functions push and pop are implemented in a similar manner:

inline void stack::push(const int item)
{
    data[count] = item;
    ++count;
}

inline int stack::pop(  )
{
    // Stack goes down by one
    --count;

    // Then we return the top value
    return (data[count]);
}

The stack class is now complete. All you have to do is use it.

Using a class is much like using a structure. Declaring a class variable is the same, except you use the word class instead of struct:

    class stack a_stack;        // Stack we want to use

The word class is not needed and is frequently omitted:

    stack a_stack;        // Stack we want to use

You access the members of a structure using a dot; for example:

    structure.field = 5;

Accessing the members of a class is similar, except that the members of a class can be both data and functions. Also, you can access only the members that are public.

To call the init member function of the stack class, all you need to do is this:

    a_stack.init(  );

The push and pop member functions can be accessed in a similar manner:

    a_stack.push(1);
    result = a_stack.pop(  );

Example 13-2 contains a class version of the stack.

/********************************************************
 * Stack                                                *
 *      A file implementing a simple stack class        *
 ********************************************************/
#include <cstdlib>
#include <iostream>
#include <cassert>

const int STACK_SIZE = 100;     // Maximum size of a stack

/********************************************************
 * Stack class                                          *
 *                                                      *
 * Member functions                                     *
 *      init -- initialize the stack.                   *
 *      push -- put an item on the stack.               *
 *      pop -- remove an item from the stack.           *
 ********************************************************/
// The stack itself
class stack {
    private:
        int count;              // Number of items in the stack
        int data[STACK_SIZE];   // The items themselves
    public:
        // Initialize the stack
        void init(  );

        // Push an item on the stack
        void push(const int item);

        // Pop an item from the stack
        int pop(  );
};

/********************************************************
 * stack::init -- initialize the stack.                 *
 ********************************************************/
inline void stack::init(  )
{
    count = 0;  // Zero the stack
}
/********************************************************
 * stack::push -- push an item on the stack.            *
 *                                                      *
 * Warning: We do not check for overflow.               *
 *                                                      *
 * Parameters                                           *
 *      item -- item to put in the stack                *
 ********************************************************/
inline void stack::push(const int item)
{
    assert((count >= 0) &&
           (count < sizeof(data)/sizeof(data[0])));
    data[count] = item;
    ++count;
}
/********************************************************
 * stack::pop -- get an item off the stack.             *
 *                                                      *
 * Warning: We do not check for stack underflow.        *
 *                                                      *
 * Returns                                              *
 *      The top item from the stack.                    *
 ********************************************************/
inline int stack::pop(  )
{
    // Stack goes down by one
    --count;

    assert((count >= 0) &&
           (count < sizeof(data)/sizeof(data[0])));

    // Then we return the top value
    return (data[count]);
}

// A short routine to test the stack
int main(  )
{
    stack a_stack;      // Stack we want to use

    a_stack.init(  );

    // Push three value on the stack
    a_stack.push(1);
    a_stack.push(2);
    a_stack.push(3);

    // Pop the item from the stack
    std::cout << "Expect a 3 ->" << a_stack.pop(  ) << '
';
    std::cout << "Expect a 2 ->" << a_stack.pop(  ) << '
';
    std::cout << "Expect a 1 ->" << a_stack.pop(  ) << '
';

    return (0);
}

This stack class has one minor inconvenience. The programmer must call the init member function before using the stack. However, programmers are terribly forgetful, and sooner or later someone is going to forget to initialize the stack. Wouldn’t it be nice if C++ had an automatic way of initializing the stack?

It does. Actually C++ will automatically call a number of member functions. The first you are concerned about is called when stack is created. In C++ language this is referred to as “creating an instance of the class stack.”

The function C++ calls to create a instance of the class is called the constructor and has the same name as the class. For example, the constructor for the stack class is named stack (also known as stack::stack outside the class body).

A variable, or instance of a class, is created when it is defined. (It can also be created by the new operator, as described in Chapter 20.)

You want to have this stack initialized automatically, so you remove the init function and replace it with the constructor, stack::stack:

class stack {
        // ...
    public:
        // Initialize the stack
        stack(  );
        // ...
};

inline stack::stack(  )
{
    count = 0;  // Zero the stack
}

You may have noticed that the return type void has been omitted in the constructor declaration. Constructors can never return a value, so the void is not needed. In fact, the compiler will complain if it’s present.

Since the constructor is called automatically, the program is now simpler. Instead of writing:

int main(  )
{
    stack a_stack;      // Stack we want to use

    a_stack.init(  );

you can just write:

int main(  )
{
    stack a_stack;      // Stack we want to use

    // Use the stack

Also, since you no longer have to count on the programmer putting in the init call, the program is more reliable.

inline stack::~stack(  ) {
    if (count != 0)
        std::cerr << "Error: Destroying a nonempty stack
";
}

class person {
    public:
        std::string name;      // Name of the person
        std::string phone;     // Person's phone number

    public:
        person(const std::string i_name, const std::string i_phone);
    // ... rest of class
};

person::person(const std::string i_name, const std::string i_phone)
{
    name = i_name;
    phone = i_phone;
}

int main(  )
{
    person sam("Sam Jones", "555-1234");

class person {
    // ... rest of the class
    public:
        person(const std::string i_name);
};

person::person(const std::string i_name)
{
    name = i_name;
    phone = "No Phone";
}

    person unnamed_source;     // Illegal

Copy Constructor

The copy constructor is a special constructor that is used to make an exact copy of a class. For example, a copy constructor for the stack class would look like this:

stack::stack(const stack& old_stack)
{
    int i;     // Index used to copy the data

    for (i = 0; i < old_stack.count; ++i) {
        data[i] = old_stack.data[i];
    }
    count = old_stack.count;
}

Let’s examine this function in more detail. The declaration:

stack::stack(const stack& old_stack)

identifies this as a copy constructor. The single parameter (const stack& old_stack) identifies this particular constructor as the copy constructor. This function is expected to turn the current instance of the class into an exact copy of the parameter.

The code:

for (i = 0; i < old_stack.count; ++i) {
    data[i] = old_stack.data[i];
}
count = old_stack.count;

takes all the data from the old stack and puts it into the new stack.

The copy constructor can be invoked explicitly, as illustrated in the following example:

stack a_stack;      // A simple stack

a_stack.push(1);    // Put a couple of elements on the stack
a_stack.push(2);

stack b_stack(a_stack);  // Create a copy of the stack

On the face of it, the copy constructor doesn’t seem that important. But if you remember, back in Chapter 9, I discussed the various ways C++ can pass parameters to a function. One of these was call by value. That’s where a copy of the parameter is made and passed to the function.

When a stack or any other class is passed as a call-by-value parameter, a copy is made of that class using the copy constructor.

In the following code, we’ve added some commentary to show you the functions that C++ will automatically call behind your back:

As you can see, C++ does a lot of work behind the scenes. It starts when a_stack is declared. C++ calls the default constructor to create a_stack.

The variable a_stack is used, and then passed to the function use_stack. Since a_stack is passed by value, a copy must be made of the stack using the copy constructor local_stack.stack(a_stack).

The function then adds a few items to local_stack. Note that this is a copy of a_stack, so anything you do to local_stack does not affect a_stack. At the end of the function, local_stack contains four items—1, 2, 9, 10—and a_stack contains two items: 1 and 2.

Finally after the function call, the program prints out the top element of a_stack, which is 2.

Every class has a constructor and a destructor. If the programmer does not write these member functions, C++ will automatically generate them. Also, there are several member functions, such as the copy constructor, that can be called automatically.

class int_array {
    public:
        int_array(unsigned int size);

    int_array example(10);

    int_array example = 10;

class int_array {
    public:
        explicit int_array(unsigned int size);

    int_array example(10);    // Works with explicit

    int_array example = 10; // Illegal because of "explicit"

So far you have used only function prototypes in the classes you’ve created. It is possible to define the body of the function inside the class itself. Consider the following code:

class stack {
    public:
        // .... rest of class

        // Push an item on the stack
        void push(const int item);
};
inline void stack::push(const int item)
{
    data[count] = item;
    ++count;
}

This code can instead be written as:

class stack {
    public:
        // .... rest of class

        // Push an item on the stack
        void push(const int item) {
            data[count] = item;
            ++count;
        }
};

The inline directive is not required in the second case since all functions declared inside a class are automatically declared inline.

Programming style for classes looks pretty much like the style for structures and functions. Every member variable should be followed by a comment explaining it, and every member function should be commented like a function.

However, you comment the prototypes for member functions differently from normal function prototypes. For normal functions you put a full function comment block in front for the prototype. If you did this for the member functions of a class, the comments would obscure the structure of the class. This is one of the few cases when too many comments can cause trouble. So you put a one-line comment in front of each member function prototype and full comments in front of the function itself.

But what about inline-member functions, where the entire body of the function is declared inside the class? How do you comment that? If you put in full comments, you obscure the structure of the class. If you put in one-liners, you omit a lot of useful information. Proper commenting is a balancing act. You need to put in what’s useful and leave out what’s not.

The solution is to keep the size of the inline-member function small. There are two reasons for this: first, all inline functions should be small, and second, large functions declared inside a class make the class excessively complex. A good rule of thumb is that if the function requires more than about five lines of code, put a prototype in the class and put the body of the function elsewhere.

The structure of very small member functions should be obvious and thus not require a full-blown comment block. If the function is not obvious and requires extensive comments, you can always put in a prototype and comment the body of the function later in the program.

C++ does not require an access specifier (public, private, or protected) before the first member variable. The following is perfectly legal:

class example {
        int data;
        // ...
};

But what is the access protection of data? Is it public, private, or protected? If you put in an explicit specification, you don’t have to worry about questions like this. (For those of you who are curious, the access specification defaults to private.)

Finally, C++ will automatically generate some member functions, such as the default constructor, the copy constructor, and the assignment operator. Suppose you have a class that does not specify a copy constructor, such as this:

// Comments describing the class
// Note: The style of this class leaves something to be desired
class queue {
    private:
        int data[100];    // Data stored in the queue
        int first;        // First element in the queue
        int last;         // Last element in the queue
    public:
        queue(  );          // Initialize the queue
        void put(int item);// Put an item in the queue
        int get(  );    // Get an item from the queue
};

Did the programmer who created this class forget the copy constructor? Will the copy constructor automatically generated by C++ work, or did the programmer design this class knowing that the copy constructor would never be called? These important questions are not answered by the class as written.

All classes have a default constructor, copy constructor, assignment operator, and destructor. If you do not create one of these special member functions, C++ will generate one automatically for you. If you expect to use any of these automatic functions, you should put a comment in the class to indicate the default is being used:

// Comments describing the class
class queue {
    private:
        int data[100];    // Data stored in the queue
        int first;        // First element in the queue
        int last;         // Last element in the queue
    public:
        queue(  );          // Initialize the queue
        // queue(const queue& old_queue) 
        //     Use automatically generated copy constructor

        // queue operator = (const queue& old_queue)
        //     Use automatically generated assignment operator

        // ~queue(  )
        //    Use automatically generated destructor

        void put(int item);// Put an item in the queue
        int get(  );    // Get an item from the queue
};

Now it is obvious what member functions the programmer wanted to let C++ generate automatically, and being obvious is very important in any programming project.

The copy constructor automatically generated by C++ is rather simple and limited. It doesn’t work in all cases, as you’ll see later when you start to construct more complex classes. But what happens when the automatic copy constructor won’t work as you desire, and you don’t want to go to the trouble to create your own? After all, you may decide that a class will never be copied (or that if it is, it’s an error).

One solution is to create a dummy copy constructor that prints an error message and aborts the program:

class no_copy {
        // Body of the class
    public:
        // Copy constructor
        no_copy(const no_copy& old_class) {
            std::cerr <<
             "Error: Copy constructor for 'no_copy' called. Exiting
";
            exit(8);
        }
};

This works, sort of. The problem is that errors are detected at runtime instead of compile time. You want to catch errors as soon as possible, so this solution is at best a hack.

However, you can prevent the compiler from automatically calling the copy constructor. The trick is to declare it private. That’s your way of saying to the world, “Yes, there is a copy constructor, but no one can ever use it”:

class no_copy {
        // Body of the class
    private:
        // There is no copy constructor
        no_copy(const no_copy& old_class);
};

Now when the compiler attempts to use the copy constructor, you will get an error message like “Error: Attempt to access private member function.”

Note that in this example, you have defined the prototype for a copy constructor, but no body. Since this function is never called, a body is not needed.

In C++ a structure is just like a class, except that all the data fields and member functions are public. For example, the following two are the same:

struct data {
    int status;
    int data;

    void start(  ) {
        status = 1;
    }
};

class data {
    public:
        int status;
        int data;

        void start(  ) {
            status = 1;
        }
};

As you can see, a structure is merely a class with all the protections removed. This means that in most cases a class is superior to a structure.

In actual practice, most programmers use structures for data only. You’ll hardly ever see a structure with member functions.

Exercise 13-1: Write a parity class. The class supplies a member function named put, which counts the number of elements supplied. The other member function test returns true if an even number of put calls have been made and false otherwise.

Member functions:

void parity::put(  );    // Count another element
bool parity::test(  );   // Return true if an even number of
                           // puts have been done. Return false
                           // for an odd number.

Exercise 13-2: Write a “checkbook” class. You put a list of numbers into this class and get a total out.

Member functions:

void check::add_item(int amount);     // Add a new entry to the checkbook
int check::total(  );                 // Return the total of all items

Exercise 13-3: Write a class to implement a simple queue. A queue is similar to a stack except that the data is removed in first-in-first-out (FIFO) order.

Member functions:

void queue::put(int item);     // Insert an item in the queue
int queue::get(  );            // Get the next item from the queue

Sample usage:

queue a_queue;

a_queue.put(1);    // Queue contains: 1
a_queue.put(2);    // Queue contains: 1 2
a_queue.put(3);    // Queue contains: 1 2 3

std::cout << a_queue.get(  ) << '
';   // Prints 1, queue contains 2 3
std::cout << a_queue.get(  ) << '
';   // Prints 2, queue contains 3

Exercise 13-4: Define a class that will hold the set of integers from 0 to 31. An element can be set with the set member function and cleared with the clear member function. It is not an error to set an element that’s already set or clear an element that’s already clear. The function test is used to tell whether an element is set.

Member functions:

void small_set::set(int item);    // Set an element in the set
void small_set::clear(int item);  // Clear an element in the set
int small_set::test(int item);    // See whether an element is set

Sample usage:

small_set a_set;

a_set.set(3);      // Set contains [3]
a_set.set(5);      // Set contains [3,5]
a_set.set(5);      // Legal (set contains [3,5])

std::cout << a_set.test(3) << '
';    // Prints "1"
std::cout << a_set.test(0) << '
';    // Prints "0"

a_set.clear(5);   // Set contains [3]

Exercise 13-5: I have a simple method of learning foreign vocabulary words. I write the words down on flash cards. I then go through the stack of cards one at a time. If I get a word right, that card is discarded. If I get it wrong, the card goes to the back of the stack.

Write a class to implement this system.

Member functions:

struct single_card {
    std::string question;      // English version of the word
    std::string answer;        // Other language version of the word
};

// Constructor -- takes a list of cards to 
//              initialize the flash card stack
void flash_card::flash_card(single_card list[]);   

// Get the next card 
const single_card& flash_card::get_card(  );

//The student got the current card right
void flash_card::right(  );

// The student got the current card wrong
void flash_card::wrong(  );

//Returns true -- done / false -- more to do
bool done(  );