链式队列---c++版本

大忽悠爱学习

发布于 2021-03-11 11:10:16

3350

发布于 2021-03-11 11:10:16

文章被收录于专栏：c++与qt学习

尾插头删

因此这里选择有头节点的链式队列

注意：在进行删除元素的过程中，当进行到最后一个节点的删除时，要将rear指回头结点，不然rear为也指针

因为删除完最后一个有效节点时，rear为野指针，并且按理rear应该指向队列的尾部，此时队列头尾重合，所以要把rear指向头结点

main.cpp

#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

#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;
    }
};