(第二章一一栈与队列)第四节 队列的链式存储结构C++

这一节是第二章的最后一节了，队列的链式存储结构操作。这一节和链栈特别像，操作都是类似的，可以对比一下。

总结一下目前写的代码实现的操作：

• 入栈操作
• 出栈操作
• 初始化链队列
• 输出链队列全部元素
• 获取队列长度
  写的比较简陋，其实可以更复杂一点，比如查询操作，输入一个数，然后查询队列中有没有这个数等等。这些实现也比较简单，有兴趣可以自己实现一下。
  完整代码如下：

// 队列的顺序存储操作
// Author:chao
// Date:2022.07.14
#include
using namespace std;
#include
typedef int ElemType;  // 定义队列中的元素性质

//链队列的结构
// 结点
struct QNode
{
	ElemType data;
	QNode* next;
};

//链队列结构
struct LinkQueue
{
	QNode* front, * rear; 
};

void InitQueue(LinkQueue* Q)
{
	QNode* p = new QNode;
	p->next = NULL;
	Q->front = p;
	Q->rear = p;
}
//插入链队列元素
void EnQueue(LinkQueue* Q, ElemType e)
{
	QNode *s = new QNode; //开辟一个新结点
	if (!s) cout << "分配空间失败。" << endl;
	s->data = e;
	s->next = NULL;
	Q->rear->next = s; //当前队列Q的尾指针指向的结点，它的后继指向s。
	Q->rear = s; // 地洞队尾指针，把当前s设置为队尾结点，rear指向s。
}

// 元素出链队列,链队列是有头结点的。这里需要注意。
// 所以对于队列第一个元素是：Q->front->next;也就是头节点指向的下一个结点。
void DeQueue(LinkQueue* Q)
{
	//要把结点占用的内存释放掉，所以先新建一个结点暂存
	QNode* p;
	if (Q->front == Q->rear) cout << "队列为空。" << endl;
	p = Q->front->next; //把第一个结点暂存在p中
	Q->front->next = p->next;  // 头节点指向第二个结点
	if (Q->rear == p) Q->rear = Q->front; //如果删除结点恰好是队尾，那将队尾rear指向头结点。
	free(p);
}

//输出链队列元素
void Coutqueue(LinkQueue* Q)
{
	if (Q->front == Q->rear) cout << "队列为空。" << endl;
	QNode* p;
	p = Q->front->next;
	while (p != NULL)
	{
		cout << p->data<<" ";
		p = p->next;
	}
	cout << endl;
}

//获取队列长度
int LengthQueue(LinkQueue* Q)
{
	int length = 0;
	QNode* p; // 新建一个结点p用来指引队列中移动
	p = Q->front;
	while (p != NULL)
	{
		p = p->next;
		length++;
	}
	cout << "队列长度为： " << length << endl;
	return length;
}



int main() {
	LinkQueue qlink;
	InitQueue(&qlink);
	int n;
	ElemType e;
	cout << "请输入队列结点数：";
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cout << "输入数值： " << endl;
		cin >> e;
		EnQueue(&qlink, e);
	}
	cout << "完整队列如下：" << endl;
	Coutqueue(&qlink);
	DeQueue(&qlink);
	Coutqueue(&qlink);
	system("pause");
	return 0;
}

如果发现代码中有错误或者不足的地方，还望各位大佬们指正。