C语言：链表实现队列（queue）

生活中，排队到处可见：超市结账的时候排队，电影院检票的时候排队，医院挂号的时候排队等等。先到的人当然有优先的权利！先到先得，后到后得就是队列得核心思想。

如图。A 先进队，A 就得先出来，不管 A 愿不愿意！接着是 B , C , D , E , F , G 。总之，队列就是指先进先出（FIFO, First-In-First-Out）的线性表。那么问题来了，特殊的线性表.........嗯，是用顺序表实现呢还是用链表实现呢？而且队列的队头只能删除数据，队尾只能插入数据...貌似链表好实现一点呢！

我们先创建两个结构体，一个是链表节点的结构，一个是包含两个指针的结构，这两个指针，一个是指向链表头节点的指针（head），一个是指向链表尾节点的指针（tail）。队尾每进入一个节点，tail 指针就向后指向新节点；队头每次出去一个节点，head 指针就指向后一个节点。

最后队列大致的结构如下图：

 结构体创建

typedef struct QueueNode{
	struct QueueNode * next;
	int data;
}qNode;

typedef struct queue{
	qNode * head;//链表头指针
	qNode * tail;//链表尾指针
}pNode;

 初始化队列

void queueInit(pNode * pq){
	pq->head=NULL;
	pq->tail=NULL;
}

 队列的进列和出列

void queuePush(pNode * pq,int data){
	 qNode * newNode=(qNode *)malloc(sizeof(qNode));
	 newNode->data=data;
	 newNode->next=NULL;
	 if(pq->head==NULL){
		 pq->head=pq->tail=newNode;
	 }else{
		 pq->tail->next=newNode;
		 pq->tail=newNode;
	 } 
}
void queuePop(pNode * pq){
	qNode * cur=pq->head;
	if(pq->head==NULL){
		return;
	}
	if(pq->head==pq->tail){
		free(cur);
		pq->head=pq->tail=NULL;
	}else{
		pq->head=cur->next;
		free(cur);
	}
}

取出队列头节点和尾节点

int queueFront(pNode * pq){
	if(pq->head==NULL){
		return -1;
	}
	return pq->head->data;
}

int queueBack(pNode * pq){
	if(pq->tail==NULL){
		return -1;
	}
	return pq->tail->data;
}

读取队列的长度

int queueSize(pNode * pq){
	int i=0;
	qNode * cur=pq->head;
	if(pq->head==NULL)
	while(cur!=NULL){
		i++;
		cur=cur->next;
	}
	return i;
}

销毁队列

void queueDestroy(pNode * pq){
	qNode * cur=pq->head;
	while(cur!=pq->tail){
		qNode * next=cur->next;
		free(cur);
		cur=next;
	}
	pq->head=NULL;
	pq->tail=NULL;
}

调试

int main()
{
	pNode q;
	queueInit(&q);
	queuePush(&q,1);
	queuePush(&q,2);
	queuePush(&q,3);
	queuePush(&q,4);//添加元素1，2，3，4
	printf("%d\n",queueFront(&q));//读取第一个元素
	printf("%d\n",queueBack(&q));//读取第二个元素
	queuePop(&q);//出列一个元素
	queuePush(&q,5);//进列一个元素
	printf("%d\n",queueFront(&q));//读取第一个元素
	printf("%d\n",queueBack(&q));//读取第二个元素
	system("pause");
}

结果

总之，根本没有什么真正的队列空间来存放链表，而是只抽象成一个结构体，结构体中只有两个指向链表头节点和尾节点的指针。最后通过修改头指针和尾指针的指向来实现队列的进列和出列罢了！

最后，大家也可以尝试一下用数组实现队列，这里就不多介绍啦~