队列的链式存储结构（链队）_队列的链式存储结构代码

链队

1.队列的链式存储结构

typedef struct QNode{	//结点结构
	QElemType data;		//结点数据域
	struct QNode *next;	//结点指针域
}QNode,*QueuePtr;	//指向某个结点的指针类型QNode*，指向队头和队尾结点的指针类型QueuePtr

typedef struct{		//链队结构
	QueuePtr front;	//队头指针
	QueuePtr rear;	//队尾指针
}LinkQueue;	
1
2
3
4
5
6
7
8
9

2.链队的初始化操作

初始化就是构造一个只有一个头结点的空队

Status InitQueue(LinkQueue &Q){
	Q.front = Q.rear = new QNode;	//生成新结点为头结点，同时队头和队尾指向此结点
	Q.front -> next = NULL;		//头结点的指针域置空
	return OK;
}
1
2
3
4
5

3.链队的入队操作

链队在入队前无需判断是否队满，而需要为入队元素动态分配一个结点空间

Status EnQueue(LinkQueue &Q, QElemType e){
	p = new QNode;	//创建新结点（指针指向结点，用该指针代表该结点）
	p->data = e;	//将元素填入结点数据域
	p->next = NULL;	//将此结点指针域置空
	Q.rear->next = p;	//将前驱结点和新结点相连
	Q.rear = p;	//将p指向的结点，现在用Q.rear来替代它指向此结点
	return OK;
}
1
2
3
4
5
6
7
8

4.链队的出队操作

链队在出队前需判断队列是否为空，在出队后需释放队头元素的所占空间
删除队列中某一个元素

删除最后一个元素

Status DeQueue(LinkQueue &Q, QElemType &e){
	if(Q.front == Q.rear)	//判断队列空
		return ERROR;
	p = Q.front->next;	//重命名Q.front->next为p
	e = p->data;	//将结点数据域的元素赋值给e，达到清空目的
	Q.front->next = p->next;	//用Q.front->next代替p->next指向p->next指向的结点
	if(Q.rear == p)	//如果删除的是最后一个元素
		Q.rear = Q.front;	//恢复为链队的初始状态
	delete p;	//删除结点(用指向结点的指针代表结点)
	return OK;
}
1
2
3
4
5
6
7
8
9
10
11

5.取出队头元素

SElemType GetHead(LinkQueue Q){
	if(Q.front != Q.rear)	//队列非空
		return Q.front->next->data;
}
1
2
3
4