#include <iostream>
#include <cstdlib>
using namespace std;
#ifndef _QUEUE_H
#define _QUEUE_H

template <class T>
class Queue
{
    protected :
        struct node
        {
            T data;
            node * next;
        };
        typedef node * ptr;

        ptr first;
        ptr last ;
        int size;

    public:

Queue();
// default constructor
//Postcondition : The queue is initialized to empty
Queue(const Queue<T> & x);
//copy constructor

~Queue();
//destructor

bool empty() const;
//Precondition : none
// Postcondition : none
// Returns true if queue is empty

void insert (const T & x);
// Precondition : Queue is not full
// Postcondition : item x is added to rear of queue

T remove();
// Precondition : queue is not empty
// Postcondition : first item is removed ffrom queue
// Returns : first item in queue

int getsize();
// Precondition : none
// Post condition returns size of queue

T front() const;
//precondition Queue is not empty
//postcondition: returns first item -- queue is unchanged

};

//implementation

// default constructor
template <class T>
Queue<T>::Queue():first(NULL), last(NULL), size(0)
{
}

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

    first = NULL;
    last = NULL;
    T temp;

    ptr p = x.first;
    for (int i = 1; i <= x.size; i++)
    {
        temp = p->data;
        insert(temp);
        p = p-> next;
    }
    size = x.size;
}

template <class T>
Queue<T>::~Queue()
{
// free all dynamic memory
    for (int i = 1; i <= size ; i++)
    {
        ptr p = first;
        first = first -> next;
        delete p;
    }
}

template <class T>
void Queue<T>::insert(const T& x)
{
    ptr p = new node;
    p -> data = x;
    p-> next = NULL;
    if (last == NULL) // Queue was empty
        first = last = p;
    else
    {
        last -> next = p;
    last = p;
    }
    size++;
}

template <class T>
T Queue<T>::remove()
{
    if (first == NULL)
    {
        cout<< "Queue underflow - remove";
        exit(1);
    }
    ptr p = first;
    T temp = p->data;
    first = first -> next;
    if (first == NULL) // Queue becomes empty
        last = NULL;
    delete p;
    size--;
    return temp;
}

template <class T>
T Queue<T>::front() const
{
    if (first == NULL)
    {
        cout<< "Queue underflow - front";
        exit(1);
    }
    return first -> data;
}

template <class T>
bool Queue<T>::empty() const
{
    return (first == NULL);
}

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

#endif