数据结构-链式队列(用链表实现队列) 学习笔记_链表和链式队列

---

前言

视频连接：

懒猫老师-数据结构-(11)链式队列(用链表实现队列)
https://www.bilibili.com/video/av94576761

本人 看完懒猫老师教学视频后，写出来的代码，均实现相关功能
（自己测试是这样的 doge，如果有问题的话 记得B站@我 原罪Suntre CSDN可能不常在）

---

提示：以下是本篇文章正文内容，下面案例可供参考

1.链式队列函数模板源码分享

代码如下（示例）：

#ifndef LINKQUEUE_H
#define LINKQUEUE_H



template <class TypeDate>
class LinkQueue
{
    private:
        typedef struct Node{
            TypeDate date;      //数据域
            struct Node *next; //指针域
        }node,*Link;            //链表结构体
        Link Front,Rear; //头指针 和 尾部指针
        int length;     //队列元素个数
    public:
        LinkQueue();               //构造函数
        virtual ~LinkQueue();     //析构函数
        void enQueue(TypeDate x); //入队
        bool deQueue(TypeDate &item); //出队
        bool getFront(TypeDate &item); //获得队头元素
        bool isEmpty();           //判断是否为空
        void clearQueue();        //清空队列
        bool displayQueue();      //显示队列内容
        int  queueLength();       //获得队列元素个数

    protected:
};


template <class TypeDate>
LinkQueue<TypeDate>::LinkQueue()
{
    Front = new  node;  //分配内存 创建节点
    Front->next = nullptr;
    Rear = Front; //尾部指针  = 头部指针
    length = 0;   //长度 初始化为 0   有头节点的 链队
}

template <class TypeDate>
LinkQueue<TypeDate>::~LinkQueue()
{
    clearQueue(); //删除数据节点
    delete Front;//删除头节点
    delete Rear; //删除尾节点

}

template <class TypeDate>
void LinkQueue<TypeDate>::enQueue(TypeDate x)
{
    Link p;//新建node指针
    p = new node;//分配内存 创建节点
    p->date = x;  //数据装载
    p->next = nullptr; //空指针
    Rear->next = p;//当前末尾元素 next 指向 新加入的节点P
    Rear = p;      //Rear  指向 末尾节点
    length++;      //长度+1

}

template <class TypeDate>
bool LinkQueue<TypeDate>::deQueue(TypeDate &item)
{
    Link p;
    p = Front->next;  //指向头节点后一个

    if(isEmpty())   //判断是否为空队列
        return false;
    else
    {
        item = p->date;   //采用 引用的方式输出
        Front->next = p->next; // Front next域  指 p  的 next域的内容
        if(p->next == nullptr)// 节点关系Front  p(Front->next)  p->next
            Rear = Front; // Rear 指向 Front  当只有一个节点数据域
        delete p;  //删除p 节点
        length--;   //长度减少
        return true;
    }

}

template <class TypeDate>
bool LinkQueue<TypeDate>::getFront(TypeDate &item)
{
    Link p;
    p = Front->next;  //指向头节点后一个

    if(isEmpty())   //判断是否为空队列
        return false;
    else
    {
        item = p->date;   //指针方式输出  也可以采用 引用的方式输出  &item  item = p->date;
    }

}

template <class TypeDate>
bool LinkQueue<TypeDate>::isEmpty()
{
    return  (Front == Rear)&&(length ==0);

}

template <class TypeDate>
void LinkQueue<TypeDate>::clearQueue()
{
    Link p;
    p = Front->next;
    while( p != nullptr) //判断 Front->next 是否为空指针
    {
        Front->next = p->next;// Front next域  指 p  的 next域的内容
        delete p; //删除节点
        length--; //长度减1
        p = Front->next;
    }
    Rear = Front;  //结尾指针指向头部


}
template <class TypeDate>
bool LinkQueue<TypeDate>::displayQueue()
{
    Link p;
    p = Front->next;
    if(p == nullptr)
        return false;

    while( p != nullptr)
    {
        printf("%lf\n",p->date);// 测用的情况<double> date的情况  实际使用需要修改
        p = p->next;

    }
    return true;
}
template <class TypeDate>
int LinkQueue<TypeDate>::queueLength()
{
    return length;  //返回长度
}



#endif // LINKQUEUE_H

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

二、测试主函数 和 效果

1.主函数

#include <iostream>

using namespace std;
#include "LinkQueue.h"
int main()
{
    LinkQueue<double> a;

    a.enQueue(5);
    a.enQueue(6);
    a.enQueue(7);
    a.enQueue(8);
    a.displayQueue();
    cout << "长度" << a.queueLength() <<endl;

    double num =0;
    a.deQueue(num);
    cout << "出队" << num <<endl;

    cout << "长度" << a.queueLength() <<endl;

    cout << "列表为空吗" << a.isEmpty()<<endl;

    a.displayQueue();

    a.clearQueue();
     cout << "清除队列" << endl;
    if(a.displayQueue())
    {
    }
    else
    {
        cout << "列表为空" << endl;
    }

    cout << "列表为空吗" << a.isEmpty()<< endl;
    cout << "长度" << a.queueLength() <<endl;



    cout << "Hello world!" << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2.效果

总结

模板写下来 方便之后调用 省事，舒服。
接着准备 肝银行问题 qwq

感谢 懒猫老师的指导，感谢懒猫老师的优秀教学资源。