第四期 02季 C/C++数据结构 链队列的基本操作

本期关注点当然是我们的队列，队列是先进先出的。（本季链队列操作）

本次实训关注点在于链队列，操作代码如下：

#include 
using namespace std;

typedef struct QNode {
	char data;
	struct QNode* next;
}QNode,*QueuePtr;		//结点类型 指针类型 QueuePtr为指向结构体QNode的指针型

typedef struct {
	QueuePtr front;
	QueuePtr rear;
}linkQueue;				//链队列

void InitQNode(linkQueue &Q) {
	Q.front = Q.rear = new QNode;	//生成新结点作为头结点，队头和队尾指针指向此结点    /单链表：新生一个结点指向此结点
	if (!Q.front){
		cout << "获取空间失败！未完成初始化。" << endl;
	}
	else {
		Q.front->next = NULL;			//新生头结点指针域置空
		cout << "初始化成功。 " << endl;
	}
}
void PushQueue(linkQueue &Q) {		//入队
	QNode* p;
	cout << "输入入队的个数：";
	int n; cin >> n;
	cout << "入队的元素为：";
	for (int i = 0; i < n; i++){
		p = new QNode;
		char e; cin >> e;
		p->data = e;
		p->next = NULL;			//新建一个结点 为了接在尾指针后面

		Q.rear->next = p;		//1.修改尾指针  将链队列的最后一个元素的下一个指向新建的p结点
		Q.rear = p;				//将队列的最后一个直接指向p//将队列p作为最后一个元素		
	}	
}

void PopQueue(linkQueue& Q) {		//出队
	QNode* p;
	cout << "输入出队的个数：";
	int n; cin >> n;
	cout << "出队元素为：";
	char e; 
	for (int i = 0; i < n; i++) {
		if (Q.front==Q.rear){			//判断是否为空
			cout << "队列内无元素，无法出栈！";
		}
		else {
			p = new QNode;				//新创结点，存出队列元素
			p = Q.front->next;			//将第一个元素赋值给p
			e = p->data;				//第一个元素赋值给e
			cout << e;
			Q.front->next = p->next;	//将p 的下一个最为第一个元素
			if (Q.rear == p) {			//如果遇到最后一个指针，删除结点，并让头尾结点指向头结点
				Q.front = Q.rear;
			}
			delete p;
		}
	}
	cout << endl;
}
void GetHead(linkQueue &Q) {
	if (Q.front!=Q.rear){
		cout << "队头元素为：" << Q.front->next->data << endl;
	}
	else
	{
		cout << "队列为空，无头元素！" << endl;
	}
}
void DesQueue(linkQueue& Q) {
	QNode* p;
	while (Q.front) {
		p = Q.front->next;				//实现将 Q.front->next给新的结点p
		delete Q.front;					//在将Q.front销毁
		Q.front = p;				//在将结点p赋值给Q.front（Q.front结点指向p)
	}
	cout << "销毁成功" << endl;
}
int main() {
	linkQueue Q;
	cout << "1.";
	InitQNode(Q);

	cout << "2.";
	PushQueue(Q);

	cout << "3.";
	PopQueue(Q);
	cout << "4.";
	GetHead(Q);
	cout << "5.";
	DesQueue(Q);
}

代码运行截图：