Data Structures Demystified (Demystified)

Stack in Action Using C++

Now that you understand how to create and use a stack, we ll pick up the pace and explore an industrial-strength stack. You ve may have heard the term industrial strength used in relation to programming and may be curious what this really means.

Industrial strength is a term used in industry that implies a product is designed to withstand stress. Industrial strength can be used to describe any kind of product, but in this case the product is the program that creates and uses a stack.

Programs used to illustrate the concepts of a stack in this chapter are bare bones and lack the robust features that are found in industrial-strength programs. A bare-bones program is what you need when you re learning the concepts of stacks and other data structures because the program contains only statements that pertain to what you are learning.

However, once you learn the concept, you need to see how it s applied in a real-world program. That s what we ll be exploring in the Stack in Action sections of this chapter. In this section, you ll take a look at how a stack is created and used in an industrial-strength C++ program. Later, you ll see the Java version of this program.

We ll use as an example an industrial-strength C++ program that creates and uses a stack. The program is contained within three files, stack.h , stack.cpp , and stackDemo.cpp . The stack.h file is a header file that contains the definition of the Stack class, which is the blueprint of the Stack class. The stack.cpp file is a source code file that contains the implementation of the member functions of the Stack class. The stackDemo.cpp file contains the source code for the C++ program that declares the instance of the Stack class and calls its member functions. Let s begin by taking a look at the stack.h header file, which is shown in the next code example. As you ll recall from your C++ classes, a header file typically contains definitions and preprocessor instructions. A preprocessor is a program that applies preprocessor instructions to source code before the code is compiled.

The stack.h header file contains one preprocessor instruction, #define , which defines a symbol. Here we ve defined the symbol DEFAULT_SIZE and given it a value of 10. The preprocessor then replaces all occurrences of DEFAULT_SIZE with 10 before the code is compiled. The DEFAULT_SIZE is the default size of the stack if the no argument is passed to the constructor. Function parameters in C and C++ can be assigned default values in the function prototype as long as those arguments are at the end of the argument list. If the size value is not passed in, it gets defaulted to the value of DEFAULT_SIZE , which is 10 in our example.

The stack.h file also contains the definition of the Stack class. The Stack class definition has the same size , top , and values attributes you saw in the previous C++ example. However, the definition of member functions is different from what you saw because member functions are implemented outside the class definition in the stack.cpp source code file. The header file contains only the prototype of the functions, which make up the blueprint for the class.

From your C++ class, you ll remember that only the prototype or signature of a member function needs to be included in a class definition. The implementation of the member function can be outside the class definition. There are two important reasons for keeping the definition (header file) and implementation (source) in separate files:

• It keeps your development environment cleaner and easier to understand.

• It allows you to provide a commercial software application programmer interface to a programmer without handing over your source code. You provide the programmer with your header files, which they will use to compile their code (they only need header files to compile the code). You provide your source code in the form of precompiled libraries that are referenced by the programmer s program during linking.

The class definition contains signatures of six member functions. The first member function is called Stack , which is the constructor that you learned about previously in this chapter. Previously, you learned that the constructor is passed an integer representing the size of the stack. In the real-world version, the program sets a default size that can be overridden when an instance of the class is created in the program. The default size is specified by using the DEFAULT_SIZE , which is 10 (see #define ).

The next member function is ~Stack() and is the destructor of the class. A destructor is the last member function that is called when the instance of the class goes out of scope and dies. A constructor must always be the same name as the class and begin with a tilde (~). By definition, destructors cannot accept any arguments. The purpose of the destructor is to free memory that is used by the stack or do any other sort of cleanup that s required.

The remaining member functions are the same functions that you learned about previously in this chapter.

//stack.h #define DEFAULT_SIZE 10 class Stack { private: int size; int top; int* values; public: Stack(int size = DEFAULT_SIZE); virtual ~Stack(); bool isFull(); bool isEmpty(); void push(int); int pop(); };

The stack.cpp file is a source code file that contains the implementation of the Stack class s member functions. We placed these in a different file from the class definition because it is easier to read and maintain as well as for other reasons explained previously.

The file begins with the preprocessor instruction #include that tells the computer to evaluate the contents of the stack.h file before compiling the stack.cpp file so it knows about the Stack class definition before compiling the program.

Member functions in the stack.cpp file will be familiar to you because all except one are the same member functions that you learned about previously in the chapter. However, the names of the member functions might be confusing at first glance because each name begins with the name of the class followed by two colons (::). The two colons are called the scope resolution operator .

You must precede the name of a member function with the class name and scope resolution operator if the member function is defined outside the class definition. Think of this as telling the computer that the member function belongs to the Stack class.

The ~Stack() member function frees memory used by the stack. It does this by using the delete operator and referencing the name of the array used for the stack. In this example, values is the name of the array.

To avoid memory leaks, freeing memory is important whenever memory is dynamically allocated. The square brackets ([]) are used with delete because the object being removed from memory was dynamically created.

The stack.cpp is compiled as you would compile any source code. The result is an object file that is joined together with the compiled stackDemo.cpp source code file by the linker to create an executable program called a load module .

//stack.cpp #include "stack.h" Stack::Stack(int size) { this->size = size; values = new int[size]; top = -1; } Stack::~Stack() { delete[] values; } bool Stack::isFull() { if(top < size-1) { return false; } else { return true; } } bool Stack::isEmpty() { if(top == -1) { return true; } else { return false; } } void Stack::push(int x) { if(!isFull()) { top++; values[top] = x; } } int Stack::pop() { int retVal = 0; if(!isEmpty()) { retVal = values[top]; top--; } return retVal; }

Finally, we come to the stackDemo.cpp program, which is the C++ program that creates the instance of the Stack class. The first statement creates the stack in a three-step process. The first step is to use the new operator to allocate space in memory for the Stack class by calling the constructor of the class. The new operator returns the memory location of the stack. The second step is to declare a pointer called stack . The last step is to assign the memory location returned by the new operator to the stack pointer.

In this example, we used the default size for the stack, which is 10 elements. We can pass the Stack() constructor an integer to change the size of the stack.

The push() member function is called three times. Each time a different value is placed on the stack. Notice that the - > pointer is used instead of the dot operator. You must do this because stack is a pointer to an instance of the class and not the instance itself.

The last portion of the stackDemo.cpp program calls the pop() member three times. Each time a value is removed from the top of the stack and displayed on the screen.

//stackDemo.cpp void main() { Stack *stack = new Stack(); stack->push(10); stack->push(20); stack->push(30); for(int i=0; i<3; i++) { cout << stack->pop() << endl; } }