Data Structure and Algorithm - Stack - stackAsLinkdedlist.h source code

stackAsLinkedlist.h as template


---

#include <iostream>
#include <string.h>
#include <assert.h>
using namespace std;
// Stack as Linkedlist

template <class Type>
class Node{
    public:
        Type data;
        Node *link;
        Node *back;
        Node(int data){
            this->data = data;
            link = NULL;
            back = NULL;
        }
};

template<class Type>
class stackType
{
private:
     int stackTop; //variable to point to the top of the stack
     Node<Type> *newnode;
     Node<Type> *tail;
public:
    //Function to initialize the stack to an empty state.
    //Postcondition: stackTop = 0
    void initializeStack(){
        tail = NULL;         
        stackTop = 0;
    }
   
    //Function to determine whether the stack is empty.
    //Postcondition: Returns true if the stack is empty;
    // otherwise, returns false.
    bool isEmptyStack(){
        return (stackTop == 0);
    }
    //Function to remove all the elements from the stack.
    //Postcondition: stackTop = 0
    void destroyStack(){
        for(int i=0;i<stackTop;i++)
           pop();
        stackTop = 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 stack.
    void push(Type newItem){
                newnode = new Node<Type>(newItem);
                if(stackTop > 0){
                    tail->link = newnode;
                    newnode->back = tail;
                    tail = newnode;
                } 
                tail = newnode;
                stackTop++;
    }
   
    //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.
    Type top(){
        assert(stackTop!=0);    // if stackTop = 0 then exit program
        return tail->data;
    }
   
    //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.
    void pop(){
        if(isEmptyStack()){
            cout<<"Stack is Empty..."<<endl;
        }else{
                if(stackTop == 1){
                    Node<Type> *delnode;
                    delnode = tail;
                    tail = NULL;
                    delete delnode;
                }else{
                    tail = tail->back;
                    delete tail->link;
                    tail->link = NULL;
                }
            stackTop--;
        }
    }
     // number of stacks
    int Nstack(){
         return stackTop;
     }   
    //constructor
    stackType(){
        stackTop = 0;
        tail = NULL;
    }
 
    //destructor
    ~stackType(){
         destroyStack();
    }
};

---