数据结构的C++实现之队列的链式存储结构

数据结构的C++实现之队列的链式存储结构2013-08-13 csdn Simba888888队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头节点，而队尾指针指向终端节点。空队列时，front和rear都指向头节点。

示例程序：（改变自《大话数据结构》）

#include<iostream>using namespace std;typedef int ElemType;typedef struct Node{ElemType data;struct Node *next;} Node, *NodePtr;typedef struct{NodePtr front;/* 队头、队尾指针 */NodePtr rear;} LinkQueue;/* 构造一个空队列 */bool InitQueue（LinkQueue *Lp）{cout << "Init Queue ..." << endl;NodePtr p = （NodePtr）malloc（sizeof（Node））;p->next = NULL;Lp->front = Lp->rear = p;return true;}/* 销毁队列,包括头节点 */bool DestroyQueue（LinkQueue *Lp）{cout << "Destroy Queue ..." << endl;while （Lp->front）{Lp->rear = Lp->front->next;free（Lp->front）;Lp->front = Lp->rear;}return true;}/* 清为空队列，保留头节点 */bool ClearQueue（LinkQueue *Lp）{cout << "Clear Queue ..." << endl;NodePtr p = Lp->front->next;Lp->front->next = NULL;Lp->rear = Lp->front;NodePtr q;while （p）{q = p->next;free（p）;p = q;}return true;}bool QueueEmpty（LinkQueue LQ）{return LQ.front == LQ.rear;}int QueueLength（LinkQueue LQ）{int i = 0;if （LQ.front == NULL）return 0;NodePtr p = LQ.front->next;while （p）{++i;p = p->next;}return i;}bool GetHead（LinkQueue LQ, ElemType *pe）{NodePtr p;if （LQ.front == LQ.rear）return false;p = LQ.front->next;*pe = p->data;cout << "Get Head Item : " << *pe << endl;return true;}/* 插入元素Elem为队列的新的队尾元素 */bool EnQueue（LinkQueue *Lp, ElemType Elem）{cout << "EnQueue Item " << Elem << endl;NodePtr s = （NodePtr）malloc（sizeof（Node））;s->data = Elem;s->next = NULL;Lp->rear->next = s;Lp->rear = s;return true;}/*删除队列的队头元素,用*pe返回其值 */bool DeQueue（LinkQueue *Lp, ElemType *pe）{if （Lp->front == Lp->rear）return false;NodePtr p = Lp->front->next;*pe = p->data;cout << "DeQueue Item " << *pe << endl;Lp->front->next = p->next;if （Lp->rear == p）/* 若队头就是队尾，则删除后将rear指向头结点*/Lp->rear = Lp->front;free（p）;return true;}/* 从队头到队尾依次对队列中每个元素输出 */bool QueueTraverse（LinkQueue LQ）{cout << "Queue Traverse ..." << endl;NodePtr p = LQ.front->next;while （p）{cout << p->data << " ";p = p->next;}cout << endl;return true;}int main（void）{LinkQueue LQ;InitQueue（&LQ）;for （int i = 0; i < 5; i++）EnQueue（&LQ, i）;QueueTraverse（LQ）;int result;GetHead（LQ, &result）;DeQueue（&LQ, &result）;QueueTraverse（LQ）;if （！QueueEmpty（LQ））cout << "Queue Length : " << QueueLength（LQ） << endl;/*ClearQueue（&LQ）;*/DestroyQueue（&LQ）;cout << "Queue Length : " << QueueLength（LQ） << endl;return 0;}

输出为：

总的来说，如果可以确定队列的最大值，建议用循环队列，如果不能预估队列的长度，则用链队列。