带你了解什么是链队列

链队列简介

队列是一种特殊的线性表，只允许在表前删除，而在表后插入。和栈一样，队列也是一个受限的线性表。插入操作的结束称为队列尾，删除操作的结束称为队列头。

在队列的形成过程中，可以利用线性链表的原理来生成队列。基于链表的队列动态创建和删除节点效率低下，但它们可以动态增长。队列中使用FIFO(先进先出)。新元素(等待进入队列的元素)总是插入到列表的末尾，并从列表的头部读取。一次读取一个元素，一次释放一个元素。所谓动态创建，动态发布。因此，不存在溢出问题。因为链表是由结构间接形成的，所以也方便遍​​历。

1.入场操作

添加队列末尾元素，先将队列末尾的下一个元素指向添加的元素，然后再次将指针指向队列的新末尾。

2. 脱机操作

头节点指向队尾，操作是杀队尾，先指向新队尾(即旧队尾的继任者)，然后释放旧队尾团队结束。如果列表中除头节点外只有一个元素，则需要将尾部指向头节点。

链式队列的代码实现

1.链式队列的实现

#ifndef QUEUELI_H
#define QUEUELI_H
template<class T>
class Queue
{
public:
	Queue();
	~Queue();
	bool isEmpty() const;
	const T& getFront() const;
	void enqueue(const T& x);
	T dequeue();
	void MakeEmpty();
private:
	struct ListNode
	{
		T element;
		ListNode *next;
		ListNode(const T& theElement, ListNode *n=0)
			:element(theElement),next(n) {}
	};
	ListNode *front;
	ListNode *back;
};
template<class T>
const T& Queue<T>::getFront() const
{
	if (isEmpty())
		throw"Queue is empty.";
		return front->element;
}
template<class T>
Queue<T>::Queue()
{
	front = back = 0;
}
template<class T>
Queue<T>::~Queue()
{
	MakeEmpty();
}
template<class T>
bool Queue<T> ::isEmpty() const
{
	return front == 0;
}
template <class T>
void Queue<T>::enqueue(const T& x)
{
	if (isEmpty())
		back = front = new ListNode(x);
	else
		back = back->next = new ListNode(x);	
}
template<class T>
T Queue<T> ::dequeue()
{
	T frontItem = getFront();
	ListNode *old = front;
	front = front->next;
	delete old;
	return frontItem;
}
template <class T>
void Queue<T>::MakeEmpty()
{
	while (!isEmpty())
		dequeue();
}
#endif

2. 测试链队列

#include<iostream> 
#include"QueueLi.h" 
using namespace std; 
int main() 
{ 
	Queue<int> myQ; 
	myQ.enqueue(10); 
	myQ.enqueue(20); 
	myQ.enqueue(20); 
	cout << myQ.getFront() << endl; 
	myQ.dequeue(); 
	cout << myQ.dequeue() << endl; 
	cout << myQ.dequeue() << endl; 
	for (int j = 0; j < 8; j++) 
	{ 
		for (int i = 0; i < 8; i++) 
			myQ.enqueue(i); 
		while (!myQ.isEmpty()) 
			cout << myQ.dequeue() << endl; 
	} 
}

大家如果对此感兴趣，想了解更多相关知识，不妨来关注一下星辉的Java队列教程，里面的内容丰富，通俗易懂，适合没有基础的小白学习，希望对大家能够有所帮助。