第 3 章 栈和队列（单链队列）

1. 背景说明

队列(queue)是一种先进先出(first in first out,缩为 FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。

2. 示例代码

1）status.h

/* DataStructure 预定义常量和类型头文件 */#ifndef STATUS_H
#define STATUS_H/* 函数结果状态码 */
#define TRUE 					1			/* 返回值为真 */
#define FALSE 					0			/* 返回值为假 */
#define RET_OK 					0			/* 返回值正确 */
#define INFEASIABLE    		   	2			/* 返回值未知 */
#define ERR_MEMORY     		   	3			/* 访问内存错 */
#define ERR_NULL_PTR   			4			/* 空指针错误 */
#define ERR_MEMORY_ALLOCATE		5			/* 内存分配错 */
#define ERR_NULL_STACK			6			/* 栈元素为空 */
#define ERR_PARA				7			/* 函数参数错 */
#define ERR_OPEN_FILE			8			/* 打开文件错 */
#define ERR_NULL_QUEUE			9			/* 队列为空错 */
typedef int Status;							/* Status 是函数的类型,其值是函数结果状态代码，如 OK 等 */
typedef int Bollean;						/* Boolean 是布尔类型,其值是 TRUE 或 FALSE */#endif // !STATUS_H

2) linkQueue.h

/* 单链队列 —— 队列的链式存储结构头文件 */#ifndef LINKQUEUE_H
#define LINKQUEUE_H#include "status.h"typedef int QElemType;typedef struct QNode {QElemType data;struct QNode *next;
} QNode, *QueuePtr;typedef struct {QueuePtr front, rear;
} LinkQueue;/* 构造一个空队列 Q */
Status InitQueue(LinkQueue *Q);/* 销毁队列 Q(无论空否均可) */
Status DestroyQueue(LinkQueue *Q);/* 将 Q 清为空队列 */
Status ClearQueue(LinkQueue *Q);/* 若 Q 为空队列,则返回 TRUE,否则返回 FALSE */
Bollean QueueEmpty(const LinkQueue *Q);/* 求队列的长度 */
int QueueLength(LinkQueue *Q);/* 若队列不空,则用 e 返回 Q 的队头元素,并返回 OK, 否则返回 ERROR */
Status GetQueueHead(const LinkQueue *Q, QElemType *e);/* 插入元素 e 为 Q 的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e);/* 若队列不空,删除 Q 的队头元素,用 e 返回其值,并返回 OK, 否则返回 ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e);/* 从队头到队尾依次对队列 Q 中每个元素调用函数 vi() */
Status QueueTraverse(const LinkQueue *Q, void(*vi)(QElemType));#endif // !LINKQUEUE_H

3) linkQueue.c

/* 单链队列 —— 队列的链式存储结构源文件 */#include "linkQueue.h"
#include <stdio.h>
#include <stdlib.h>/* 构造一个空队列 Q */
Status InitQueue(LinkQueue *Q)
{Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));if (!Q->front) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return ERR_MEMORY_ALLOCATE;}Q->front->next = NULL;return RET_OK;
}/* 销毁队列 Q(无论空否均可) */
Status DestroyQueue(LinkQueue *Q)
{while (Q->front) {Q->rear = Q->front->next;free(Q->front);Q->front = Q->rear;}return RET_OK;
}/* 将 Q 清为空队列 */
Status ClearQueue(LinkQueue *Q)
{Q->rear = Q->front;QueuePtr p = Q->front->next;Q->front->next = NULL;QueuePtr q = NULL;while (p) {q = p;p = p->next;free(q);}return RET_OK;
}/* 若 Q 为空队列,则返回 TRUE,否则返回 FALSE */
Bollean QueueEmpty(const LinkQueue *Q)
{return (Q->front == Q->rear) ? TRUE : FALSE;
}/* 求队列的长度 */
int QueueLength(LinkQueue *Q)
{int length = 0;QueuePtr p = Q->front;while (p != Q->rear) {++length;p = p->next;}return length;
}/* 若队列不空,则用 e 返回 Q 的队头元素(队头元素为 front 的下一个元素), 并返回 OK, 否则返回 ERROR */
Status GetQueueHead(const LinkQueue *Q, QElemType *e)
{if (Q->front == Q->rear) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_QUEUE);return ERR_NULL_QUEUE;}*e = Q->front->next->data;return RET_OK;
}static QueuePtr MakeNewQueueNode(QElemType e)
{QueuePtr p = (QueuePtr)malloc(sizeof(QNode));if (!p) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_MEMORY_ALLOCATE);return NULL;}p->data = e;p->next = NULL;return p;
}/* 插入元素 e 为 Q 的新的队尾元素 */
Status EnQueue(LinkQueue *Q, QElemType e)
{QueuePtr p = MakeNewQueueNode(e);if (p == NULL) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_PTR);return ERR_NULL_PTR;}Q->rear->next = p;Q->rear = p;return RET_OK;
}/* 若队列不空,删除 Q 的队头元素,用 e 返回其值,并返回 OK, 否则返回 ERROR */
Status DeQueue(LinkQueue *Q, QElemType *e)
{if (Q->front == Q->rear) {printf("FuncName: %-15s Line: %-5d ErrorCode: %-3d\n", __func__, __LINE__, ERR_NULL_QUEUE);return ERR_NULL_QUEUE;}QueuePtr p = Q->front->next;*e = p->data;Q->front->next = p->next;if (Q->rear == p) {Q->rear = Q->front;}free(p);return RET_OK;
}/* 从队头到队尾依次对队列 Q 中每个元素调用函数 vi() */
Status QueueTraverse(const LinkQueue *Q, void(*vi)(QElemType))
{QueuePtr p = Q->front->next;while (p) {vi(p->data);p = p->next;}return RET_OK;
}

4) auxiliary.h

/* 辅助函数头文件 */#ifndef AUXILIARY_H
#define AUXILIARY_H#include "linkQueue.h"/* 打印栈元素 */
void Print(QElemType e);#endif // !AUXILIARY_H

5) auxiliary.c

/* 辅助函数实现源文件 */#include "auxiliary.h"
#include <stdio.h>/* 打印栈元素 */
void Print(QElemType e)
{printf("%d ", e);
}

6) main.c

/* 入口程序源文件 */#include "status.h"
#include "auxiliary.h"
#include "linkQueue.h"
#include <stdio.h>int main(void)
{LinkQueue Q;Status ret = InitQueue(&Q);if (ret == RET_OK) {printf("Initialize queue success!\n");}printf("The queue is %s\n", (QueueEmpty(&Q) == TRUE) ? "empty" : "not empty");printf("The length of the queue is %d\n", QueueLength(&Q));EnQueue(&Q, -5);EnQueue(&Q, 5);EnQueue(&Q, 10);printf("After insert 3 elements, the length of the queue is %d\n", QueueLength(&Q));printf("The queue is %s\n", (QueueEmpty(&Q) == TRUE) ? "empty" : "not empty");printf("The elements of the queue is: ");QueueTraverse(&Q, Print);printf("\n");QElemType e;ret = GetQueueHead(&Q, &e);if (ret == RET_OK) {printf("The element of the head of the queue is %d\n", e);}DeQueue(&Q, &e);printf("Delete the element of the head of the queue %d\n", e);ret = GetQueueHead(&Q, &e);if (ret == RET_OK) {printf("The new element of the head of the queue is %d\n", e);}ClearQueue(&Q);printf("After clear the queue, Q.front = %p, Q.rear = %p, Q.front->next = %p\n",Q.front, Q.rear, Q.front->next);DestroyQueue(&Q);printf("After destroy the queue, Q.front = %p, Q.rear = %p\n", Q.front, Q.rear);return 0;
}

3. 输出示例

注意：free() 函数的作用并不仅仅把内存释放，还将指针置为空。