链队实现（C语言）

我们之前已经了解过栈了，我们知道，栈是先进后出，后进先出

那么队则是先进先出，后进后出

就像我们去排队买饭一样，排在前面的人就先买到，天经地义对吧>-<

那么我们知道了队的原理，链队实现起来就相对容易多了。

在这里我们要注意：我们这里的头节点不能和之前的头节点一样了，因为我们这是链式队列，需要的操作是先进先出，后进后出，即尾插头删，所以这里我们的头节点要有两个指针域，分别指向待插入位置和待删除位置。

我们先在头文件中进行函数声明

typedef int ELEM_TYPE;
typedef struct Node {
	ELEM_TYPE data;
	struct Node* next;
}Node,*PNode;
typedef struct Head {
	struct Node* front;
	struct Node* rear;
}Head,*Plist;
void Init(Plist plq);
bool Push(Plist plq,ELEM_TYPE val);
bool Pop(Plist plq);
bool Top(Plist plq,ELEM_TYPE* rtval);
int Getlength(Plist plq);
bool IsEmpty(Plist plq);
void Clear(Plist plq);
void Destory(Plist plq);
void Show(Plist plq);

头文件中函数定义

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include"list_queue.h"
void Init(Plist plq) {
	assert(plq!=NULL);
	plq->front = NULL;
	plq->rear = NULL;
}
bool Push(Plist plq, ELEM_TYPE val) {
	assert(plq != NULL);
	struct Node* pnewnode = (struct Node*)malloc(sizeof(struct Node));
	assert(pnewnode!=NULL);
	pnewnode->data = val;

	if (IsEmpty(plq)) {
		pnewnode->next = NULL;
		plq->front = plq->rear = pnewnode;
		return true;
	}
	pnewnode->next = plq->rear->next;
	plq->rear->next = pnewnode;
	plq->rear = pnewnode;
	return true;
}
bool Pop(Plist plq) {
	assert(plq!=NULL);
	if (IsEmpty(plq)) {
		return false;
	}
	if (plq->front->next==NULL){//plq->front==plq->rear
		free(plq->front);
		plq->front = plq->rear = NULL;
		return true;
	}

	struct Node* p = plq->front;
	plq->front = p->next;
	free(p);
	p = NULL;
	return true;
}
bool Top(Plist plq, ELEM_TYPE* rtval) {
	assert(plq != NULL);
	if (IsEmpty(plq)) {
		return false;
	}
	*rtval = plq->front->data;
	return true;
}
int Getlength(Plist plq) {
	assert(plq!=NULL);
	int count = 0;
	for (struct Node* p = plq->front; p!= NULL;p=p->next) {
		count++;
	}
	return count;
}
bool IsEmpty(Plist plq) {
	assert(plq!=NULL);
	return plq->front == NULL;
}
void Clear(Plist plq) {
	assert(plq!=NULL);
	Destory(plq);
}
void Destory(Plist plq) {
	assert(plq != NULL);
	/*while (plq->front!=NULL) {
		struct Node* p = plq->front;
		plq->front = p->next;
		free(p);
	}
	plq->rear =plq->front= NULL;*/
	struct Node* p = plq->front;
	struct Node* q;
	plq->front = plq->rear = NULL;
	while (p!=NULL) {
		q = p->next;
		free(p);
		p = q;
	}
}
void Show(Plist plq) {
	assert(plq != NULL);
	for (struct Node* p = plq->front; p != NULL; p = p->next) {
		printf("%5d",p->data);
	}
	printf("\n");
}

测试文件

测试用例

#include<stdio.h>
#include"list_queue.h"
int main() {
	struct Head hd;
	Init(&hd);
	for (int i = 0; i < 20; i++) {
		Push(&hd,i+1);
	}
	Show(&hd);
	Pop(&hd);
	Pop(&hd);
	Pop(&hd);
	Show(&hd);
	printf("%d\n",Getlength(&hd));
	ELEM_TYPE temp;
	Top(&hd,&temp);
	printf("%d\n",temp);
	Clear(&hd);
	Show(&hd);
	Destory(&hd);
	return 0;
}