Notes 7a:
Addendum A to Essentials of Data Structures, Cpt 7

Math 61 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

Contents

• Array Implementation of a Stack in C++
• Coding Member Functions
• Testing for an Empty Stack
• Push
• Pop
• Peek

Array Implementation of a Stack in C++

(Cf. F&T, pp 189ff)

We will first implement a stack using an array as the underlying, fundamental data structure, and then use a different approach which will include "pointer" variables and "linked lists."

We can contrast how a stack is implemented in Pascal or even in (pure) C with how we can implement it in C++. In C++ we can make use of "data encapsulation" and include within the class both the data storage structure as well as the fundamental operations which operate on the data. Including operations in a record structure is not possible in many older languages!

Thus, in C++, (among other things) "push" and "pop" are member functions within the class that we design as our "stack" data structure, and the actual data storage structure (the array) is kept private and unable to be accessed except by means of the member functions of the class.

For the sake of generality, F&T write the code using the data-type "DataType", which may be defined to be any standard or user defined type. This may be done by means of a typedef statement as follows. If one wishes, in a specific program, to make DataType actually be int, one includes the statement:

     typedef int DataType;

In creating a stack, we assume some maximum number of elements in the stack. It is best to declare this as a constant identifier, e.g.,

      const int MaxStackSize = 50;

         class Stack
	 {
	    private:
	       DataType stacklist[MaxStackSize];
	       int top;
	    public:
	       //... to be determined ...
	 }

• Push (as a void function which takes one argument, the item to be added to the stack)
• Pop (as a "value" function which returns a value of type DataType and takes no argument),
• StackEmpty (as a "value" function which returns true [i.e., 1] or false [i.e., 0]), and
• Peek (as a "value" function which returns a value of type DataType and takes no argument).

• ClearStack (as a void function which removes any contents in the stack), and
• StackFull (as a void function which determines whether we have reached the designated maximum number of elements in the stack).

Coding Member Functions

In the following code, we assume that the first element into the stack will be placed in subscript location zero, and the others will follow in higher numbered subscript locations. We also assume that the "top of stack" pointer points to (i.e., has the subscript value of) the last location used for a stack element. Thus, if the stack is empty, the "top of stack" value is -1, and before storing an element in the stack, we must increase the "top of stack" pointer value.

Internal to Push and Pop we will also test to make sure that we have not exceeded the capacity of the stack and that the stack actually contains something to "pop" off.

C++ provides a standard output "file" called cerr in which error messages can be directed. Also there is an abrupt ending function, exit, which is usually given the argument of 1 when used to abort the program's operation immediately. This value can be tested at the system level to determine whether a program ended abnormally or not. (Cf. Savitch 2, p. 226)

The F&T book sometimes uses const to designate member functions which do not change anything in the class. This is an optional modifier which helps by warning the user if something has been miscoded and the member function is, in fact, changing something it was not intended to do. Its use is completely optional. (Cf. F&T, p. 9, Savitch 2, p 453-56. Also Notes M1 for Math 10.)

Testing for an Empty Stack

To determine whether a stack is empty, we merely need to check the value of the "top of stack" pointer to see whether it is -1 or not. This can be done by using the logical expression top == -1 which evaluate to 1 (true) if it is true or 0 (false) if false. Thus, we need only return the value of this expression without any other statements needed.

       int Stack::StackEmpty(void)
       {
          return (top == -1);
       }

Push

        void Stack::Push (DataType & item)
	{
	  // if the stack is full, terminate the program
	  if (top == MaxStackSize-1)
	  {
	     cerr << "Stack overflow!" << endl;
	     exit (1);
	  }
	  // else increment top and copy item to stacklist
	  top++;
	  stacklist[top] = item;
       }

Pop

       DataType Stack::Pop (void)
       {
          DataType temp;
          // if the stack is empty, terminate the program
	  if (top == -1)
	  {
	     cerr << "Attempt to pop an empty stack!" << endl;
	     exit(1);
	  }
	  // copy the top element
	  temp = stacklist[top];
	  // decrement the top pointer
	  top--;
	  // return the top value from temp
	  return temp;
       }

Peek

       DataType Stack::Peek (void)
       {
          // if the stack is empty, terminate the program
	  if (top == -1)
	  {
	     cerr << "Attempt to peek at an empty stack!" << endl;
	     exit(1);
	  }
	  // return the top element
	  return stacklist[top];
       }

This page is maintained by Dennis C. Smolarski, S.J.
© Copyright 1998 Dennis C. Smolarski, SJ, All rights reserved.
Last changed: 28 April 1998.