C# · 12月 20, 2021

数据结构知识整理 – 链队

主要内容

队列的定义

链队的存储结构

链队的各项操作

初始化

入队

出队

取队头元素

 

队列的定义

栈和队列是两种重要的线性结构,与一般线性表不同,它们是操作受限的特殊线性表,主要用于辅助其他数据结构的操作和处理,基本不用于存储数据元素信息。

队列(Queue)是一种先进先出(First In First Out,FIFO)的线性表。它只允许在表的一端插入,而在表的另一端删除元素。这和日常生活中的排队一个道理。

在队列中,允许插入的一端叫队尾(rear),允许删除的一端则称为队头(front)。

链队的存储结构

链队是指采用链式存储结构实现的队列,通常采用单链表。

一个链队显然需要两个分别指示队头和队尾的指针才能唯一确定,所以不能像链栈那样仅用一个基地址表示。

初始状态时,队头(尾)结点为空,即 front == rear == NULL; ,这同时也是判断空队的条件;

typedef struct QNode /*链队结点结构*/

{

Elemtype data;

struct QNode *next; /*结点间的指向*/

} QNode;

typedef struct /*链队结构*/

{

QNode *front; /*队头结点指针*/

QNode *rear; /*队尾结点指针*/

} LinkQueue;

链队的各项操作

初始化

void InitQueue(LinkQueue &Q)

{

Q.front = Q.rear = new QNode; /*给指针front和rear动态分配同一个空间,该空间为头结点空间,data为空*/

Q.rear->next = NULL; /*队尾(头)结点的指针域设为空*/

}

入队

插入操作只考虑队尾指针rear,rear指向新插入结点,新插入结点的指针域设为NULL。

void EnQueue(LinkQueue &Q,Elemtype e)

{

QNode *p = new QNode; /*插入新结点*/

p->data = e;

p->next = NULL;

Q.rear->next = p;

Q.rear = p;

}

出队

删除操作只考虑队头指针front,头结点指向出队结点的下一个结点,保存出队结点的数据元素信息。

void DeQueue(LinkQueue &Q,Elemtype &e)

{

if(Q.front == Q.rear) exit(-1); /*空队*/

QNode *p = new QNode; /*p用于临时保存出队结点空间,以备释放*/

p = Q.front->next; /*队头指针front指向空结点,不含数据元素信息,我们操作的结点应该是它的下一个结点*/

e = p->data; /*保存出队结点的数据元素信息*/

Q.front->next = p->next; /*使队头结点(空结点)的指针指向出队结点的下一个结点*/

if(Q.rear == p) Q.rear = Q.front; /*最后一个结点被删除,重新变为空队*/

delete p; /*利用完出队结点,释放空间*/

}

取队头元素

Elemtype GetHead(LinkQueue &Q)

{

if(Q.front != Q.rear) /*非空队*/

return Q.front->next->data;

}