linkedqueue.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef LINKEDQUEUE_H
#define LINKEDQUEUE_H
#include <iostream>
#include "LinkedList.h"
template <class T>
class LinkedQueue { //链式队列类定义
public:
	LinkedQueue() : rear(NULL),front(NULL) {} //构造函数, 建立空队列
	bool EnQueue(const T& x); //将x加入到队列中
	bool DeQueue(T& x); //删除队头元素,x返回其值
	bool getFront(T& x)const; //查看队头元素的值
	void makeEmpty(); //置空队列
	bool IsEmpty()const {return (front == NULL) ? true : false;}
	//判队列空否
	int getSize()const; //求队列元素个数
	void show();//输出
protected:
	LinkNode<T,T> *front, *rear; //队头、队尾指针
};
template <class T>
void LinkedQueue<T>::makeEmpty() {
	//置空队列，释放链表中所有结点。
	LinkNode<T,T> *p;
	while (front != NULL) { //逐个删除队列中的结点
		p = front; front = front->link; delete p;
	}
};
template <class T>
bool LinkedQueue<T>::EnQueue(const T& x) {
	//将新元素x插入到队列的队尾(链式队列的链尾)。
	if (front == NULL)
	{
		front = rear = new LinkNode<T,T>(x);
	//空队列时，新结点成为队列的第一个结点，既是队头又是队尾
	if (front == NULL) return false; //分配结点失败
	}
	else {
		rear->link = new LinkNode<T,T>(x);
		//非空队列时，在链尾追加新的结点并更新队尾指针
		if (rear->link == NULL) return false; //分配结点失败
		rear = rear->link;
	}
	return true;
};
template <class T>
bool LinkedQueue<T>::DeQueue(T& x) {
	//如果队列不为空，将队头结点从链式队列中删去，函数返回true，否则返回false。
	if (IsEmpty() == true) return false; //队列空则返回false
	LinkNode<T,T> *p = front; //队列不空，暂存队头结点
	x = front->data;
	front = front->link; delete p; //队头修改，释放原队头结点 124
	return true; //函数返回true
};
template <class T>
bool LinkedQueue<T>::getFront(T& x)const {
	//若队列不空，则函数返回队头元素的值及true。若队列空，则函数返回false。
	if (IsEmpty() == true) return false; //队列空则返回false
	x = front->data; //取队头元素中的数据值
	return true;
};
template <class T>
int LinkedQueue<T>::getSize()const {
	//求队列元素个数。
	LinkNode<T,T> *p = front; int k = 0;
	while (p != NULL) {p = p->link; k++;}
	return k;
};
template <class T>
void LinkedQueue<T>::show() {
	//输出队列中元素
	cout << "队列中元素个数有"<< getSize() << endl;
	LinkNode<T,T> *p = front; int i = 1;
	while (i<=getSize())
	{
		cout << i << " : " << p->data << endl;
		p = p->link;
        i++;
	}
};
#endif;