一、链队列的基本概念
队列的链式存储就是用一个线性链表来表示队列,称为链队,一般用单链表表示。
为了操作上的方便,需要一个头指针和尾指针分别指向链队列的队头和队尾元素。图形表示如下。
链队列的图形示意图:
front 指向链队的队头元素,rear指向链队的队尾元素。
删除出队时只要修改队头指针,插入入队时只要修改队尾指针。
二、链队列的实现
typedef int DataType; // 这里以整型为队列的数据类型
class QueueNode {
public:
DataType data;
QueueNode *next;
QueueNode() {
next = NULL;
}
}
class LinkQueue {
private:
QueueNode *front;
QueueNode *rear;
public:
LinkQueue() { // 构造一个新的空队列
front = NULL;
rear = NULL;
}
~LinkQueue() { // 销毁一个已存在的队列
QueueNode *p, *q;
p = front;
while(p) { // 删除链上所有的结点
q = p;
p=p->next;
delete q;
}
front = NULL; // 置为空表示空队列
rear = NULL; // 置为空表示空队列
}
int Empty_Queue(); // 判断队列是否为空
int En_Queue(DataType e); // 将元素e插入队尾
int De_Queue(DataType &e); // 从队头删除一个元素到e中返回
int Front_Queue(DataType &e); // 从队头取出一个元素到e中返回
}
(一)判断链队列是否为空
算法思想:只需判断front和rear是否都等于NULL。
int LinkQueue::Empty_Queue() {
return (front == NULL && rear == NULL);
}
(二)进队操作
算法思想:首先申请新结点,不成功则失败退出;否则,将申请的结点插入单链表的表尾。注意,此时如果原来的队列非空,只需修改队尾指针即可;若原来队列为空,则不仅要修改rear,还需要修改front后再返回成功标志。
int LinkQueue::En_Queue(DataType e) {
QueueNode *p = new QueueNode;
if (p) { // 申请结点成功
p->data = e;
if (rear) { // 原队列为非空队列,入队元素直接插入单链表的尾部
rear->next = p;
rear = p;
} else { // 原队列为空队列,插入元素既是队头元素也是队尾元素
front = rear = p;
}
return 1;
} else
return 0;
}
(三)出队操作
算法思想:首先判断队列是否为空,为空,则失败退出;否则,删除队头指针指向的结点。注意,此时如果原来的队列只有一个结点,则删除队头指针指向的结点后成了空队列,因此还要修改队尾指针。
int LinkQueue::De_Queue(DataType &e) {
QueueNode *p;
if (!Empty_Queue()) {
p = front;
e = p->data;
front = front->next; // 修改队头指针
if (!front) { // 删除出队元素后队列成了空队列,要修改队尾指针
rear = NULL;
}
delete p;
return 1;
} else
return 0;
}
(四)取队头元素操作
算法思想:首先判断队列是否为空,为空则失败退出;否则,取出队头指针front指向的结点的值。
int LinkQueue::Front_Queue(DataType &e) {
if (!Empty_Queue()) {
e = front->data;
return 1;
} else
return 0;
}