C++实现链队_c++链队列(有头结点)的初始化、入队、出队、取队头元素操作。

C++实现链队中的基本操作：

1、链队的初始化
2、链队的入队
3、链队的出队
4、链队的取值
5、链队的判空
6、链队的求长
7、链队的清空
8、链队的销毁
9、链队的打印

注意：在链队的出队操作中，要用if语句来判断出队元素是否为最后一个元素。若是，则将队尾指针重新赋值，指向头结点，否则尾指针会被delete。

 
//Date：2021/11/21
 
#include<iostream>
using namespace std;
#define	QElemType int//QElemType类型可根据实际情况自行设定
 
//*******************************队列的链式存储结构******************************
typedef struct QNode
{
	QElemType data;//结点的数据域
	struct QNode* next;//结点的指针域
}QNode, * QueuePtr;//QueuePtr为指向结构体QNode的指针类型
typedef struct
{
	QueuePtr front;//队头指针
	QueuePtr rear;//队尾指针
}LinkQueue;
 
//****************************链队的基本操作函数*****************************
 
//链队的初始化
void InitQueue(LinkQueue& Q)
{
	//构造一个空队列
	Q.front = Q.rear = new QNode;//生成新结点作为头结点，对头指针和队尾指针指向该结点
	Q.front->next = NULL;
}
 
//链队的入队
bool EnQueue(LinkQueue& Q, QElemType e)
{
	//在队尾插入元素e
	QNode* p;
	p = new QNode;
	p->data = e;
	p->next = NULL;
	Q.rear->next = p;
	Q.rear = p;//修改队尾指针
	return true;
}
 
//链队的出队
bool DeQueue(LinkQueue& Q, QElemType& e)
{
	//删除队头元素，并用e返回其值
	QNode* p;
	if (Q.front == Q.rear)
		return false;
	p = Q.front->next;//用p临时保存队头元素空间，以备释放
	e = p->data;//e保存队头元素的值
	Q.front->next = p->next;
	if (Q.rear == p)//若出队的是最后一个元素，则队尾指针指向头结点
		Q.rear = Q.front;
	delete p;//释放原队头元素空间
	return true;
}
 
//取链队的队头元素
bool GetHead(LinkQueue Q, QElemType& e)
{
	//返回链队的队头元素，不修改队头指针
	if (Q.front==Q.rear)
		return false;//链队为空，取值失败
	e = Q.front->next->data;
	return true;
}
 
//*******************************链队的基本功能函数****************************
 
//1、入队
void EnQueue(LinkQueue &Q)
{
	QElemType e;
	bool flag;
	cout << "请输入要入队的元素：" << endl;
	cin >> e;
	flag = EnQueue(Q, e);
	if (flag)
		cout << "入队成功！" << endl;
	else
		cout << "入队失败！" << endl;
}
 
//2、出队
void DeQueue(LinkQueue &Q)
{
	QElemType e;
	bool flag;
	flag = DeQueue(Q, e);
	if (flag)
		cout << "出队元素为：" << e << endl;
	else
		cout << "出队失败！" << endl;
}
 
//3、取值
void GetHead(LinkQueue Q)
{
	QElemType e;
	bool flag;
	flag = GetHead(Q, e);
	if (flag)
		cout << "取得的队头元素为：" << e << endl;
	else
		cout << "取队头元素失败！" << endl;
}
 
//4、判空
void QueueEmpty(LinkQueue Q)
{
	if (Q.front == Q.rear)
		cout << "链队为空！" << endl;
	else
		cout << "链队不为空！" << endl;
}
 
//5、求长
void QueueLength(LinkQueue Q)
{
	int i = 0;
	while (Q.front != Q.rear)//遍历链队，统计结点数
	{
		i++;
		Q.front = Q.front->next;
	}
	cout << "链队的长度为：" << i << endl;
}
 
//6、清空
void ClearQueue(LinkQueue& Q)
{
	QNode* p,*q;
	p = Q.front->next;
	while (p)//从队头开始，依次删除
	{
		q = p->next;
		delete p;
		p = q;
	}
	Q.rear = Q.front;
}
 
//7、销毁
void DestroyQueue(LinkQueue& Q)
{
	QNode* p;
	while (Q.front)//从头结点开始，依次删除
	{
		p = Q.front->next;
		delete Q.front;
		Q.front = p;
	}
}
 
//8、打印
void PrintQueue(LinkQueue Q)
{
	int i = 0;
	while (Q.front != Q.rear)//遍历链队
	{
		i++;
		Q.front = Q.front->next;
		cout << "链队第" << i << "个数据为：" << Q.front->data << endl;
	}
}
 
//菜单
void menu()
{
	cout << "***************************************************************************" << endl;
	cout << "***********************************1、入队*********************************" << endl;
	cout << "***********************************2、出队*********************************" << endl;
	cout << "***********************************3、取值*********************************" << endl;
	cout << "***********************************4、判空*********************************" << endl;
	cout << "***********************************5、求长*********************************" << endl;
	cout << "***********************************6、清空*********************************" << endl;
	cout << "***********************************7、销毁*********************************" << endl;
	cout << "***********************************8、打印*********************************" << endl;
	cout << "***********************************9、退出*********************************" << endl;
	cout << "***************************************************************************" << endl;
}
 
int main()
{
	LinkQueue Q;
	InitQueue(Q);
	int select;
	while (1)
	{
		system("CLS");//清屏操作
		menu();
		cout << "请输入菜单序号：" << endl;
		cin >> select;
		switch (select)
		{
		case 1://入队
			EnQueue(Q);
			system("pause");//按任意键继续
			break;
		case 2://出队
			DeQueue(Q);
			system("pause");
			break;
		case 3://取值
			GetHead(Q);
			system("pause");
			break;
		case 4://判断链队是否为空
			QueueEmpty(Q);
			system("pause");
			break;
		case 5://求链栈的长度
			QueueLength(Q);
			system("pause");
			break;
		case 6://清空
			ClearQueue(Q);
			system("pause");
			break;
		case 7://销毁
			DestroyQueue(Q);
			system("pause");
			return 0;
			break;
		case 8://打印
			PrintQueue(Q);
			system("pause");
			break;
		case 9:
			cout << "欢迎下次使用!" << endl;//退出
			system("pause");
			return 0;
			break;
		default:
			cout << "菜单序号输入有误！" << endl;
			system("pause");
			break;
		}
	}
	system("pause");
	return 0;
}

参考资料：《数据结构》（C语言版）严蔚敏