前面用顺序存储的方式实现了队列，顺序存储的方式存在着缺点，在出队时要移动大量的元素，在大数据量时需要消耗大量的资源。针对此采用链式存储的方式实现队列。其结构组成如下,需要重点说明的是增加了length，其表示结点的个数，一般书上没有这个元素，Martin老师加上的，确实好用！
typedef struct _linlList {datatype data;_linlList* next;
}linkList;
typedef struct _linkQueue {int length;linkList* front;linkList* rear;
}linkQueueNode,linkQueue;
用图表示更加直观：
由结构体组成和图可以看出，头结点是带有两个指针 front和 rear，分别指向第一个结点和最后一个结点，length是结点的个数，初始化为0。结点的组成是链式结构，由数据data和next指针组成。在前期搞明白单链式结构的基础上，相应的操作就变得很简单了。初始化函数如下
bool initLinkQueue(linkQueue* &lq) {lq = new linkQueue;if (!lq) return false;lq->length = 0;lq->front = lq->rear = NULL;return true;
}
其他的操作都是常规的，入队、出队、遍历、获取头元素等等。整个代码如下，亲测可过
#include<Windows.h>
#include<iostream>
#define MAX_SIZE 10
using namespace std;
typedef int datatype;
typedef struct _linlList {datatype data;_linlList* next;
}linkList;
typedef struct _linkQueue {int length;linkList* front;linkList* rear;
}linkQueueNode,linkQueue;bool initLinkQueue(linkQueue* &lq);//链式队列初始化
bool linkQueueEnter(linkQueue*& lq, datatype data);//入队
void linkQueuePrint(linkQueue*& lq);
bool linkQueueDelete(linkQueue*& lq, datatype* data);//出队
bool linkQueueGetHead(linkQueue*& lq, datatype* data);//获取队首的元素，不出队
void linkQueueClear(linkQueue*& lq);//清空队列
int linkQueueGetLength(linkQueue*& lq);//获取队列的长度
void linkQueueDestroy(linkQueue*& lq);//销毁列表int main() {linkQueue* lq=NULL;initLinkQueue(lq);int i;for (i = 0; i < 15; i++) {if (linkQueueEnter(lq, i)) {cout << "入队成功！" << endl;}else {cout << "入队失败！" << endl;}}linkQueuePrint(lq);cout << "***********出队******************" << endl;datatype* data=new int ;for (int i = 0; i < 5; i++) {if (linkQueueDelete(lq, data)) {cout << "出队的元素是" << *data << endl;}else {cout << "出队失败！" << endl;}}if (linkQueueGetHead(lq, data)) {cout << "获取队列首元素是:" << *data << endl;}cout << "队列的长度为:" << linkQueueGetLength(lq)<<endl;linkQueueClear(lq);cout << "清空后队列的长度为:" << linkQueueGetLength(lq)<<endl;linkQueueDestroy(lq);system("pause");return 0;
}
bool initLinkQueue(linkQueue* &lq) {lq = new linkQueue;if (!lq) return false;lq->length = 0;lq->front = lq->rear = NULL;return true;
}
bool linkQueueEnter(linkQueue*& lq, datatype data) {if (!lq || lq->length == MAX_SIZE) return false;linkList* node = new linkList;node->data = data;node->next = NULL; if (!lq->front) {lq->rear=lq->front = node;}else {lq->rear->next = node;lq->rear = node;}lq->length++;return true;
}
void linkQueuePrint(linkQueue*& lq) {if (!lq) return ;if (!lq->length) {cout << "队列长度为0" << endl;return;}linkList* tmp = lq->front;while(tmp) {cout << tmp->data << " ";tmp = tmp->next;}cout << endl;
}
bool linkQueueDelete(linkQueue*& lq, datatype* data) {if (!lq || !lq->length) return false;*data = lq->front->data;linkList* tmp = lq->front;lq->front = tmp->next;delete tmp;lq->length--;return true;
}
bool linkQueueGetHead(linkQueue*& lq, datatype* data) {if (!lq || !lq->length) return false;*data = lq->front->data;return true;
}
int linkQueueGetLength(linkQueue*& lq) {if (!lq) return -1;return lq->length;
}
void linkQueueClear(linkQueue*& lq) {if (!lq || !lq->length) return;linkList* tmp = NULL;while (lq->front) {tmp = lq->front->next;delete lq->front;lq->front = tmp;}lq->front = lq->rear = NULL;lq->length = 0;
}
void linkQueueDestroy(linkQueue*& lq) {if (!lq || !lq->length) return;linkList* tmp = lq->front;while (lq->front) {tmp = lq->front->next;delete lq->front;lq->front = tmp;}delete lq->front;delete lq->rear;delete lq;
}