数据结构（C语言）之——链队列

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

typedef char ElemType; //定义元素类型

typedef struct LinkNode { //链队列结点
	ElemType elem;
	struct LinkNode *next; 
}LinkNode;

typedef struct LinkQueue {
	LinkNode *front, *rear; //链队列的队首和队尾指针
	int length; //队列长度（结点个数）
}LinkQueue;

//创建空队列
LinkQueue* createQueue() {
	//初始时front和rear都指向头结点
	LinkQueue* q = (LinkQueue*)malloc(sizeof(LinkQueue));
	q->front = (LinkNode*)malloc(sizeof(LinkNode));
	q->front->next = NULL;
	q->rear = q->front;
	return q;
}

//释放队列内存
void releaseQueue(LinkQueue* q) {
	LinkNode* p;
	while(q->front != NULL) {
		p = q->front;
		q->front = q->front->next;
		free(p);
	}
	free(q);
}

//判断队空
bool isEmpty(LinkQueue* q) {
	return q->rear == q->front ? true : false;
}

//新元素入队
void inQueue(LinkQueue* q, ElemType e) {
	LinkNode* node = (LinkNode*)malloc(sizeof(LinkNode));
	node->elem = e;
	node->next = q->rear->next;
	q->rear->next = node; //新结点插入到rear之后
	q->rear = node; //修改表尾指针
}

//出队（带头结点）
ElemType outQueue(LinkQueue* q) {
	if(isEmpty(q)) return NULL;
	LinkNode* ptr = q->front->next;
	ElemType e = ptr->elem;
	q->front->next = ptr->next; //修改头结点的next指针
	if(q->rear == ptr) //此次是最后一个结点出队
		q->rear = q->front;
	free(ptr); //释放结点空间
	return e;
}

int main() {
	LinkQueue* q = createQueue();
 
	printf("输入入队序列（从左至右依次入队）：（如abcdefg）：");
	char inputStr[100];
	scanf("%s", &inputStr);
	for(int i=0; i<strlen(inputStr); i++) {
		inQueue(q, inputStr[i]);
	}
 
	ElemType e;
	printf("出队序列（从左至右依次出队）：");
	while(!isEmpty(q)) {
		e = outQueue(q);
		printf("%c", e);
	}
	printf("
");
 
	releaseQueue(q);
	return 0;
}

结果：

输入入队序列（从左至右依次入队）：（如abcdefg）：abcdefg
出队序列（从左至右依次出队）：abcdefg