Source code for pointer stack example P.J. Drongowski 4 November 2004 (Updated 16 March 2005) Differences from the simple array stack implementation * Use of dynamic storage allocation to obtain storage for the array to hold stack items * A copy constructor to make an exact copy of an existing stack + Allocates memory for the stack item array dynamically + Copies the contents of the existing stack array to the new one * A destructor to deallocate the stack array * Use of a pointer variable to remember the current top of stack * Use of exceptions to catch bad allocation exceptions (i.e., exceptions thrown by new) This stack implementation uses dynamic memory allocation to allocate space to store the stack items. While you take a tour of the code, please note the following differences between this implementation and the array stack implementation in project #4. The constructor uses the C++ new operator to allocate an array for the stack items. The size of the array is specified by the argument to the constructor. The new operation is surrounded by a "try-catch" block to catch any exceptions thrown by new (e.g., no storage space available.) Because we are allocating storage for the array dynamically, we must provide a copy constructor for stack objects. C++ inserts calls to the copy constructor whenever the program must make a copy of an old object, such as when passing an object by value to a function. The copy constructor allocates space for a copy of the stack values, then copies the old stack values into the new array. The copy constructor must also copy the values of any "ordinary" data members. The destructor deallocates the array storage using the delete operator. The programmer must deallocate (release) any dynamically allocated storage. If not, the storage will be lost and cannot be reclaimed or reused. This is called a "memory leak." If enough storage is lost, there may not be enough storage to satisfy allocation requests using the new operator. In which case, an exception will be thrown or the program will ungracefully terminate. In push, pop, etc., we are using a pointer to maintain the top of stack instead of an integer index. We are also using an integer variable to remember the stack depth (i.e., the number of items in the stack) in order to detect stack empty, overflow, etc. *********************************************** ptr_stack.h *********************************************** #ifndef ARRAY_STACK_H #define ARRAY_STACK_H class Stack { public: Stack(int size = DEFAULT_SIZE) ; Stack(const Stack &old) ; // Copy constructor ~Stack() ; // Destroy stack void clear() ; // Reset the stack void push(int value) ; // Push item on stack int pop() ; // Pop and return top of stack int getTop() ; // Return top item without popping bool isEmpty() ; // Return true if stack is empty void showAll() ; // Shows all items in stack void showTop() ; // Shows top item on stack private: static const int DEFAULT_SIZE = 128 ; int *topOfStack ; // Pointer to top of stack int *stackValues ; // Pointer to array of values int stackSize ; // Size of stack array int stackDepth ; // Number of items in stack bool checkUnderflow(const char *method) ; bool checkOverflow(const char *method) ; } ; #endif *********************************************** ptr_stack.h *********************************************** #include using namespace std ; #include "ptr_stack.h" // Function: Stack // Purpose: Create a new stack object // Side effects: // Allocates the stack value array. Size of // the array is one otem larger than requested // to accommodate an "empty" item. Initializes // topOfStack pointer and stackDepth. Stack::Stack(int size) { // Use depth == 0 as stack empty indicator stackDepth = 0 ; // Allocate stack value array try { stackValues = new int[size+1] ; } catch(bad_alloc ex) { cerr << "*error* Unable to allocate stack array" << endl ; cerr << "Requested stack size: " << size << endl ; cerr << "Exception: " << ex.what() << endl ; exit(1) ; } // Save stack size for later checks stackSize = size ; // First item in array is reserved for "empty" topOfStack = stackValues ; } // Function: Stack // Purpose: Copy constructor // Parameters: // old: Reference to old stack to be copied // Side-effects: // Initializes copy of stack Stack::Stack(const Stack &old) { int i ; stackSize = old.stackSize ; stackDepth = old.stackDepth ; try { stackValues = new int[stackSize+1] ; } catch(bad_alloc ex) { cerr << "*error* Unable to alloc array (copy)" << endl ; cerr << "Requested stack size: " << stackSize+1 << endl ; cerr << "Exception: " << ex.what() << endl ; exit(1) ; } for (i = 0 ; i <= stackDepth ; i++) { stackValues[i] = old.stackValues[i] ; } topOfStack = &stackValues[stackDepth] ; } // Function: ~Stack // Purpose: Destroys an existing stack object // Side-effects: // Release stack array storage Stack::~Stack() { delete [] stackValues ; } // Function: checkUnderflow // Purpose: Check for stack underflow condition // Returns: // false if underflow, true if no underflow bool Stack::checkUnderflow(const char *method) { // Check for an empty stack if (isEmpty()) { cerr << "*error* Stack underflow (" << method << ")" << endl ; return( false ) ; } return( true ) ; } // Function: checkOverflow // Purpose: Check for stack overflow condition // Returns: // false if overflow, true if no overflow bool Stack::checkOverflow(const char *method) { // Check for overflow if (stackDepth >= stackSize) { cerr << "*error* Stack overflow (" << method << ")" << endl ; return( false ) ; } return( true ) ; } void Stack::clear() { // Reset stack stackDepth = 0 ; topOfStack = stackValues ; } void Stack::push(int value) { // Increment stackDepth stackDepth = stackDepth + 1 ; if (checkOverflow("push")) { // Write new TOS value *++topOfStack = value ; } else { stackDepth = stackDepth - 1 ; cerr << "*warning* push() ignored\n" ; } } int Stack::pop() { int value ; if (checkUnderflow("pop")) { // Return current TOS value = *topOfStack-- ; // Decrement stackDepth stackDepth = stackDepth - 1 ; return( value ) ; } else { cerr << "*warning* pop() ignored\n" ; cerr << "*warning* Returning zero\n" ; return( 0 ) ; } } int Stack::getTop() { if (! isEmpty()) { return( *topOfStack ) ; } else { cerr << "*warning* getTop: Stack is empty\n" ; cerr << "*warning* getTop: Returning zero\n" ; return( 0 ) ; } } bool Stack::isEmpty() { // Return true if stack is empty return( stackDepth == 0 ) ; } void Stack::showAll() { int index ; int *ptrItem ; cout << "Stack contents: " ; ptrItem = topOfStack ; for( index = stackDepth ; index > 0 ; index--) { cout << *ptrItem-- << " " ; } cout << "<>" << endl ; } void Stack::showTop() { if (! isEmpty()) { cout << "TOS: " << *topOfStack << endl ; } else { cerr << "*warning* showTop: Stack is empty\n" ; cerr << "*warning* showTop: Cannot display top of stack\n" ; } }