尾插头删
因此这里选择有头节点的链式队列
注意：在进行删除元素的过程中，当进行到最后一个节点的删除时，要将rear指回头结点，不然rear为也指针
因为删除完最后一个有效节点时，rear为野指针，并且按理rear应该指向队列的尾部，此时队列头尾重合，所以要把rear指向头结点
main.cpp
代码语言：javascript复制#include<iostream>
using namespace std;
#include"s.hpp"
//测试代码------------------------
void test()
{
linkQueue<int> q;
q.enlinkQueue(1);
q.enlinkQueue(2);
q.enlinkQueue(3);
cout << q.queueLen() << endl;
while (!q.isEmpty())
{
int temp = q.getTop();
cout << temp << endl;
q.delinkQueue();
}
q.clear();
cout << q.queueLen() << endl;
}
int main()
{
test();
system("pause");
return 0;
}linkQueue.hpp
代码语言：javascript复制#include<iostream>
using namespace std;
//节点结构体
template<class T>
struct node
{
T data;
node* next;
};
//队列类
template<class T>
class linkQueue {
private:
node<T>* front, *rear;//指向队列头结点，指向队列尾节点
int length; //元素个数
public:
//这里只需要默认无参构造，不需要有参构造
linkQueue()
{
//在堆区创建一个头结点
front = rear = new node<T>;
front->next = NULL;
length = 0;
}
~linkQueue()//释放队列空间
{
//头结点为空，就不进行释放
if (front == NULL)
{
return;
}
//如果不为空，就先释放除了子节点，再释放头节点
for (int i = 0; i < length; i )
{
//把每一个开辟在堆区的节点都进行释放，包括头节点
//相当于销毁链表
//用一个临时节点保存下一个要删除的节点
node<T>* temp;
temp = front;
front = front->next;
free(temp);
}
}
//入队---尾插
void enlinkQueue(T val)
{
//不用判断队列是否为满，因为是链式存储
//头插
node<T>* s = new node<T>;
s->data = val;
s->next = NULL;
rear->next = s;
rear = s;
length ;
}
//出队---头删
bool delinkQueue()
{
//队列为空，返回假
if (front == rear)
{
return false;
}
//进行头删
//提前保存下一个要删除的节点
node<T>* temp = front->next;
front->next = temp->next;
//判断删除的是否是最后一个节点，是的话把rear指向头结点
if (temp == rear)
{
rear = front;
}
free(temp);
length--;
return true;
}
//获取队头元素
T getTop()
{
return front->next->data;
}
//清空队列
void clear()
{
//清空除头结点以外的节点
node<T>* workNode;
workNode = front->next;
while (workNode)
{
//保存下一个要删除的节点
node<T>* nextNode = workNode;
workNode = workNode->next;
free(nextNode);
}
workNode = NULL;
//尾指针更新到头指针处
front->next = NULL;
rear = front;
length = 0;
}
int queueLen()
{
return length;
}
bool isEmpty()
{
if (length == 0)
return true;
return false;
}
};
