第三章算法设计题6

#pragma once
#include 

using namespace std;


//队列的链式存储结构
//结点类型的定义
typedef struct QNode
{
	int data;
	struct QNode* next;
}QNode,*Queueptr;

//只设一个指向队尾元素的指针
typedef struct
{
	Queueptr rear;//队尾指针
}linkQueue;

//初始化
void InitQueue(linkQueue &Q)
{ 
	Q.rear = new QNode;
	//将队尾指针指向头结点
	Q.rear->next = Q.rear;
	
}


//判队空
bool EmptyQueue(linkQueue &Q)
{
//当头结点的next指针指向自己时为空队
	if (Q.rear->next == Q.rear)
	{
		return true;
	}
	else
	{
		return false;
	}
	
}


//入队在尾结点处插入元素
void EnQueue(linkQueue &Q, int e)
{ 
	QNode* p = new QNode;//为入队元素分配结点空间，用指针p指向
	p->data = e;
	p->next = Q.rear->next;//初始化新结点并链入
	Q.rear->next = p;//头节点指向p
	Q.rear = p;//将尾指针移至新结点
}

//出队,把头结点后的元素删除 
int DeQueue(linkQueue& Q)
{
	int e;
	QNode* p;
	if (EmptyQueue(Q))
	{
		cout << "队列为空" << endl;
		exit(0);
	}

	//p指向队头元素
	p = Q.rear->next->next;
	//保存结点中数据
	e = p->data;

	//修改头节点的指针域
	Q.rear->next->next = p->next;
	//最后一个元素被删除
	if (p == Q.rear)
	{
		//p结点出队后，要将队尾指针指向头结点
		Q.rear = Q.rear->next;
		Q.rear->next = p->next;
	}

	delete p;//释放被删结点
	return e;
}

//清空
void ClearQueue(linkQueue &Q)
{ 
	QNode* s;
	//当队列非空，将队中元素逐个出队
	while (!EmptyQueue(Q))
	{
		s = Q.rear->next->next;
		Q.rear->next = s->next;
		delete s;
	}
}


//遍历
void printQ(linkQueue Q)
{
	QNode* temp = Q.rear->next->next;
	{
		while (temp != Q.rear->next)
		{
			cout << temp->data <<" ";
			temp = temp->next;
		}
		cout << endl;
	}
}



int main()
{
	linkQueue Q;
	InitQueue(Q);

	cout << "未插入元素之前：";
	if (EmptyQueue(Q))
	{
		cout << "空" << endl;
	}
	else
	{
		cout << "非空" << endl;
	}

	int num;
	cout << "请输入元素的个数：";
	cin >> num;

	int elem;
	for (int i = 0; i < num; i++)
	{
		cout << "请输入需要插入的元素：";
		cin >> elem;
		EnQueue(Q, elem);
	}
	


	cout << "插入元素之后：";
	if (EmptyQueue(Q))
	{
		cout << "空" << endl;
	}
	else
	{
		cout << "非空" << endl;
	}

	cout << "元素为：" << endl;
	printQ(Q);


	system("pause");
	return 0;
}