Intermediate Business Programming with C++

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:

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:

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.:

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:

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:

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:

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:

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

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:

The class will have two data members:

The class methods that are required are the following:

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

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:

To help with debugging, we will add the following:

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:

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.

Related

Категории