栈和队列的应用 —— 链队列

栈和队列的应用 —— 链队列

队列除了可以采用顺序存储（顺序队列），也可以采用链式存储（链队列）。

顺序队列指分配一段连续的空间，用两个整型下标front和rear分别指向队头和队尾。

而链队列类似于一个单链表，需要用两个指针front和rear分别指向队头和队尾。

为了在出队时删除元素方便，可以增加一个头节点。因为链队列是单链表形式，因此可以借助单链表的定义。

链队列中节点的结构体定义：

链队列的结构体定义：

对链队列的操作和单链表一样，只不过它只能在队头删除，在队尾插入，是操作受限的单链表。

对链队列的基本操作包括初始化、入队、出队和取队头元素等。

【初始化】

进行链队列的初始化，创建一个头节点，使头指针和尾指针指向头节点

[算法代码]

void InitQueue(LinkQueue &Q){  //注意使用引用参数，否则出了函数的作用域，其改变无效
	Q.front = Q.rear = new Qnode;  //创建头节点，使头指针和尾指针指向头节点
	Q.front-> next = NULL;
}
1
2
3
4

【入队】

先创建一个新节点，将元素e 存入该节点的数值域

p = new Snode;  //生成新节点
p->data = e; //将e 放在新节点的数据域
1
2

然后将新节点插入队尾，使尾指针后移

其中：①“Q.rear->next=s ”指把s 节点的地址赋值给队列尾节点的next域，即尾节点的next指针指向s ；②“Q.rear=s ”指把s 节点的地址赋值给尾指针，即尾指针指向s ，尾指针永远指向队尾。

[算法代码]

void EnQueue(LinkQueue &Q , int e){ //入队，将元素 e 放入队尾
	Qptr = s;
	s = new Qnode;
	s-> data = e;
	s-> next = NULL;
	Q.rear->next = s; //将新节点插入队尾
	Q.rear = s; //尾指针后移
}
1
2
3
4
5
6
7
8

【出队】

出队相当于删除第1个数据元素，即将第1个数据元素节点跳过去，首先用p 指针指向第1个数据节点，然后跳过该节点，即Q.front->next=p ->next

若在队列中只有一个元素，则在删除后需要修改队尾指针

[算法代码]

bool DeQueue(LinkQueue &Q , int &e){ //出队，删除Q的队头元素，用e 返回其值
	if(Q.front == Q.rear){ //队空
		return false;
	}
	Qptr p = Q.front->next;
	e = p->data; //保留队头元素
	Q.front-> next = p->next;
	if(Q.rear == p){ //若在队列中只有一个元素，则在删除后需要修改队尾指针
		Q.rear = Q.front;
	}
	delete p;
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

【取队头元素】

队头实际上是Q.front->next指向的节点，即第1个数据节点，队头元素就是该节点的数据域存储的数据元素

[算法代码]

int GetHead(LinkQueue Q){ //取队头元素，不修改队头指针
	if(Q.front != Q.rear){ //队列非空
		return Q.front-> next->data;
	}
	return -1;
}
1
2
3
4
5
6