第94篇 C++数据结构（四）队列

• 1.队列简介
• • 1.队列的存储结构
• 2.节点
• 3.实现
• • 3.1.变量
  • 3.2.方法
• 4.测试
• • 4.1.测试代码
  • 4.2.输出结果
• 5.实现代码
• 6.总结

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

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

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

template 
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) {}
};

#include 

#include "Queue.h"

void queueTest();

int main()
{
	queueTest();

	return 0;
}

void queueTest()
{
	std::cout << "n构造：" << std::endl;
	Queue 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 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;
	}
}

构造：

数据个数：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!

#pragma once
#ifndef _QUEUE_H_
#define _QUEUW_H_

#include 

template 
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 
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_

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