数据结构：队列（C++含量更多）

JYY97409

510人浏览 · 2025-12-12 16:06:13

JYY97409 · 2025-12-12 16:06:13 发布

与C版本相比改进的地方

C++中同一个类中函数调用成员变量不用一次次的传参，直接使用成员名就行（这里面还是有一个隐藏的this的）

C++中可以直接写好构造函数和析构函数，就不用想C一样每次创建一个队列就初始化一次，在使用结束时也可以通过析构函数直接销毁，直接省了好多步骤

C++中创建的类的实例可以做到操作时互不干扰

其实还有优化空间，我写的时候每个函数中的判空都是再写一遍的，其实另外写一个判空函数更好

准备部分

struct QTNode//基本节点
{
	TypeNode _val;
	struct QTNode* next;
};

class QT
{
//...........
private:
	QTNode* _head;
	QTNode* _tail;
	int _size;
};

这里是队列的成员变量声明

构造函数&&析构函数

QT()//构造函数
	{
		_head = nullptr;
		_tail = nullptr;
		_size = 0;
	}
	~QT()//析构函数
	{
		QTNode* cur = _head;
		QTNode* next = nullptr;
		while (cur)
		{
			next = cur->next;
			free(cur);
			cur = next;
		}
	}

入队列（push）

入队列就是很经典的链表动态申请和链表的连接

void QTpush(TypeNode val)//入队列
	{
		QTNode* NewNode = (QTNode*)malloc(sizeof(QTNode));
		if (nullptr == NewNode)
		{
			perror("malloc");
			return;
		}
		NewNode->next = nullptr;
		NewNode->_val = val;
		if (nullptr == _head && nullptr == _tail)
		{
			_head = _tail = NewNode;
			_head->next = nullptr;
			_tail->next = nullptr;
		}
		else
		{
			_tail->next = NewNode;
			_tail = NewNode;
			_tail->next = nullptr;
		}
		_size++;
	}

出队列（pop）

TypeNode QTpop()//出队列
	{
		if (nullptr == _tail && nullptr==_head)
		{
			std::cout << "当前队列中没有数据" << std::endl;
			return -1;
		}
		else
		{
			TypeNode ret;
			if (nullptr == _tail)
			{
				std::cout << "当前队列中没有数据" << std::endl;
				return -1;
			}
			else if (_head == _tail)
			{
				ret = _head->_val;
				free(_head);
				_head = _tail = nullptr;
			}
			else
			{
				ret = _tail->_val;
				QTNode* cur = _head;
				while (cur->next != _tail)
				{
					cur = cur->next;
				}
				free(_tail);
				_tail = nullptr;
				_tail = cur;
				_tail->next = nullptr;//注意这里，不将_tail->next置空后续会越界访问
			}
			_size--;
			return ret;
		}	
	}

注意在将_tail指向的元素置空并指向上一个元素时应该将上一个的next置空，防止越界访问。

如果没有这一步的话，_tail指针在挪向上一个位置时它的next仍然指向已经被释放的空间，此时就会......

what can i say

就会坠机

取队头元素&&取队尾元素&&展示所以元素

TypeNode QTtail()//取头元素
{
	TypeNode ret;
	if (nullptr == _tail && nullptr == _head && _size == 0)
	{
		std::cout << "当前队列中没有数据" << std::endl;
		return -1;
	}
	else
	{
		if (nullptr == _tail)
		{
			ret = -1;
		}
		else
		{
			ret = _tail->_val;
		}
	}
	return ret;
}
TypeNode QTfront()//取尾元素
{
	TypeNode ret;
	if (nullptr == _tail && nullptr == _head && 0 == _size)
	{
		std::cout << "当前队列中没有数据" << std::endl;
		return -1;
	}
	else
	{
		if (nullptr == _head)
		{
			ret = -1;
		}
		else
		{
			ret = _head->_val;
		}
	}
	return ret;
}
void QTdisplay()//展示全部节点数据
{
	if (nullptr == _head && nullptr == _tail)
	{
		std::cout << "当前队列中没有数据" << std::endl;
		return;
	}
	else
	{
		QTNode* cur = _head;
		while (cur)
		{
			std::cout << cur->_val << "  ";
			cur = cur->next;
		}
		std::cout << std::endl;
	}
}

类的声明加定义

#pragma once
#include<iostream>
typedef int TypeNode;

struct QTNode//基本节点
{
	TypeNode _val;
	struct QTNode* next;
};

class QT
{
public:
	QT()//构造函数
	{
		_head = nullptr;
		_tail = nullptr;
		_size = 0;
	}
	~QT()//析构函数
	{
		QTNode* cur = _head;
		QTNode* next = nullptr;
		while (cur)
		{
			next = cur->next;
			free(cur);
			cur = next;
		}
	}
	void QTpush(TypeNode val)//入队列
	{
		QTNode* NewNode = (QTNode*)malloc(sizeof(QTNode));
		if (nullptr == NewNode)
		{
			perror("malloc");
			return;
		}
		NewNode->next = nullptr;
		NewNode->_val = val;
		if (nullptr == _head && nullptr == _tail)
		{
			_head = _tail = NewNode;
			_head->next = nullptr;
			_tail->next = nullptr;
		}
		else
		{
			_tail->next = NewNode;
			_tail = NewNode;
			_tail->next = nullptr;
		}
		_size++;
	}
	TypeNode QTpop()//出队列
	{
		if (nullptr == _tail && nullptr==_head)
		{
			std::cout << "当前队列中没有数据" << std::endl;
			return -1;
		}
		else
		{
			TypeNode ret;
			if (nullptr == _tail)
			{
				std::cout << "当前队列中没有数据" << std::endl;
				return -1;
			}
			else if (_head == _tail)
			{
				ret = _head->_val;
				free(_head);
				_head = _tail = nullptr;
			}
			else
			{
				ret = _tail->_val;
				QTNode* cur = _head;
				while (cur->next != _tail)
				{
					cur = cur->next;
				}
				free(_tail);
				_tail = nullptr;
				_tail = cur;
				_tail->next = nullptr;
			}
			_size--;
			return ret;
		}	
	}
	TypeNode QTtail()//取头元素
	{
		TypeNode ret;
		if (nullptr == _tail && nullptr == _head && _size == 0)
		{
			std::cout << "当前队列中没有数据" << std::endl;
			return -1;
		}
		else
		{
			if (nullptr == _tail)
			{
				ret = -1;
			}
			else
			{
				ret = _tail->_val;
			}
		}
		return ret;
	}
	TypeNode QTfront()//取尾元素
	{
		TypeNode ret;
		if (nullptr == _tail && nullptr == _head && 0 == _size)
		{
			std::cout << "当前队列中没有数据" << std::endl;
			return -1;
		}
		else
		{
			if (nullptr == _head)
			{
				ret = -1;
			}
			else
			{
				ret = _head->_val;
			}
		}
		return ret;
	}
	void QTdisplay()//展示全部节点数据
	{
		if (nullptr == _head && nullptr == _tail)
		{
			std::cout << "当前队列中没有数据" << std::endl;
			return;
		}
		else
		{
			QTNode* cur = _head;
			while (cur)
			{
				std::cout << cur->_val << "  ";
				cur = cur->next;
			}
			std::cout << std::endl;
		}
	}
private:
	QTNode* _head;
	QTNode* _tail;
	int _size;
};

实际使用

#include"QT.h"

int main()
{
	QT qt1;
	qt1.QTpush(1);
	qt1.QTpush(2);
	qt1.QTpush(3);
	qt1.QTpush(4);
	qt1.QTpush(5);
	qt1.QTpush(6);
	qt1.QTdisplay();
	std::cout << qt1.QTpop() << std::endl;
	std::cout << qt1.QTtail() << std::endl;
	std::cout << qt1.QTfront() << std::endl;
	qt1.QTdisplay();
	return 0;
}