链式队列的实现

原文地址：https://wanqbin.xyz/2019/03/31/链式队列的实现-1/

写在前面

  链式队列是队列的链式存储结构表示。队列是操作受限的表，队列有队头和队尾，插入元素的一端称为队尾，删除元素的一端称为队头。这和一般排队的概念一样，后来的人排在队尾，首先对队头的人进行服务，对队头的人服务后，原当前队头后的人就排在了当前队头。新来的人排在队尾后，原队尾的人就不再是当前队尾了，新来的人就成了当前队尾。
  链式队列的队头指针指在队列的当前队头节点位置，队尾指针指在队列的当前队尾节点位置。不带头节点的链式队列，出队列时可直接删除头指针所指的节点，因此，链式队列不带头指针时更加方便。

1.链式队列节点类的定义和实现

template<class T>
class LinkQueue;

template<class T>
class QueueNode
{
	friend class LinkQueue<T>;
public:
	T data;
	QueueNode<T>(const T& item, QueueNode<T> *ptrNext = NULL);
	~QueueNode() {};

private:
	QueueNode<T> *next;
};

template<class T>
inline QueueNode<T>::QueueNode(const T & item, QueueNode<T>* ptrNext)
{
	this->data = item;
	this->next = ptrNext;
}

2.链式队列类的定义

template<class T>
class LinkQueue
{
public:
	LinkQueue();//构造函数
	~LinkQueue();//析构函数

	void insert(const T& item);//入队
	T delet();//出队
	T readFront() const;//读队头元素
	bool empty() const;//判断队列是否为空
	void clearQueue();//清空队列
	int getSize() const;//取队列长度
	void display() const;//输出队列元素

private:
	QueueNode<T> *front;//指向队头的指针
	QueueNode<T> *rear;//指向队尾的指针
	int size;
};

3.链式队列类的实现

template<class T>
inline LinkQueue<T>::LinkQueue()
{
	size = 0;
	front = rear = NULL;
}

template<class T>
inline LinkQueue<T>::~LinkQueue()
{
	clearQueue();
	front = rear = NULL;
}

template<class T>
inline void LinkQueue<T>::insert(const T & item)
{
	QueueNode<T> *new_node = new QueueNode<T>(item);
	if (rear != NULL)
	{
		rear->next = new_node;
	}
	rear = new_node;
	if (front == NULL)
	{
		front = new_node;
	}
	size++;
}

template<class T>
inline T LinkQueue<T>::delet()
{
	if (size == 0)
	{
		cout << "Queue is empty" << endl;
		exit(1);
	}
	T member = front->data;
	QueueNode<T> *p = front->next;
	delete front;
	front = p;
	size--;
	return member;
}

template<class T>
inline T LinkQueue<T>::readFront() const
{
	return front->data;
}

template<class T>
inline bool LinkQueue<T>::empty() const
{
	return (size==0);
}

template<class T>
inline void LinkQueue<T>::clearQueue()
{
	QueueNode<T> *p1, *p2;
	p1 = front;
	while (p1 != NULL)
	{
		p2 = p1;
		p1 = p1->next;
		delete p2;
	}
	size = 0;
}

template<class T>
inline int LinkQueue<T>::getSize() const
{
	return size;
}

template<class T>
inline void LinkQueue<T>::display() const
{
	QueueNode<T> *p = front;
	int i = 0;
	while (p != NULL)
	{
		cout << "第" << i << "号元素为：" << p->data << endl;
		i++;
		p = p->next;
	}
}

4.测试主函数

void test()
{
	LinkQueue<int> queue;
	for (int i = 0; i < 10; i++)
	{
		queue.insert(i * 10);
	}
	cout << "队列长度为：" << queue.getSize() << endl;
	queue.display();
	cout << "栈顶元素为：" << queue.readFront() << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << "元素：" << queue.delet() << "被删除" << endl;
	}
	cout << "队列长度为：" << queue.getSize() << endl;
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}void test()
{
	LinkQueue<int> queue;
	for (int i = 0; i < 10; i++)
	{
		queue.insert(i * 10);
	}
	cout << "队列长度为：" << queue.getSize() << endl;
	queue.display();
	cout << "栈顶元素为：" << queue.readFront() << endl;
	for (int i = 0; i < 10; i++)
	{
		cout << "元素：" << queue.delet() << "被删除" << endl;
	}
	cout << "队列长度为：" << queue.getSize() << endl;
}

int main()
{
	test();
	system("pause");
	return EXIT_SUCCESS;
}

输出结果如下：
[外链图片转存失败(img-05sgyqAN-1565276338751)(https://i.imgur.com/NmtLrOb.png)]