13.1 Stacks

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.

Table 13-1. Stack operation

Operation	Stack after operation
Push (4)	4
Push (5)	5 4
Push (8)	8 5 4
Pop (returns 8)	5 4
Pop (returns 5)	4
Push (9)	9 4
Pop (returns 9)	4
Pop (returns 4)	<empty>

13.1.1 Designing a Stack

The easiest way to design a stack is to let someone else do it. C++ comes with a very nice stack class as part of the Standard Template Library (See Chapter 25.) But to learn about simple classes, in this chapter we are going to create our own.

We start a stack design by designing the data structure. This structure will need a place to put the data (called data) and a count of the number of items currently pushed on the stack (called count):

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 
}; 

Next you need to create the routines to handle the push and pop operations. The push function stores the item on the stack and then increases the data count:

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;
}

This version of the program does not do a good job of checking for stack overflow or other error conditions. Later, in Chapter 14, you'll see how you can use this simple stack to make a safer, more complex one.

Popping simply removes the top item and decreases the number of items in 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]); 
} 

There is one item you've overlooked: initializing the stack. You must set up the stack before you can use it. Keeping with the spirit of putting everything in a stack_xxxx routine, create the stack_init function:

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

Notice that you don't need to zero the data field in the stack, since the elements of data are overwritten by the push operation.

You are now finished. To actually use the stack, you declare it and initialize it, then you can push and pop to your heart's content (or at least within the limits of the stack):

    stack a_stack;    // Declare the stack

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

Example 13-1 contains a complete implementation of the structure version of the stack and a short test routine.

Example 13-1. stack_s/stack_s.cpp

/********************************************************
 * 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 <assert.h>
#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) << '\n';
    std::cout << "Expect a 2 ->" << stack_pop(a_stack) << '\n';
    std::cout << "Expect a 1 ->" << stack_pop(a_stack) << '\n';

    return (0);
}