Linked Implementation of Stacks

[qingquan-li]

LinkedStackDemo/LinkedStackType.h

// This class specifies that basic operations on a stack
// as a linked list.

#ifndef LINKEDSTACKTYPE_H
#define LINKEDSTACKTYPE_H

// Defination of the node
template <class T>
struct node
{
    T info;
    node<T> *link;
};

template <class T>
class LinkedStackType
{
private:
    // stackTop gives the address of the top element of the stack.
    node<T> *stackTop; //Pointer to the stack

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

public:
    LinkedStackType();
    //Default constructor
    //Postcondition: stackTop = NULL;

    LinkedStackType(const LinkedStackType<T> & otherStack);
    //Copy constructor

    ~LinkedStackType();
    //Destructor
    //Postcondition: All the elements of the stack are removed from the stack.

    const LinkedStackType<T> & operator=
            (const LinkedStackType<T> & otherStack);
    //Overloaded assignment operator

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

    //In this linked implementation of stacks, the memory to store the stack
    //elements is allocated dynamically. Logically, the stack is never full.
    //bool isFullStack() const;
    //Function to determine whether the stack is full.
    //Postcondition: Returns false.

    void initializeStack();
    //Function to initialize the stack to an empty state.
    //Postcondition: The stack elements are removed; stackTop = NULL.

    void push(const T & 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.

    T 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 //LINKEDSTACKTYPE_H

LinkedStackDemo/LinkedStackType.cpp

#include <iostream>
#include <cassert>

#include "LinkedStackType.h"

using namespace std;

/*
 * Default constructor
 * Initializes the stack to an empty state when a stack object is declared.
 */
template <class T>
LinkedStackType<T>::LinkedStackType()
{
    stackTop = NULL;
}

/*
 * Copy constructor
 * Makes a copy of otherStack.
 */
template <class T>
LinkedStackType<T>::LinkedStackType(const LinkedStackType<T> & otherStack)
{
    stackTop = NULL;
    copyStack(otherStack);
}

/*
 * Destructor
 * Removes all the elements from the stack.
 */
template <class T>
LinkedStackType<T>::~LinkedStackType()
{
    initializeStack();
}

/*
 * Overloaded assignment operator
 * Copies otherStack into this stack.
 */
template <class T>
const LinkedStackType<T> & LinkedStackType<T>::operator=
        (const LinkedStackType<T> & otherStack)
{
    if (this != &otherStack) //avoid self-copy
        copyStack(otherStack);

    return *this;
}

/*
 * Function to determine whether the stack is empty.
 * Postcondition: Returns true if the stack is empty,
 *                otherwise returns false.
 */
template <class T>
bool LinkedStackType<T>::isEmptyStack() const
{
    return (stackTop == NULL);
}

/*
 * Function to initialize the stack to an empty state.
 * Postcondition: The stack elements are removed; stackTop = NULL.
 */
template <class T>
void LinkedStackType<T>::initializeStack()
{
    node<T> *temp; //pointer to delete the node

    while (stackTop != NULL) //while there are elements in the stack
    {
        temp = stackTop; //set temp to point to the current node
        stackTop = stackTop->link; //advance stackTop to the next node
        delete temp; //deallocate memory occupied by temp
    }
}

/*
 * 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.
 */
template <class T>
void LinkedStackType<T>::push(const T & newItem)
{
    node<T> *newNode; //pointer to create the new node

    newNode = new node<T>; //create the node

    newNode->info = newItem; //store newItem in the node
    newNode->link = stackTop; //insert newNode before stackTop
    stackTop = newNode; //set stackTop to point to the top node
}

/*
 * 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.
 */
template <class T>
T LinkedStackType<T>::top() const
{
    assert(stackTop != NULL); //if stack is empty, terminate the program
    return stackTop->info; //return the top element
}

/*
 * 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.
 */
template <class T>
void LinkedStackType<T>::pop()
{
    node<T> *temp; //pointer to deallocate memory

    if (stackTop != NULL)
    {
        temp = stackTop; //set temp to point to the top node

        stackTop = stackTop->link; //advance stackTop to the next node
        delete temp; //delete the top node
    }
    else
        cout << "Cannot remove from an empty stack." << endl;
}

/*
 * Copy stack
 * Makes an identical copy of otherStack.
 */
template <class T>
void LinkedStackType<T>::copyStack(const LinkedStackType<T> & otherStack)
{
    node<T> *newNode, *current, *last;

    if (stackTop != NULL) //if stack is nonempty, make it empty
        initializeStack();

    if (otherStack.stackTop == NULL)
        stackTop = NULL;
    else
    {
        current = otherStack.stackTop; //set current to point to the stack to be copied

        //copy the stackTop element of the stack
        stackTop = new node<T>; //create the node

        stackTop->info = current->info; //copy the info
        stackTop->link = NULL; //set the link field of the node to NULL
        last = stackTop; //set last to point to the node
        current = current->link; //set current to point to the next node

        //copy the remaining stack
        while (current != NULL)
        {
            newNode = new node<T>;

            newNode->info = current->info;
            newNode->link = NULL;
            last->link = newNode;
            last = newNode;
            current = current->link;
        }//end while
    }//end else
}//end copyStack

LinkedStackDemo/main.cpp

// A client's program illustrates how a linked stack object is used.

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

using namespace std;

// Function prototypes
void testCopy(LinkedStackType<int> OStack);


int main()
{
    LinkedStackType<int> stack;
    LinkedStackType<int> otherStack;
    LinkedStackType<int> newStack;

    stack.push(34);
    stack.push(43);
    stack.push(27);

    // Use the assignment operator to copy the elements of stack into
    // newStack.
    newStack = stack;

    cout << "After the assignment operator (`newStack = stack;`), "
            "newStack: " << endl;

    // Output the elements of newStack.
    while (!newStack.isEmptyStack())
    {
        cout << newStack.top() << endl;
        newStack.pop();
    }

    cout << endl;

    // Use the assignment operator to copy the elements of stack into
    // otherStack.
    otherStack = stack;

    cout << "Testing the copy constructor: `testCopy(otherStack);`" << endl;
    testCopy(otherStack);

    cout << "After the copy constructor, otherStack: " << endl;

    // Output the elements of otherStack.
    while (!otherStack.isEmptyStack())
    {
        cout << otherStack.top() << endl;
        otherStack.pop();
    }

    return 0;
}


// Function to test the copy constructor.
void testCopy(LinkedStackType<int> OStack)
{
    cout << "Stack in the function testCopy: " << endl;

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

    cout << endl;
}

Output:

After the assignment operator (`newStack = stack;`), newStack: 
27
43
34

Testing the copy constructor: `testCopy(otherStack);`
Stack in the function testCopy: 
27
43
34

After the copy constructor, otherStack: 
27
43
34