主要内容

队列的定义

链队的存储结构

链队的各项操作

初始化

入队

出队

取队头元素

?

队列的定义

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

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

}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!