The Stack as an ADT

An Example: Recursive Functions

Let's consider what happens when we use a recursive function in a program. See gcd.cpp. Whenever the function gcd( ) begins execution (i.e., is activated), an activation record (or stack frame) is created to store the current environment for each call of the function. A stack frame's contents include:

• parameters (signature)

• caller's state information

• local variables

• temporary storage

What kind of data structure should be used to store these items so that they can be recovered and the system is reset when the function main( ) resumes execution?

Problem:

• main( ) can call FunctionA (e.g. , GCD( ))

• FunctionA (e.g. GCD( )) can call FunctionB (e.g. GCD( ))

• FunctionB (e.g. GCD( )) can call FunctionC (e.g. GCD( ))

• FunctionC (e.g. GCD( )) can call FunctionD (e.g. GCD( ))

• etc.… (Opps OverFlow?)

When one function calls another function, the call interrupts the execution of the first function and after the second function ends, the first needs to be able to resume its own execution in the same state it was in before the interruption e.g.:

• When FunctionD finishes, control should return to FunctionC

• When FunctionC finishes, control should return to FunctionB.

• When FunctionB finishes, control should return to FunctionA.

• When FunctionA finishes, control should return to main( ).

This is sometimes referred to as unwinding.

So, the order of returns from a function is the reverse of function invocations; this is a Last In First Out (LIFO) behavior.

Question: How can we implement an ADT to solve this problem?

Answer: Use a stack to store the activation records. Since it is manipulated at run-time, it is called a run-time stack.

Question: What happens when a function is called?

Answer:

• Push a copy of its activation record onto the run-time stack

• Copy its arguments into the parameter spaces

• Transfer control to the address of the function's body

The top activation record in the run-time stack is always that of the function currently executing.

Question: What happens when a function terminates?

Answer:

• Pop activation record of terminated function from the run-time stack

• Use a new top activation record to restore the environment of the next interrupted function and resume execution of the interrupted function.

We will need to be able to implement constructs like this no matter what language we are using. The ADT which meets this need is called a stack.

Introduction to the Stack

A stack is an ordered collection of data items in which access is possible only at one end (called the top of the stack). This construct is sometimes called Last In First Out or LIFO. (A stack is sometimes called a LIFO list.)

For another example of what a stack is, consider the following graphic, which is a stack of books:

In general when placing each individual book on the stack, each individual book is added to the stack at the top (this process is called a Push). When a book is removed, it is removed from the top, one book at a time (this process is called a Pop).

In viewing the graphic above from left to right, it can be seen that there are several different types of actions (functions) that will be needed in order to implement the code necessary to simulate these actions. The implementation will need to be able to do each of the following processes:

• create a place for the stack of books

• place a book on the stack (Push)

• view the top book on the stack

• remove the top book from the stack (Pop)

• determine if there are any books on the stack

• determine if there is any more room for additional books on the stack

An Example: A Stack as a Long Array

Create a C++ Stack to simulate the book example above. The first example of a C++ stack will be an array of long integers (An array is not the only way to create a stack in C++ as can be seen when linked listed and then STL (Standard Temple Library) are considered later in the lectures.

In this example, to start with, the bottom of the stack is at position 0 because an array in C++ starts with index 0 (of course in some other languages an array starts at 1).

The 5 Phases of Software Development

1. The Specifications Phase

2. The Design Phase

3. The Coding Phase (Look at the code very closely. Are there cases where the program could fail? Has the program adequately provided for error handling?)

4. The Testing Phase (What should be done here?)

   To test enter into the stack by Pushing onto the stack the following: 19, 51, 134, 64, 321, 78, 55 and 80. Pop the stack after 80 has been entered. Pick additional values to test what happens when the stack reaches it capacity. If you were a member of Quality Assurance at your company, think of additional tests you might want to use.

5. The Maintenance Phase (What should be anticipated for this phase?)

The Specifications Phase

This C++ example will be a stack that will be numbers stored into an array of longs. So the first step will be to define the stack to be an array of longs of the particular size needed which for this example will be 10 elements.

The value: myTop will be used to contain the index of the top element of the stack (i.e. the value of the last element added to the stack). To begin with, the value of myTop is -1 when the stack has no elements.

Thus after defining the array, the value of myTop should be set to -1.

As discussed above, a stack has two main procedures: Push and Pop. The first is Push which places a new element into the stack. This is accomplished by incrementing myTop and assigning a value to the element of the array to which myTop in the index of. The second is Pop which removes an element from the stack. This is accomplished by decrementing myTop. (Actually, when a Pop occurs, the value of the stack to which myTop was the index of is not removed from the array. While this element has not actually been removed as an array member, this element can no longer be reached because myTop contains a value below the index of the "deleted element".

In addition to these two main procedures, a stack needs to be able to determine if the stack is empty. In this example, the stack would be empty when myTop was equal to -1, i.e. the array has no elements.

Another procedure needed is being able to determine if the stack is full. In this example, the stack would be full when myTop is 1 less than the size of the array.

The last procedure needed is to be able to get access to the top element of the stack. This can be done by looking at the value of the array where myTop is the index of the element of the array.

For example, assume that stack is a long array with 10 elements and that the numbers to be stored into the stack: myStack are to include the following:

 {19, 51, 134, 64, 321, 78, 55, 80} 

The stack should operate like the following:

• The long array: myStack[] is defined to have 10 elements.

• myTop begins with the value -1 meaning that there are no elements in the stack.

• Next myTop is incremented to 0 and 19 is assigned to the element: myStack[0] (i.e. 19 is Pushed onto the stack.)

• Next myTop is incremented to 1 and 51 is assigned to the element myStack[1] (i.e. 51 is Pushed onto the stack.)

• These steps are followed by Pushing 134, 64, 321, 78, 55 and 80 onto the stack by incrementing myTop for each Push and then assigning the number to the respective element of myStack[] as can be seen in the following graphic:

  

• Before each new element is added to the array (Pushed on to the stack), the program will need to determine whether the stack is full, i.e. it needs to be determined whether myTop is 9.

• Before each element is removed from the array (Popped from the stack), the program will need to determine whether the stack is empty, i.e. it needs to determine whether myTop is -1.

• Once all of the numbers have been added to the stack, then they are Popped from the stack by decrementing myTop. This can be seen in the graphic above where 80 was Popped from the stack by decrementing myTop. Of course 80 is still in that place in memory and it is still an element of the array. However, as far as the stack is concerned, 80 has been removed, i.e. Popped from the stack and is no longer available.

To achieve the objectives indicated from the example above, the basic operations of a stack should include:

• Construct a stack (usually empty)

• Check to determine whether the stack is empty

• Check to determine whether the stack is full

• Add an element at the top of the stack (Push)

• Retrieve the top element of the stack

• Remove the top element of the stack (Pop)

Working with this stack, you would begin by determining whether there are any elements in the stack and whether the stack is full before any elements have been entered. For testing purposes, Push the elements:

 19, 51, 134, 64, 321, 78, 55 and 80 

onto the stack. After adding: i.e. Pushing each element onto the stack, test to determine what has been added, whether there are any elements in the stack and whether the stack is full. After the last element has been added, Pop the stack. Again determine what the top element is, whether the stack is full and whether it is empty.

The Design Phase

To implement the specifications, a C++ class needs to be created. Therefore in designing the class, the data members, the operations (member functions) and any other conditions that will be required to achieve the specifications need to be defined into the class.

Independent of the class there will need to be a long:

• capacity: The size of the stack. (For testing purposes, set this to 10.)

The class will have two data members:

• myTop: A long that is the index of the top element.

• myStack[ ]: A long array that holds the elements of the stack.

The class methods that are required are the following:

• Construction: Initializes an empty stack.

• isEmpty method: Determines if the stack contains any values (i.e. return false if myTop > -1 and otherwise true)

• isFull method: Determines if stack has any more room for additional values. (i.e. return false if myTop < capacity -1 and otherwise true)

• Push method: Modifies a stack by adding a value to the top of the stack (i.e. ++myTop and theStack[myTop] = value)

• Top method: Retrieves the value at the top of the stack (i.e. what is theStack[myTop]?)

• Pop method: : Modifies the stack by removing the top value of the stack (i.e. -- myTop)

To assist with debugging, the following method will be added but is not in general a method of a stack:

• Display method: Displays all the elements stored in the stack to the screen.

The following is a UML diagram for the design of the class Stack:

The program should be a menu system that implements a call to each of the stack methods. The stack will be created when the program begins. No pseudo code or structure chart will be provided here since menu programs have been studied previously in these lecture notes.

Designing a Stack Class

The stack created above worked fine for a stack of longs. But what about a stack of chars, doubles or even a stack of Date objects. It would seem reasonable that if at all possible, we should try to make a stack class that is independent of the data type. (In fact this is what is done in the C++ Standard Temple Library (STL) that will be discussed later.)

The question that then arises is: What must be done to the stack class created above to be useful as a stack of any kind of objects? What can be the same and what has to be changed? To create a generalized stack class, we still need the following operations:

• Construction: Initializes an empty stack.

• isEmpty operation: Determines if stack contains any values

• isFull operation: Determines if the stack can hold any more elements.

• Push operation: Modifies a stack by adding a value to top of stack

• Top operation: Retrieves the value at the top of the stack

• Pop operation: Modifies a stack by removing the top value of the stack

To help with debugging, we will add the following:

• Display operation: Displays all the elements stored in the stack.

What must be done is to change any references to long for input and output of the item/members of the class.

The design of these operations must be modified so that they are independent of the class objects being stored in the stack.

What is still needed are the following:

• An array data member whose elements will hold the stack elements.

• An integer data member to indicate the top of the stack

In the above example, the stack was of the form:

 long theArray[theCapacity]; 

However what is needed now is an array definition of the following form:

 stackElementType theArray[theCapacity]; 

where stackElementType could be any data type for theArray[ ]. A solution (for now) is to use the typedef mechanism and put the following before the class' definition:

 typedef long stackElementType; 

In a similar fashion the methods Push( ) and Top( ) need to be changed so that they refer to stackElementType rather than to a long.

The next modification that needs to be considered is how to handle the variable: theCapacity. There are a couple of solutions for it.

1. This variable could be handled as in the example above and the following statement could be placed before the class definition:

    const short theCapacity = 128; 

2. Another solution for theCapacity could be to make it a static data member of the class. In this case the class' definition could contain the following statement:

    static const short theCapacity; 

Then below the class' definition it would be necessary to initialize theCapacity with the following statement:

 static const short Stack::theCapacity = 128; 

In this way theCapacity would be independent of any object of the class.

Regardless of which solution that is used for theCapacity, the array: theArray[ ] needs to be defined as a data member in the private section as in the following:

 stackElementType theArray[theCapacity]; 

See the modified program: stack.cpp. To be sure that the Stack class is as general as possible, check out the following example where the data type is the class Date seen in a previous example. See date.h and new_stack.cpp.

General Comments:

As you construct your stack class, be sure to build in routines that handle possible errors. You will notice that some of the functions in the examples of this lecture do that. However the programmer must go into as great a detail as possible to create a well constructed error handling program. What should be done is to use the C++ reserved words: throw, catch and try.

Another consideration as one develops stack classes like those in this lecture would be to consider whether a destructor should be created to clean up. While that was not needed here, the programmer should always consider whether one is needed. I am sure that you have encountered programs that would not end or did not end correctly. Some of these problems can be related to the lack of a proper destructor. This problem is reduced in the programming language C# that has a garbage collector for this purpose.

In these examples we had to restrict our stack to a predetermined number of items. This can be wasteful of memory and in addition it can lead to memory overflow when we need a larger stack than the one that was defined. This problem can be handled with a construct called vectors and dynamic memory allocation. The ADT vectors are best handled using STL as will be seen in a later lecture.

Factorization: A Stack Example

Suppose that you wanted to find all of the prime factors of a number. For example:

 4 = 2 * 2 6 = 2 * 3 12 = 2 * 2 * 3 18 = 2 * 3 * 3 

These are examples of the prime factorization of the respective numbers. But what about any number in general. First you need to identify all of the primes (well not all but at least say the first 15). The first 15 primes are:

 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43 and 47 

What is needed is to consider how the prime factors of a number are found. For example take the number: 52. The first thing is to check the first prime to see if it divides 52. It does and 52 = 2 * 26. So 26 = 52/2. This is followed by checking all of the primes to see if one divides 26. The prime 2 divides it and the factorization is 26 = 2 * 13. So13 = 26/2. This is followed by finding the prime factorization of 13. In this case the process determines that 13 is a prime number. Therefore:

 52 = 2 * 2 * 13 

What can therefore be done is to take any number. Divide it by elements of the array of primes starting at the smallest and continuing until at least one is found. Once a prime divisor is found, that prime is divided into the number getting an integral quotient. The process is continued until the remaining number is itself a prime.

This problem is well suited to use stacks. That is as each prime factor is found; the prime is placed onto a stack. After all of them are found, the stack can then be "unwound" until the stack is empty. For this problem, the stack class discussed before will be used. See stacks.h.

Using this stack header file and the technique discussed above, a program may be written to handle the problem. For a solution see factors.cpp.