linkedqueue.h

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

//:LinkedQueue.h
#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H

#include <iostream>

template<class T> class LinkedQueue;

template<class T>
class Node{
	T data;
	Node<T>* next;
public:
	friend class LinkedQueue<T>;
};

class OutOfBounds{
public:
	OutOfBounds() {}
};

template<class T>
class LinkedQueue{
	Node<T>* front;
	Node<T>* rear;
public:
	LinkedQueue() { front = rear = 0; }
	~LinkedQueue();
	bool isEmpty() const { return (front ? false : true); }
	T first() const;
	T last() const;
	LinkedQueue<T>& add(const T& x);
	LinkedQueue<T>& Delete(T& x);
	void output(std::ostream& out) const;
};

template<class T>
LinkedQueue<T>::~LinkedQueue()
{
	Node<T>* link;

	while(front)
	{
		link = front->next;
		delete front;
		front = link;
	}
}

template<class T>
T LinkedQueue<T>::first() const
{
	if(!front)
		throw OutOfBounds();

	return front->data;
}

template<class T>
T LinkedQueue<T>::last() const
{
	if(!rear)
		throw OutOfBounds();

	return rear->data;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::add(const T& x)
{
	Node<T>* link = new Node<T>;
	link->data = x;
	link->next = 0;

	if(front)
	{
		rear->next = link;
		rear = link;
	}
	else
		front = rear = link;

	return *this;
}

template<class T>
LinkedQueue<T>& LinkedQueue<T>::Delete(T& x)
{
	if(!front)
		throw OutOfBounds();

	Node<T>* link = front->next;
	x = front->data;
	delete front;
	front = link;

	return *this;
}

template<class T>
void LinkedQueue<T>::output(std::ostream& out) const
{
	if(!front)
		out << "The queue is empty!";
	else
	{
		Node<T>* link = front;
		out << "The queue is: " << std::endl;

		while(link)
		{
			out << link->data << " ";
			link = link->next;
		}
	}
}

template<class T>
std::ostream& operator<<(std::ostream& out, const LinkedQueue<T>& q)
{
	q.output(out);

	return out;
}

#endif //LINKEDQUEUE_H
///:~