链队的实现

参考网站

MyQueue.h头文件：

#ifndef MYQUEUE_H
#define MYQUEUE_H

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

typedef int QElemType;

typedef struct QueueNode {
	struct QueueNode* next;
	QElemType val;
}QueueNode;

typedef struct Queue {
	QueueNode* head;
	QueueNode* tail;
}Queue;

int QueueInit(Queue* q);
int EnQueue(Queue* q, QElemType e);
QElemType DeQueue(Queue* q);
int QueueEmpty(Queue* q);
int QueueSize(Queue* q);
void QueueDestroy(Queue* q);
QElemType QueueFront(Queue* q);
QElemType QueueBack(Queue* q);

#endif

MyQueue.c源文件：

#include "My_Queue.h"

//初始化队列，使head指针和tail指针初始化为NULL
int QueueInit(Queue* q) {
	q->head = q->tail = NULL;
	return 0;
}

//入队元素。如果队为空（q->head==NULL），将head和NULL同时设为newNode。否则，将tail指针域指向newNode，然后将tail设置为newNode
int EnQueue(Queue* q, QElemType x) {
	assert(q);
	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	assert(newNode);
	newNode->val = x;
	newNode->next = NULL;
	if (q->tail == NULL) {
		q->tail = q->head = newNode;
	}
	else {
		q->tail->next = newNode;
		q->tail = newNode;
	}
	return 0;
}

//遍历队列，求出队列大小
int QueueSize(Queue* q) {
	QueueNode* cur = q->head;
	int size = 0;
	while (cur) {
		cur = cur->next;
		size++;
	}
	return size;
}

QElemType DeQueue(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	QElemType ret = 0;
	//如果队中只有一个元素，将head和tail都指向NULL
	if (q->head->next == NULL) {
		ret = q->head->val;
		free(q->head);
		q->head = q->tail = NULL;
	}
	//否则将head释放后，将其指向下一个元素
	else {
		ret = q->head->val;
		QueueNode* next = q->head->next;
		free(q->head);
		q->head = next;
	}
	return ret;
}

int QueueEmpty(Queue* q) {
	assert(q);
	return q->head == NULL;
}

void QueueDestroy(Queue* q) {
	QueueNode* cur = q->head;
	while (cur) {
		QueueNode* nextNode = cur->next;
		free(cur);
		cur = nextNode;
	}
	q->head = q->tail = NULL;
}

QElemType QueueFront(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->val;
}

QElemType QueueBack(Queue* q) {
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->val;
}

Test.c测试：

#include "My_Queue.h"
void TestQueue()
{
	Queue q;
	QueueInit(&q);
	EnQueue(&q, 1);
	EnQueue(&q, 2);
	EnQueue(&q, 3);
	EnQueue(&q, 4);
	
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		DeQueue(&q);
	}
	QueueDestroy(&q);
}

int main()
{
	TestQueue();
	return 0;
}