#include <iostream>
using namespace std;

template<typename T>
class Node
{
public:
    Node(T t):data(t), next(NULL){};
    T getdata() {return data;};
    Node<T> *next;       // The client program (list) needs to maintain the link, 
						 //so public.
private:
    T data;              // We don't want the data to be changed directly. 
};

///////////////////////////////////////////////////////////////////
//////////// Stack Class Template   ///////////////////////////////
///////////////////////////////////////////////////////////////////
template<typename T>
class Stack
{
public:
	Stack();
	Stack(Stack<T> & st); // Important!!
	void push(T data); 
	T pop();
	bool isempty();
	~Stack();  // Delete every node in the list.
	friend Node<T> *peek_top(Stack<T> & s);  // This is not a good idea. 
private:
	Node<T> *top;
};


template<typename T>
Stack<T>::Stack()     // Can't go like Stack::Stack()
:top(NULL) {}

template<typename T>               // Copy constructor
Stack<T>::Stack(Stack<T> & st)     // Need & st
{
	if (st.top == NULL) 
	{
		top=NULL;
		return;
	}
	Node<T> *cur, *next, *new_node;
	cur = new Node<T>((st.top)->getdata());
	next=cur->next=(st.top)->next;
	top = cur;
	while (next != NULL)
	{
		new_node = new Node<T>(next->getdata());
		next=new_node->next=next->next;
		cur->next=new_node;
		cur=new_node;
	}
}

template<typename T>
void Stack<T>::push(T data)   
{
	Node<T> *new_node; 
	new_node = new Node<T>(data);
	new_node->next = top;
	top = new_node;
}

template<typename T>
T Stack<T>::pop()   
{
	T data;
	if (top==NULL) return data;
	Node<T> *node=top;
	data=top->getdata();
	top = top->next;
	delete node;
	return data;
}


template<typename T>
bool Stack<T>::isempty()   
{
	return (top==NULL);
}

template<typename T>
Stack<T>::~Stack()     // Destructor
{
	while (top!=NULL) pop();
}

template<typename T>
Node<T> *peek_top(Stack<T> & s)   
{
	return s.top;
}

///////////////////////////////////////////////////////////////////
//////////// Queue Class Template   ///////////////////////////////
///////////////////////////////////////////////////////////////////
template<typename T>
class Queue
{
public:
	Queue();
	Queue(Queue<T> & st); // Copy Constructor
	void push(T data); 
	T pop();
	bool isempty();
	~Queue();  // Delete every node in the list.
private:
	Node<T> *head, *tail;
};


template<typename T>
Queue<T>::Queue()     
:head(NULL), tail(NULL){}

template<typename T>               // Copy constructor
Queue<T>::Queue(Queue<T> & st)     // Need & st
{
	if (st.head == NULL) 
	{
		head=tail=NULL;
		return;
	}
	Node<T> *cur, *next, *new_node;
	cur = new Node<T>((st.head)->getdata());
	next=cur->next=(st.head)->next;
	head = tail = cur;
	while (next != NULL)
	{
		new_node = new Node<T>(next->getdata());
		next = new_node->next = next->next;
		tail = cur = cur->next = new_node;
	}
}

template<typename T>
void Queue<T>::push(T data)   
{
	Node<T> *new_node; 
	new_node = new Node<T>(data);
	new_node->next = head;
	head = new_node;
	if (tail == NULL)
		tail = head; 
}



template<typename T>
T Queue<T>::pop()   
{
	T data;
	if (head==NULL) return data;

	Node<T> *new_tail=head;   // The node before tail
	
	if (head == tail) 
		head = new_tail = NULL; // No node before tail
	else /// has more than one node;
		while (new_tail->next != tail)
			new_tail = new_tail->next;
	
	data = tail->getdata();
	delete tail;
	tail = new_tail;
	return data;
}


template<typename T>
bool Queue<T>::isempty()   
{
	return (head==NULL);
}

template<typename T>
Queue<T>::~Queue()     // Destructor
{
	while (head!=NULL) pop();
}