Implementation of Stacks as Arrays

[qingquan-li]

StackADT.h

// This abstract class StackADT specifies the basic operations on a stack.
// This class defines these operations as an ADT (Abstract Data Type).

#ifndef STACKADT_H
#define STACKADT_H

template <class Type>
class StackADT
{
public:
    virtual void initializeStack() = 0;
    //Method to initialize the stack to an empty state.
    //Postcondition: Stack is empty.

    virtual bool isEmptyStack() const = 0;
    //Function to determine whether the stack is empty.
    //Postcondition: Returns true if the stack is empty,
    //               otherwise returns false.

    virtual bool isFullStack() const = 0;
    //Function to determine whether the stack is full.
    //Postcondition: Returns true if the stack is full,
    //               otherwise returns false.

    virtual void push(const Type& newItem) = 0;
    //Function to add newItem to the stack.
    //Precondition: The stack exists and is not full.
    //Postcondition: The stack is changed and newItem
    //               is added to the top of the stack.

    virtual Type top() const = 0;
    //Function to return the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: If the stack is empty, the program
    //               terminates; otherwise, the top element
    //               of the stack is returned.

    virtual void pop() = 0;
    //Function to remove the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: The stack is changed and the top
    //               element is removed from the stack.
};

#endif //STACKADT_H

ArrayBasedStack.h

// This class specifies the basic operation on a stack as an array.
// Because all the elements of a stack are of the same type, a stack can be
// implemented as either an array (with fixed size) or a linked structure.
// Use an array to implement a stack:
// The first element of the array is the top of the stack.
// The top of the stack is the index of the last element pushed onto the stack.
// A stack element is accessed only through the top of the stack.

#ifndef ARRAYBASEDSTACK_H
#define ARRAYBASEDSTACK_H

#include "StackADT.h"

template <class Type>
class ArrayBasedStack : public StackADT<Type>
{
private:
    int maxStackSize; //variable to store the maximum stack size
    int stackTop; //variable to point (index) to the top of the stack
    // The value of stackTop indicates the number of elements in the
    // stack, and the value of stackTop - 1 points to the top item
    // in the stack.
    // Note that stackTop can range from 0 to maxStackSize. If stackTop
    // is nonzero, then stackTop - 1 is the index of the top element of
    // the stack.
    Type *list; //pointer to the array that holds the stack elements

    void copyStack(const ArrayBasedStack<Type>& otherStack);
    //Function to make a copy of otherStack.
    //Postcondition: A copy of otherStack is created and assigned to this stack.

public:
    ArrayBasedStack(int stackSize = 100);
    //Constructor
    //Create an array of the size stackSize to hold
    //the stack elements. The default stack size is 100.
    //Postcondition: The variable list contains the base
    //               address of the array, stackTop = 0, and
    //               maxStackSize = stackSize

    ~ArrayBasedStack();
    //Destructor
    //Remove all the elements from the stack.
    //Postcondition: The array (list) holding the stack
    //               elements is deleted.

    ArrayBasedStack(const ArrayBasedStack<Type>& otherStack);
    //Copy constructor

    const ArrayBasedStack<Type>& operator=(const ArrayBasedStack<Type>&);
    //Overload the assignment operator.

    void initializeStack();
    //Function to initialize the stack to an empty state.
    //Postcondition: stackTop = 0

    bool isEmptyStack() const;
    //Function to determine whether the stack is empty.
    //Postcondition: Returns true if the stack is empty,
    //               otherwise returns false.

    bool isFullStack() const;
    //Function to determine whether the stack is full.
    //Postcondition: Returns true if the stack is full,
    //               otherwise returns false.

    void push(const Type& newItem);
    //Function to add newItem to the stack.
    //Precondition: The stack exists and is not full.
    //Postcondition: The stack is changed and newItem
    //               is added to the top of the stack.

    Type top() const;
    //Function to return the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: If the stack is empty, the program
    //               terminates; otherwise, the top element
    //               of the stack is returned.

    void pop();
    //Function to remove the top element of the stack.
    //Precondition: The stack exists and is not empty.
    //Postcondition: The stack is changed and the top
    //               element is removed from the stack.
};

#endif //ARRAYBASEDSTACK_H

ArrayBasedStack.cpp

#include <iostream>
#include <cassert>

#include "ArrayBasedStack.h"

using namespace std;


template <class Type>
ArrayBasedStack<Type>::ArrayBasedStack(int stackSize)
{
    if (stackSize <= 0)
    {
        cout << "Size of the array to hold the stack must "
             << "be positive." << endl;
        cout << "Creating an array of size 100." << endl;

        maxStackSize = 100;
    }
    else
        maxStackSize = stackSize; //set the stack size to
                                  //the value specified by
                                  //the parameter stackSize

    stackTop = 0; //set stackTop to 0
    list = new Type[maxStackSize]; //create the array to
                                   //hold the stack elements
}//end constructor


template <class Type>
ArrayBasedStack<Type>::~ArrayBasedStack()
{
    delete [] list; //deallocate the memory occupied
    //by the array
}//end destructor


template <class Type>
ArrayBasedStack<Type>::ArrayBasedStack(const ArrayBasedStack<Type>& otherStack)
{
    list = NULL;

    copyStack(otherStack);
}//end copy constructor


template <class Type>
const ArrayBasedStack<Type>& ArrayBasedStack<Type>::operator=
                                (const ArrayBasedStack<Type>& otherStack)
{
    if (this != &otherStack) //avoid self-copy
        copyStack(otherStack);

    return *this;
}//end operator=


template <class Type>
void ArrayBasedStack<Type>::initializeStack()
{
    stackTop = 0; //set stackTop to 0
}//end initializeStack


template <class Type>
bool ArrayBasedStack<Type>::isEmptyStack() const
{
    return (stackTop == 0);
}//end isEmptyStack


template <class Type>
bool ArrayBasedStack<Type>::isFullStack() const
{
    return (stackTop == maxStackSize);
} //end isFullStack


template <class Type>
void ArrayBasedStack<Type>::push(const Type& newItem)
{
    if (!isFullStack())
    {
        list[stackTop] = newItem;   //add newItem at the top
        stackTop++; //increment stackTop
    }
    else
        cout << "Cannot add to a full stack." << endl;
}//end push


template <class Type>
Type ArrayBasedStack<Type>::top() const
{
    assert(stackTop != 0);      //if stack is empty,
                                //terminate the program
    return list[stackTop - 1];  //return the element of the
                                //stack indicated by
                                //stackTop - 1
}//end top


template <class Type>
void ArrayBasedStack<Type>::pop()
{
    if (!isEmptyStack())
        stackTop--; //decrement stackTop
    else
        cout << "Cannot remove from an empty stack." << endl;
}//end pop


template <class Type>
void ArrayBasedStack<Type>::copyStack
                     (const ArrayBasedStack<Type>& otherStack)
{
    delete [] list;
    maxStackSize = otherStack.maxStackSize;
    stackTop = otherStack.stackTop;

    list = new Type[maxStackSize];

    //copy otherStack into this stack
    for (int j = 0; j < stackTop; j++)
        list[j] = otherStack.list[j];
}//end copyStack

main.cpp

// This program tests various operations of a stack.

#include <iostream>
#include "ArrayBasedStack.cpp"

using namespace std;

// Function prototypes
void testCopyConstructor(ArrayBasedStack<int> otherStack);


int main()
{
    ArrayBasedStack<int> stack(50);
    ArrayBasedStack<int> copyStack(50);
    ArrayBasedStack<int> dummyStack(100);

    stack.initializeStack();
    stack.push(23);
    stack.push(45);
    stack.push(38);
    copyStack = stack; //copy stack into copyStack

    cout << "The elements of copyStack: ";

    while (!copyStack.isEmptyStack())
    {
        cout << copyStack.top() << " ";
        copyStack.pop();
    }
    cout << endl;

    copyStack = stack;
    testCopyConstructor(stack); //test copy constructor

    if (!stack.isEmptyStack())
        cout << "The original stack is not empty." << endl
             << "The top element of the original stack: "
             << copyStack.top() << endl;

    dummyStack = stack; //copy stack into dummyStack

    cout << "The elements of dummyStack: ";

    while (!dummyStack.isEmptyStack())
    {
        cout << dummyStack.top() << " ";
        dummyStack.pop();
    }

    cout << endl;

    return 0;
}

void testCopyConstructor(ArrayBasedStack<int> otherStack)
{
    if (!otherStack.isEmptyStack())
    {
        cout << "otherStack is not empty." << endl;
        cout << "The top element of otherStack: "
             << otherStack.top() << endl;
    }
}


/* Output:
The elements of copyStack: 38 45 23
otherStack is not empty.
The top element of otherStack: 38
The original stack is not empty.
The top element of the original stack: 38
The elements of dummyStack: 38 45 23
*/