Lesson 1

This module explores how to use classes to construct a dynamically sized stack. By closely examining this implementation of a useful data structure, you will learn:

1. How a constructor member function can be overloaded to allow different initializations
2. How to use a copy constructor
3. How a destructor member function works

You know that an automatic variable is created when its definition is executed. The space for an automatic variable is allocated in a memory area called the stack. The stack has a fixed size that is determined by your compiler and there is usually a compiler option that enables you to change the stack size although this is rarely necessary. At the end of the block in which an automatic variable is defined, the memory allocated for the variable on the stack is released, and is thus free to be reused. When you call a function, the arguments you pass to the function will be stored on the stack along with the address of the location to return to when execution of the function ends. Memory that is not occupied by the operating system or other programs that are currently loaded is called the heap or the free store.
You can request that space be allocated within the free store at runtime for a new variable of any type. You do this using the new operator, which returns the address of the space allocated and you store the address in a pointer. The new operator is complemented by the delete operator, which releases memory that you previously allocated with new. Both new and delete are keywords, so you must not use them for other purposes.

This ensures that the memory can be used subsequently by another variable. If you do not use delete, and you store a different address in pvalue, it will be impossible to free up the original memory because access to the address will have been lost. The memory will be retained for use by your program until the program ends. Of course, you cannot use it because you no longer have the address. Note that the delete operator frees the memory but does not change the pointer. After the previous statement has executed, pvalue still contains the address of the memory that was allocated, but the memory is now free and may be allocated immediately to something else, possibly by another program. The pointer now contains a spurious address so you should always reset a pointer when you release the memory to which it points, like this:

delete pvalue; // Release memory pointed to by pvalue
pvalue = nullptr; // Reset the pointer

Now pvalue does not point to anything. The pointer cannot be used to access the memory that was released. Using a pointer that contains nullptr to store or retrieve data will terminate the program immediately, which is better than the program staggering on in an unpredictable manner with data that is invalid.

A stack differs from a list in the following way. A client of a list can access any element and can insert elements at any location. However, a client of a stack can access only the element that was most recently inserted in the stack. This may seem like a serious restriction that would make stacks not very useful, but it turns out that stacks are actually one of the most commonly used data structures in computer science. For example, during program execution a stack is used to store information about the parameters and return addresses for all the functions that are currently executing. Compilers also use stacks to store information while evaluating expressions. Part of the reason for the widespread use of stacks is that a stack is relatively easy to implement. This was an important consideration for programming in languages that did not provide the capability for implementing ADTs as classes. After describing the stack ADT and providing a header file for this ADT, we will discuss two simple applications of stacks: checking for palindromes and testing for balanced parentheses. We will then show how to implement stacks in two ways: using 1) a standard container and 2) a linked list. Finally, we will study how to use stacks to evaluate arithmetic expressions.