第94篇 C++数据结构（四）队列_线程队列保存字符

1.队列简介

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

1.队列的存储结构

（1）数组：队列的顺序实现是指分配一块连续的存储单元存放队列中的元素，并附设两个指针：队头指针 front指向队头元素，队尾指针 rear 指向队尾元素的下一个位置。
（2）链表：队列的链式存储结构表示为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表，只不过它只能尾进头出而已。

2.节点

链式存储个人感觉比较方便，实现的也是链式存储方式，再次定义节点。

template <typename _dataType>
struct QueueNode
{
	using _QueueNodePtr = QueueNode*;

	_dataType m_value;
	_QueueNodePtr m_next;

	QueueNode() : m_value(_dataType()), m_next(nullptr) {}
	QueueNode(_dataType value) : m_value(value), m_next(nullptr) {}
	QueueNode(_dataType value, _QueueNodePtr next) : m_value(value), m_next(next) {}
};
1
2
3
4
5
6
7
8
9
10
11
12

3.实现

3.1.变量

3.2.方法

4.测试

4.1.测试代码

#include <iostream>

#include "Queue.h"

void queueTest();

int main()
{
	queueTest();

	return 0;
}

void queueTest()
{
	std::cout << "\n构造：" << std::endl;
	Queue<int> q;

	std::cout << "\n数据个数：" << q.size() << std::endl;

	std::cout << "\nempty:" << std::endl;
	if (q.empty()) {
		std::cout << "q is empty!" << std::endl;
	}
	else {
		std::cout << "q isn't empty!" << std::endl;
	}

	std::cout << "\npush（7）" << std::endl;
	q.push(7);
	std::cout << "\n数据个数：" << q.size() << std::endl;
	std::cout << "front = " << q.front() << std::endl;

	std::cout << "\npush:1,2,3,4,5,6" << std::endl;
	int num = 1;
	while (num < 7) {
		q.push(num++);
	}
	std::cout << "\n数据个数：" << q.size() << std::endl;
	std::cout << "front = " << q.front() << std::endl;

	Queue<int> qt = q;
	while (!qt.empty()) {
		std::cout << qt.front() << ", ";
		qt.pop();
	}

	std::cout << "\nempty:" << std::endl;
	if (q.empty()) {
		std::cout << "q is empty!" << std::endl;
	}
	else {
		std::cout << "q isn't empty!" << std::endl;
	}

	std::cout << "\npop" << std::endl;
	q.pop();
	std::cout << "\n数据个数：" << q.size() << std::endl;
	std::cout << "front = " << q.front() << std::endl;

	std::cout << "\n清空队列：" << std::endl;
	while (!q.empty()) {
		q.pop();
	}

	std::cout << "\n数据个数：" << q.size() << std::endl;
	std::cout << "\nempty:" << std::endl;
	if (q.empty()) {
		std::cout << "q is empty!" << std::endl;
	}
	else {
		std::cout << "q isn't empty!" << std::endl;
	}
}

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

4.2.输出结果

构造：

数据个数：0

empty:
q is empty!

push（7）

数据个数：1
front = 7

push:1,2,3,4,5,6

数据个数：7
front = 7
7, 1, 2, 3, 4, 5, 6,
empty:
q isn't empty!

pop

数据个数：6
front = 1

清空队列：

数据个数：0

empty:
q is empty!
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

5.实现代码

#pragma once
#ifndef _QUEUE_H_
#define _QUEUW_H_

#include <cassert>

template <typename _dataType>
struct QueueNode
{
	using _QueueNodePtr = QueueNode*;

	_dataType m_value;
	_QueueNodePtr m_next;

	QueueNode() : m_value(_dataType()), m_next(nullptr) {}
	QueueNode(_dataType value) : m_value(value), m_next(nullptr) {}
	QueueNode(_dataType value, _QueueNodePtr next) : m_value(value), m_next(next) {}
};

template <typename _dataType>
class Queue
{
	using _QueueNodePtr = QueueNode<_dataType>*;
public:
	Queue() : m_front(nullptr), m_tail(nullptr), m_len(0) {}

	Queue(const Queue& q)
	{
		if (q.m_front) {
			m_front = new QueueNode<_dataType>(q.m_front->m_value);
			m_tail = m_front;
			_QueueNodePtr front = q.m_front->m_next;
			while (front) {
				m_tail->m_next = new QueueNode<_dataType>(front->m_value);
				m_tail = m_tail->m_next;
				front = front->m_next;
			}

			m_len = q.m_len;
		}
		else {
			m_front = nullptr;
			m_tail = nullptr;
			m_len = 0;
		}
	}

	Queue& operator = (const Queue& q)
	{
		while (this->m_front) {
			this->pop();
		}

		if (q.m_front) {
			m_front = new QueueNode<_dataType>(q.m_front->m_value);
			m_tail = m_front;
			_QueueNodePtr front = q.m_front->m_next;
			while (front) {
				m_tail->m_next = new QueueNode<_dataType>(front->m_value);
				m_tail = m_tail->m_next;
				front = front->m_next;
			}

			m_len = q.m_len;
		}
		else {
			m_front = nullptr;
			m_tail = nullptr;
			m_len = 0;
		}

		return *this;
	}

	void push(_dataType value)
	{
		if (m_front == nullptr) {
			m_front = new QueueNode<_dataType>(value);
			m_tail = m_front;
		}
		else {
			m_tail->m_next = new QueueNode<_dataType>(value);
			m_tail = m_tail->m_next;
		}

		m_len++;
	}

	void pop()
	{
		assert(m_front);

		if (m_front == m_tail) {
			delete m_front;
			m_front = nullptr;
			m_tail = nullptr;
		}
		else {
			_QueueNodePtr front = m_front;
			m_front = m_front->m_next;

			delete front;
			front = nullptr;
		}

		m_len--;
	}

	_dataType& front()
	{
		assert(m_front);

		return m_front->m_value;
	}

	size_t size()
	{
		return m_len;
	}

	bool empty()
	{
		return m_front == nullptr;
	}

private:
	_QueueNodePtr m_front;
	_QueueNodePtr m_tail;
	size_t m_len;
};

#endif // _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

6.总结

只有实现，并没有详细介绍。