以前使用的顺序存储的队列，可是就是哪怕是循环队列，也可能会遇到数组溢出的问题。这时，使用链式存储会是一个更好的选择。web

一.链队列

队列的链式存储结构，其实就是线性表的单链表，只不过只能尾进头出，简称为链队列。
将头指针指向链队列的头结点

并非front指针直接指向第一个元素。数组

二.链队列实现

链队列的存储结构，这里申明两个结构体，一个是链表的，一个是队列的。svg

typedef int QElemtype;
typedef struct QNode{
	QElemtype data;
	struct QNode * next;
}QNode,*LinkQueuePtr;
typedef struct{
	LinkQueuePtr front,rear;
}LinkQueue;

队列初始化：spa

Status LinkQueue_Init(LinkQueue *Q)
{
	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
	Q->front = Q->rear = q;
	Q->front->next = NULL;
	return OK; 
}

这里必定记得将q赋给Q->front 和Q->rear。否则后面代码运行会错误。深入体会3d

入队操做指针

Status EnLinkQueue(LinkQueue *Q,QElemtype e)
{
	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
	q->data = e;
	q->next = NULL;
	Q->rear->next = q;
	Q->rear = q;
	return OK;
}

出队操做：code

Status DeLinkQueue(LinkQueue *Q,QElemtype *e )
{
	LinkQueuePtr p;
	if(Q->front == Q->rear)
		return ERROR;
	p = Q->front->next;
	*e = p->data;
	Q->front->next = p->next;
	if(Q->rear == p)
		Q->front = Q->rear;
	printf("%d ",p->data);
	free(p);
	return OK;
}

这些操做都和单链表操做相似，就是断链，挂链。而后记得出队是操做front，入队是操做rear。
实现代码xml

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
typedef int Status;
typedef int QElemtype;
typedef struct QNode{
	QElemtype data;
	struct QNode * next;
}QNode,*LinkQueuePtr;
typedef struct{
	LinkQueuePtr front,rear;
}LinkQueue;

Status LinkQueue_Init(LinkQueue *Q)
{
	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
	Q->front = Q->rear = q;
	Q->front->next = NULL;
	return OK; 
}

Status EnLinkQueue(LinkQueue *Q,QElemtype e)
{
	LinkQueuePtr q = (LinkQueuePtr)malloc(sizeof(QNode));
	q->data = e;
	q->next = NULL;
	Q->rear->next = q;
	Q->rear = q;
	return OK;
}


Status DeLinkQueue(LinkQueue *Q,QElemtype *e )
{
	LinkQueuePtr p;
	if(Q->front == Q->rear)
		return ERROR;
	p = Q->front->next;
	*e = p->data;
	Q->front->next = p->next;
	if(Q->rear == p)
		Q->front = Q->rear;
	printf("%d ",p->data);
	free(p);
	return OK;
}

int main(void)
{
	LinkQueue Q;
	QElemtype e;
	LinkQueue_Init(&Q);
	EnLinkQueue(&Q,1293);
	EnLinkQueue(&Q,3293);
	EnLinkQueue(&Q,32293);
	EnLinkQueue(&Q,12393);
	DeLinkQueue(&Q,&e);
	return 0;
}

三.结束

链队列的入队和出队在时间复杂度上都是O（1）。可是在申请和释放结点会有必定开销。
在肯定队列长度最大值状况下，选择循环队列。没法肯定时，用链队列。blog