链接队列（Link Queue）——队列的链接实现

之前讨论的连续实现的队列结构（队列（Queue）——先进先出（FIFO）的数据结构（Data Structures））与连续栈结构存在着同样的缺点，即都需要大片连续的存储空间。而这个问题在队列结构里更加严重。解决的办法则与连续栈结构问题的办法一样：使用链接队列。链接队列实现除了不需要连续空间外，其所支持的操作类型和数量与连续队列完全一样。

连接队列的类定义与连续队列相比，数据成员为头尾两个指向Node结构的指针，这里的Node既可以是节点的定义，也可以死任意用户定义的结构。

下面是链接队列类定义。

//Link Queue in C++

typedef int QueueEntry;
const int success = 0;
const int overflow = 1;
const int underflow = 2;
const int failure = -1;
const int NULL = 0;

const int maxqueue = 100;										//队列的最大尺寸

struct Node														//链接队列的节点定义
{
	QueueEntry data;
	Node * next;
};

class Queue
{
public:
	Queue::Queue()												//构建函数，初始化一个空队列
	{
		head = tail = NULL;
	}

	bool Queue::empty() const									//检查队列是否为空
	{
		if (tail == NULL || head == NULL)
			return true;
		return false;
	}

	int Queue::append(const QueueEntry &item)					//将元素item插入队列队尾
	{
		Node*new_tail = new Node;
		if (new_tail == NULL)
			return overflow;
		else
		{
			new_tail->data = item;
			new_tail->next = NULL;
		}
		if (tail == NULL)
			head = tail = new_tail;
		else
		{
			tail->next = new_tail;
			tail = new_tail;
		}
		return success;
	}

	int Queue::serve()											//删除队头元素
	{
		if (head == NULL)
			return underflow;
		Node * old_head = head;
		head = old_head->next;
		if (head == NULL)
			tail = NULL;
		delete old_head;
		return success;
	}

	int Queue::retrieve(QueueEntry &item) const					//取出队头元素
	{
		if (head == NULL)
			return underflow;
		item = head->data;
		return success;
	}

	Queue::~Queue()												//构析函数
	{
		if (head != NULL)
		{
			if(head->next = NULL)
				delete head;
			else
			{
				Node *old_head = head;
				head = head->next;
				do {
					delete old_head;
					old_head = head;
					head = head->next;
				} while (head->next != NULL);
			}
		}
	}
	
protected:
	Node * head, * tail;
};