#ifndef _STACK_H
#define _STACK_H

#include <iostream>
#include <cstdlib>
using namespace std;

template<class T>
class stack
{
private:
struct node
{
T data;
node * next;
};

typedef node * ptr;

ptr top;
int size;

public :

stack();
//constructor : creats an empty stack

stack(const stack & x);
// copy constructor

~stack();
//destructor

void push(const T & x);
// precondition : none
//postcondition : x is top item on the stack
// size of the stack it incremented

T pop();
//precondition : stack is not empty
//postcondition : top item is removed
//returns : top item

bool isempty() const;
//precondition : none
//postcondition : none
//Returns : true if no item are on the stack

int getsize() const;
//precondition : none
//postconditione : none
//Returns the number of items on the stack

T stacktop() const;
//precondition : stack is not empty
//postcondition : none
//returns top item on stack

};

template <class T>
stack<T>::stack()
{
top = NULL;
size = 0;
}

template <class T>
stack<T>::stack(const stack & x)
{

    ptr p = x.top;;
    ptr q = NULL;
    ptr r = NULL;

    size = x.size;
    top = NULL;


    for (int i = 1; i <= size; i++)
    {
        q = new node;
        q -> next = NULL;
        q->data = p->data;
        if (top == NULL)
            top = q;
        else
            r -> next = q;
        r = q;
        p = p-> next;

    }
}

template <class T>
stack<T>::~stack()
{
    int count = size;
    for (int i = 1; i <= count; i++)
    pop();
 }

template <class T>
void stack<T>::push(const T & x)
{
    ptr p = new node;
    p->data = x;
    p-> next = top;
    top = p;
    size++;
}

template <class T>
T stack<T>::pop()
{
    if (top == NULL)
    {
        cout<<"Error : stack underflow ";
        exit(1);
    }

    ptr p = top;
    top = top -> next;
    T x = p ->data;
    size--;
    delete p;
    return x;
}

template <class T>
bool stack<T>::isempty() const
{
    return top == NULL;
}

template <class T>
int stack<T>::getsize() const
{
    return size;
}

template <class T>
T stack<T>::stacktop() const
{
    if (top == NULL)
    {
            cout<<"Error : stack underflow ";
            exit(1);
    }
    return top -> data;
}
#endif