链式队列(Linked Queue)

作者：小小林熬夜学编程 | 2024-06-11 01:12:34

踩

链式队列

链式队列(Linked Queue)

1. 链式队列的概念

1.1 链式队列的定义

链式队列是基于单链表的存储表示实现的队列。

1.2 链式队列中各元素的逻辑及存储关系

链式队列可以采用单链表作为其存储表示，因此，可以在链式队列的声明中用单链表定义它的存储空间。
链式队列的队头指针指向单链表的第一个结点，队尾指针指向单链表的最后一个结点。
注：链式队列的队头元素存放在单链表的第一个结点内，若要从队列中退出一个元素，必须从单链表中删去第一个结点，而存放着新元素的结点应插在队列的队尾，即单链表的最后一个结点后面，这个新节点将成为新的队尾。

1.3 链式队列的特点

用单链表表示的链式队列特别适合于数据元素变动比较大的情况，而且不存在队列满而产生溢出的情况。
若程序中要使用多个队列，与多个栈的情形一样，用链接表示不仅能够提高效率，还可以达到共享存储空间的目的。
使用链式队列不会出现存储分配不合理的问题，也不需要进行存储的移动，

2. 链式队列的实现

2.1 链表结点结构的定义

文件：LinkNode.h


#ifndef LINK_NODE_H_


#define LINK_NODE_H_



#include <iostream>


#include <string>


#include <strstream>


using namespace std;

template <class T>
struct LinkNode         //链表结点类的定义
{
    T data;             //数据域
    LinkNode<T> *link;  //指针域——后继指针
    //仅初始化指针成员的构造函数
    LinkNode(LinkNode<T>* ptr = NULL){ link = ptr; }
    //初始化数据与指针成员的构造函数
    LinkNode(const T& value, LinkNode<T>* ptr = NULL){ data = value; link = ptr; }
};


#endif /* LINK_NODE_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

2.2 链式队列的类定义及其操作的实现

文件：LinkedQueue.h


#ifndef LINKED_QUEUE_H_


#define LINKED_QUEUE_H_



#include "LinkNode.h"


#include "Queue.h"


template <class T>
class LinkedQueue : public Queue<T>
{
public:
    LinkedQueue();                      //构造函数
    virtual ~LinkedQueue();                //析构函数
public:
    virtual bool getHead(T& x) const;       //读取队头元素，并将该元素的值保存至x
    virtual bool EnQueue(const T& x);       //新元素x入队
    virtual bool DeQueue(T& x);             //队头元素出队，并将该元素的值保存至x    
    virtual bool IsEmpty() const;           //判断队列是否为空
    virtual bool IsFull() const;            //判断队列是否为满
    virtual void MakeEmpty();               //清空队列的内容
    virtual int getSize() const;            //计算队列中元素个数
public:
    template <class T>
    friend ostream& operator<<(ostream& os, const LinkedQueue<T>& q);   //输出队列中元素的重载操作<<
private:
    LinkNode<T> *front; //队头指针，即链头指针
    LinkNode<T> *rear;  //队尾指针，即链尾指针
};

//构造函数
template <class T>
LinkedQueue<T>::LinkedQueue()
: front(NULL), rear(NULL)
{
    cout << "$ 执行构造函数" << endl;
}                       

//析构函数
template <class T>
LinkedQueue<T>::~LinkedQueue()
{
    cout << "$ 执行析构函数" << endl;
    MakeEmpty();
}   

//读取队头元素，并将该元素的值保存至x
template <class T>
bool LinkedQueue<T>::getHead(T& x) const
{
    if (true == IsEmpty())
    {
        return false;
    }
    x = front->data;
    return true;
}

//新元素x入队
template <class T>
bool LinkedQueue<T>::EnQueue(const T& x)
{
    LinkNode<T> *newNode = new LinkNode<T>(x);
    if (NULL == newNode)
    {
        return false;
    }

    if (NULL == front)
    {
        front = newNode;
        rear = newNode;
    }
    else
    {
        rear->link = newNode;
        rear = rear->link;
    }
    return true;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
bool LinkedQueue<T>::DeQueue(T& x)
{
    if (true == IsEmpty())
    {
        return false;
    }
    LinkNode<T> *curNode = front;
    front = front->link;
    x = curNode->data;
    delete curNode;
    return true;
}

//判断队列是否为空
template <class T>
bool LinkedQueue<T>::IsEmpty() const
{
    return (NULL == front) ? true : false;
}

//判断队列是否为满
template <class T>
bool LinkedQueue<T>::IsFull() const
{
    return false;
}

//清空队列的内容
template <class T>
void LinkedQueue<T>::MakeEmpty()
{
    LinkNode<T> *curNode = NULL;
    while (NULL != front)           //当链表不为空时，删去链表中所有结点
    {
        curNode = front;            //保存被删结点
        front = curNode->link;      //被删结点的下一个结点成为头结点
        delete curNode;             //从链表上摘下被删结点
    }
}

//计算队列中元素个数
template <class T>
int LinkedQueue<T>::getSize() const
{
    int count = 0;
    LinkNode<T> *curNode = front;
    while (NULL != curNode)
    {
        curNode = curNode->link;
        count++;
    }
    return count;
}

//输出队列中元素的重载操作<<
template <class T>
ostream& operator<<(ostream& os, const LinkedQueue<T>& q)
{
    int i = 0;
    LinkNode<T> *curNode = q.front;
    while (NULL != curNode)
    {
        os << "[" << i++ << "]" << " : " << curNode->data << endl;
        curNode = curNode->link;
    }
    return os;
}


#endif /* LINKED_QUEUE_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
147
148
149
150
151
152
153
154
155
156
157
158
159
160

2.3 主函数(main函数)的实现

文件：main.cpp


#include "LinkedQueue.h"



#define EXIT 0              //退出


#define GETHEAD 1           //读取队头元素，并将该元素的值保存至x


#define ENQUEUE 2           //新元素x入队


#define DEQUEUE  3          //队头元素出队，并将该元素的值保存至x


#define ISEMPTY  4          //判断队列是否为空


#define ISFULL 5            //判断队列是否为满


#define MAKEEMPTY 6         //清空队列的内容


#define GETSIZE 7           //计算队列中元素个数


#define OPERATOR_OSTREAM 8  //输出队列元素的重载操作<<


void print_description()
{
    cout << "------------------------------>链式队列<------------------------------" << endl;
    cout << "功能选项说明：" << endl;
    cout << "#0： 退出" << endl;
    cout << "#1： 读取队头元素，并将该元素的值保存至x" << endl;
    cout << "#2： 新元素x入队" << endl;
    cout << "#3： 队头元素出队，并将该元素的值保存至x" << endl;   
    cout << "#4： 判断队列是否为空" << endl;
    cout << "#5： 判断队列是否为满" << endl;
    cout << "#6： 清空队列的内容" << endl;
    cout << "#7： 计算队列中元素个数" << endl;
    cout << "#8： 输出队列元素的重载操作<<" << endl;
    cout << "--------------------------------------------------------------------" << endl;
}

//判断输入的字符串每个字符是否都是数值0~9
bool IsNumber(const string& s_num)
{
    for (size_t i = 0; i < s_num.size(); i++)
    {
        if ((s_num[i] < '0') || (s_num[i] > '9'))
        {
            return false;
        }
    }
    return true;
}

//类型转换——将string型转为模板类型T
template <class T>
T StrToTtype(const string& s_num)
{
    T n_num;
    strstream ss_num;
    ss_num << s_num;
    ss_num >> n_num;
    return n_num;
}

//输入数据值
template <class T>
T get_data()
{
    cout << "> 请输入数据值，data = ";
    string s_data;
    cin >> s_data;
    return StrToTtype<T>(s_data);
}

//构造链式队列
template <class T>
LinkedQueue<T>* construct_linkedqueue()
{
    cout << "\n==> 创建链式队列" << endl;
    LinkedQueue<T> *linkedQueue = new LinkedQueue<T>;
    return linkedQueue;
}

//析构链式队列
template <class T>
void destory_linkedqueue(LinkedQueue<T>* linkedQueue)
{
    cout << "\n==> 释放链式队列在堆中申请的空间，并将指向该空间的指针变量置为空" << endl;
    delete linkedQueue;
    linkedQueue = NULL;
}

//读取队头元素，并将该元素的值保存至x
template <class T>
void gethead(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行读取队头元素并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedQueue->getHead(data))
    {
        cout << "* 读取队头元素失败" << endl;
        return;
    }
    cout << "* 读取队头元素成功，data = " << data << endl;
}

//新元素x入队
template <class T>
void enqueue(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行新元素x入队函数" << endl;
    T data = get_data<T>();
    if (false == linkedQueue->EnQueue(data))
    {
        cout << "* 入队失败" << endl;
        return;
    }
    cout << "* 入队成功，data = " << data << endl;
}

//队头元素出队，并将该元素的值保存至x
template <class T>
void dequeue(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行队头元素出队并将该元素的值保存至x函数" << endl;
    T data;
    if (false == linkedQueue->DeQueue(data))
    {
        cout << "* 出队失败" << endl;
        return;
    }
    cout << "* 出队成功，data = " << data << endl;
}

//判断队列是否为空
template <class T>
void isempty(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行判断队列是否为空函数，IsEmpty = " << linkedQueue->IsEmpty() << endl;
}

//判断队列是否为满
template <class T>
void isfull(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行判断队列是否为满函数，IsFull = " << linkedQueue->IsFull() << endl;
}

//清空队列的内容
template <class T>
void makeempty(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行清空队列的内容函数" << endl;
    linkedQueue->MakeEmpty();
}

//计算队列中元素个数
template <class T>
void getsize(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行计算队列中元素个数函数，Size = " << linkedQueue->getSize() << endl;
}

//输出队列元素的重载操作<<
template <class T>
void operator_ostream(LinkedQueue<T>* linkedQueue)
{
    cout << "$ 执行输出队列元素的重载操作<<函数" << endl;
    cout << *linkedQueue;//或operator<<(cout, *linkedQueue);
}

//链式队列操作选择
template <class T>
void select_operation(LinkedQueue<T>* linkedQueue)
{
    if (NULL == linkedQueue)
    {
        cout << "* 没有构造链式队列，请先构造链式队列。" << endl;
        return;
    }

    string s_operation;
    while (s_operation != "0")
    {
        cout << "\n==> 请输入功能选项编号(按\"0\"退出程序)：";
        cin >> s_operation;
        while (false == IsNumber(s_operation))
        {
            cout << "* 输入有误，请重新输入：";
            cin >> s_operation;
        }
        int n_operation = atoi(s_operation.c_str());
        switch (n_operation)
        {
            case EXIT://退出
            {
                cout << "$ 退出程序" << endl;
                break;
            }
            case GETHEAD://读取队头元素，并将该元素的值保存至x
            {
                gethead(linkedQueue);
                break;
            }
            case ENQUEUE://新元素x入队
            {
                enqueue(linkedQueue);
                break;
            }
            case DEQUEUE://队头元素出队，并将该元素的值保存至x
            {
                dequeue(linkedQueue);
                break;
            }
            case ISEMPTY://判断队列是否为空
            {
                isempty(linkedQueue);
                break;
            }
            case ISFULL://判断队列是否为满
            {
                isfull(linkedQueue);
                break;
            }
            case MAKEEMPTY://清空队列的内容
            {
                makeempty(linkedQueue);
                break;
            }
            case GETSIZE://计算队列元素个数
            {
                getsize(linkedQueue);
                break;
            }
            case OPERATOR_OSTREAM://输出队列元素的重载操作<<
            {
                operator_ostream(linkedQueue);
                break;
            }
            default:
            {
                cout << "* 请输入正确的功能选项编号" << endl;
                break;
            }
        }
    }
}

int main(int argc, char* argv[])
{
    print_description();
    LinkedQueue<int> *linkedQueue = construct_linkedqueue<int>();
    select_operation(linkedQueue);
    destory_linkedqueue(linkedQueue);
    system("pause");
    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
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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265

参考文献：
[1]《数据结构(用面向对象方法与C++语言描述)(第2版)》殷人昆——第三章
[2]《C/C++常用算法手册》秦姣华、向旭宇——第二章
[3] 百度搜索关键字：链式队列

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/701102