数据结构知识整理 - 链队

概述本文章向大家介绍数据结构知识整理 - 链队，主要包括数据结构知识整理 - 链队使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

主要内容

队列的定义

链队的存储结构

链队的各项 *** 作

初始化

入队

出队

取队头元素

 

队列的定义

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

队列（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;

}

总结

以上是内存溢出为你收集整理的数据结构知识整理 - 链队全部内容，希望文章能够帮你解决数据结构知识整理 - 链队所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。