linkedstack.h

用C++写的寻找公共祖先

//:LinkedStack.h
#ifndef LINKEDSTACK_H
#define LINKEDSTACK_H

#include <iostream>
#include <sstream>
#include <string>

template<class T> class LinkedStack;

template<class T>
class StackNode{
	T data;
	StackNode<T>* next;
	friend class LinkedStack<T>;
};

template<class T>
class LinkedStack{
	StackNode<T>* top;
public:
	LinkedStack() { top = 0; }
	LinkedStack(const LinkedStack<T>& c);
	~LinkedStack() { erase(); }
	void erase();
	bool isEmpty() const { return top == 0; }
	bool isFull() const;
	T getTop() const;
	int getLength() const;
	LinkedStack<T>& add(const T& x);
	LinkedStack<T>& Delete(T& x);
	LinkedStack<T>& operator=(const LinkedStack<T>& c);
};

template<class T>
LinkedStack<T>::LinkedStack(const LinkedStack<T>& c)
{
	top = 0;

	if(!c.isEmpty())
	{	
		StackNode<T>* link = c.top;
		StackNode<T>* p = new StackNode<T>;
		p->data = link->data;
		p->next = 0;
		top = p;
		link = link->next;

		while(link)
		{
			StackNode<T>* StackNode = new StackNode<T>;
			StackNode->data = link->data;
			StackNode->next = 0;
			p->next = StackNode;
			p = StackNode;
			link = link->next;
		}
	}
}

template<class T>
void LinkedStack<T>::erase()
{
	StackNode<T>* next;

	while(top)
	{
		next = top->next;
		delete top;
		top = next;
	}
}

template<class T>
bool LinkedStack<T>::isFull() const
{
	try{
		StackNode<T>* p = new StackNode<T>;
		delete p;
		return false;
	} catch(...) {
		return true;
	}
}

template<class T>
T LinkedStack<T>::getTop() const
{
	if(isEmpty())
		throw OutOfBounds();

	return top->data;
}

template<class T>
int LinkedStack<T>::getLength() const
{
	StackNode<T>* next = top;
	int length = 0;

	while(next)
	{
		length++;
		next = next->next;
	}

	return length;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::add(const T& x)
{
	StackNode<T>* p = new StackNode<T>;
	p->data = x;
	p->next = top;
	top = p;

	return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{
	if(isEmpty())
		throw OutOfBounds();

	StackNode<T>* p = top->next;
	x = top->data;
	delete top;
	top = p;

	return *this;
}

template<class T>
LinkedStack<T>& LinkedStack<T>::operator=(const LinkedStack<T>& c)
{
	if(top)
		erase();

	if(!c.isEmpty())
	{	
		StackNode<T>* link = c.top;
		StackNode<T>* p = new StackNode<T>;
		p->data = link->data;
		p->next = 0;
		top = p;
		link = link->next;

		while(link)
		{
			StackNode<T>* StackNode = new StackNode<T>;
			StackNode->data = link->data;
			StackNode->next = 0;
			p->next = StackNode;
			p = StackNode;
			link = link->next;
		}
	}

	return *this;
}

template<class T>
std::ostream operator<<(std::ostream& out, const LinkedStack<T>& c)
{
	LinkedStack<T> m = c;
	T x;

	while(!m.isEmpty())
	{
		m.Delete(x);
		out << x << "->";
	}
	
	out << "NULL";

	return out;
}

template<class T>
std::istream operator>>(std::istream& in, LinkedStack<T>& c)
{
	std::string s;
	getline(in, s);
	std::istringstream is(s);
	int x;

	while(is >> x)
		c.add(x);

	return in;
}

#endif //LINKEDSTACK_H
///:~