递归、堆栈和队列
3.00/5 (2投票s)
本文旨在作为算法入门。
基本递归
本文旨在通过基本递归来解释算法的基础知识。稍后，我们将探讨数据结构如何与堆栈和队列相关联。然而，本文部分内容参考了 Kyle Loudon 的著作《精通 C 语言算法》。但总的来说，选择正确的算法可以解决问题，并且基本上是一种使用数据结构和抽象的计算模型。这些有助于通过列表数据、排序数据、堆叠数据、队列数据、链表上的列表数据等来分解数据。在编写算法来解决问题时，必须将问题分解为其组成部分。这就是递归重要的原因。递归允许某事物根据自身来定义。也就是说，递归函数会调用自身。在计算中，递归通过递归函数得到支持。每一次连续的调用都处理一组更精细的输入，使我们更接近问题的解决方案。想象一下锯断的树干上的年轮数量。它们基本形状相同，并且越来越小，以帮助科学家计算树的年龄。如果面临一个计算问题，那么开发人员需要弄清楚的一个重要选择是如何将原始问题分解成独立的子部分，然后编写函数来解决它们。代码示例将证明这一点。话虽如此，让我们探讨一下递归的工作原理，以展示如何以递归方式定义某些问题。
基本递归是一种允许将问题定义为自身越来越小的实例的原理。在计算中，我们通过使用递归函数来解决递归定义的问题，这些函数再次调用自身。首先，让我们考虑一个通常我们可能不会以递归方式思考的简单问题。假设我们想计算数字 n 的阶乘。数字 n 的阶乘，记作 n!，是 n 到 1 的所有数字的乘积。例如，4! = (4)(3)(2)(1)。计算此值的一种方法是循环遍历每个数字，并将其与前面数字的乘积相乘。这是一种迭代方法，可以更正式地定义为
n! = (n)(n - 1)(n - 2) . . . (1)
另一种看待这个问题的方式是定义 n! 为较小阶乘的乘积。为此，我们将 n! 定义为 n 乘以 (n-1) 的阶乘。当然，计算 (n-1)! 与 n! 是相同的问题，只是小了一点。如果我们然后将 (n-1)! 看作是 (n-1) 乘以 (n-2)!，然后是 (n-2) 乘以 (n-3)!，以此类推，直到 n = 1，我们最终会计算出 n！
下图说明了使用上述递归方法计算 4!。它还阐明了递归过程的两个基本阶段：缠绕（winding）和解缠（unwinding）。在缠绕阶段，每一次递归调用都通过进行额外的递归调用来延续递归。当某个调用达到终止条件时，缠绕阶段终止。终止条件定义了递归函数应返回而不是进行另一个递归调用的状态。例如，在计算 n 的阶乘时，终止条件是 n = 1 和 n = 0，因为函数只返回 1。每个递归函数至少必须有一个终止条件。否则，缠绕阶段将永远不会终止。缠绕阶段完成后，进入解缠阶段，在此阶段，函数的前实例以相反的顺序被重新访问。该阶段将一直进行，直到原始调用返回，此时递归过程完成。
尾部递归是一种递归形式，编译器能够为其生成优化代码。大多数现代编译器都能识别尾部转换，因此应该加以利用。下面是一个示例代码，其中包含用户定义的头文件，以例证阶乘计算中的递归原理
/**********************fact.h********************************/
#ifndef FACT_H
#define FACT_H
int fact(int n);
#endif
下一个用户定义的头文件
// File: facttail.h
#ifndef FACTTAIL_H
#define FACTTAIL_H
int facttail(int n, int a);
#endif
应将这些头文件复制并粘贴到您使用的任何版本的 VC++ 的 include 目录中。现在，这里是实现头文件中函数的那些文件。回想一下，这些函数是为了解决将被分解为“基本”递归和“尾部”递归的问题而编写的。
#include "fact.h"
int fact(int n) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n * fact(n - 1);
}
这是实现其相应头文件中定义的函数的第二个文件
#include "facttail.h"
int facttail(int n, int a) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
上述两个 C 源文件编译成对象文件。它们定义了两个用于处理分割问题部分的函数。当编译主文件时，它们将被链接到主文件中。我们将为此在命令行上执行，以获得更清晰的理解。下面是名为 _main.c_ 的主程序，其中包含主入口点。请注意，此文件在未与上述两个文件链接的情况下将无法编译。这些文件使用 Visual Studio 2008 _cl.exe_ 编译器的 /LD 开关（或项目属性页的命令行配置属性）进行编译。使用此开关意味着上述两个文件作为 DLL 进行编译，但作为对象文件链接到此主文件。
#include <stdio.h>
#include "fact.h"
#include "facttail.h"
int main(int argc, char **argv) {
int n;
for (n = 0; n <= 13; n++) {
fprintf(stdout, "%2d! recursive: %-10d ", n, fact(n));
fprintf(stdout, "tail recursive: %-10d\n", facttail(n, 1));
}
return 0;
}
好的。所以我们有两个用户定义的头文件，两个定义了这些头文件内容的源文件，以及一个在没有链接到这些定义文件的情况下无法编译的主程序。一个常见的问题是 _fprintf()_ 函数。_fprintf()_ 函数将格式化输出写入打开的文件。这是一个例子
#include <stdio.h>
#include <time.h>
int main(int argc, char *argv[])
{
FILE *fp_log;
time_t sec;
fp_log = fopen("example.log", "a");
if (fp_log != NULL)
{
time(&sec);
fprintf(fp_log, "%.24s Opened lg file.\n", ctime (&sec) );
}
return 0;
}
输出：检查 VS 2008 _cl.exe_ 编译器的命令行 _bin_ 目录，您会找到一个名为 _example.log_ 的文件。用记事本打开它，它会显示
Sat Mar 06 05:35:35 2010 Opened log file.
现在我们要编译这些算法文件。我们知道要将这些用户定义的头文件添加到 include 目录。请记住，在尝试任何编译之前，请运行 _vcvars32.bat_ 命令来设置环境。命令 _'type con > some_file.c'_ 会给你一个带有光标的空白屏幕。将这些文件复制并粘贴到该空白屏幕中，然后按 Control-Z 键盘组合键来终止文件并返回到提示符。
//C:\PROGRA~1\MICROS~1.0\VC\bin>type con > fact.c
#include "fact.h"
int fact(int n) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return 1;
else
return n * fact(n - 1);
}
^Z
/////////////////////////////////////////////////////////////
C:\PROGRA~1\MICROS~1.0\VC\bin>cl /LD fact.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
fact.c
/out:fact.dll
/dll
/implib:fact.lib
fact.obj
///////////////////////////////////////////////////////////////////
C:\PROGRA~1\MICROS~1.0\VC\bin>type con > facttail.c
#include "facttail.h"
int facttail(int n, int a) {
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
^Z
C:\PROGRA~1\MICROS~1.0\VC\bin>cl /LD facttail.c
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
facttail.c
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:facttail.dll
/dll
/implib:facttail.lib
facttail.obj
////////////////////////////////////////////////////////////////////////
C:\PROGRA~1\MICROS~1.0\VC\bin>type con > main.c
#include <stdio.h>
#include "fact.h"
#include "facttail.h"
int main(int argc, char **argv) {
int n;
for (n = 0; n <= 13; n++) {
fprintf(stdout, "%2d! recursive: %-10d ", n, fact(n));
fprintf(stdout, "tail recursive: %-10d\n", facttail(n, 1));
}
return 0;
}
^Z
C:\PROGRA~1\MICROS~1.0\VC\bin>cl main.c /link fact.obj facttail.obj
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
main.c
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:main.exe
fact.obj
facttail.obj
main.obj
C:\PROGRA~1\MICROS~1.0\VC\bin>main.exe
0! recursive: 1 tail recursive: 1
1! recursive: 1 tail recursive: 1
2! recursive: 2 tail recursive: 2
3! recursive: 6 tail recursive: 6
4! recursive: 24 tail recursive: 24
5! recursive: 120 tail recursive: 120
6! recursive: 720 tail recursive: 720
7! recursive: 5040 tail recursive: 5040
8! recursive: 40320 tail recursive: 40320
9! recursive: 362880 tail recursive: 362880
10! recursive: 3628800 tail recursive: 3628800
11! recursive: 39916800 tail recursive: 39916800
12! recursive: 479001600 tail recursive: 479001600
13! recursive: 1932053504 tail recursive: 1932053504
堆栈的缠绕和解缠
回到 4! 的简单示例。即，4 * 3 * 2 * 1 = 24。递归方法也阐明了两个基本阶段：缠绕和解缠。在缠绕阶段，每一次递归调用都通过进行额外的递归调用来延续递归。当某个调用达到终止条件时，缠绕阶段终止。终止条件定义了递归函数应返回而不是进行另一个递归调用的状态。这基本上是堆栈的解缠。当调用函数时，会分配一个堆栈，将函数的参数推送到堆栈上，同时函数执行任务。函数（理想情况下）完成任务，然后转向返回到堆栈上的返回地址。指令指针 (CS:IP) 寄存器指向紧跟在后面的指令。实际上，这是真正理解递归的一种方式：通过查看 C 语言中函数的执行方式。为此，了解 C 程序在内存中的组织方式会有所帮助。
程序内存分为四个段：代码（文本）区域、静态数据区域、堆和栈。每个段代表一块专门用于特定目的的内存。静态数据段用于存储全局和静态程序变量。数据段填充了已初始化的全局变量、字符串和其他在程序中使用的常量。尽管这些段是可写的，但它们的大小也是固定的。
堆段用于程序的其余变量。堆段的一个显著特点是它的大小不是固定的，这意味着它可以根据需要变大或变小。
堆栈段的大小也是可变的，并用作临时暂存器，用于在函数调用期间存储上下文。当程序调用函数时，该函数将拥有自己的一组传递变量，并且函数的代码将位于文本（或代码）段的不同内存位置。由于调用函数时上下文和 EIP 必须发生变化，因此堆栈用于记住所有传递的变量以及函数完成后 EIP 应该返回到哪里。
堆栈是一种经常使用的数据抽象结构。它具有先进后出 (FILO) 的排序方式，这意味着首先放入堆栈的项是最后从中取出的项。就像在一根末端有大结的线上穿珠子一样，在移除所有其他珠子之前，您无法取出第一个珠子。当一个项被放入堆栈时，称为推入 (pushing)，当一个项从堆栈中移除时，称为弹出 (popping)。
这段简短的代码首先声明了一个名为 _test_ 的函数，该函数有四个参数，所有参数都声明为整数：_a_、_b_、_c_ 和 _d_。函数的局部变量包括一个名为 _flag_ 的单个字符和一个名为 _buffer_ 的 10 个字符的缓冲区。程序运行时会执行 _main_ 函数，它只是调用 _test_ 函数。当 _our_function_ 从 _main_ 函数调用时，各种值会被推送到堆栈上以创建堆栈帧，如下所示。当调用 _our_function()_ 时，函数参数会以相反的顺序（因为它是 FILO）推送到堆栈上。函数的参数是 1、2、3 和 4，因此后续的推入指令将 4、3、2，最后是 1 推送到堆栈上。这些值对应于函数中的变量 _d_、_c_、_b_ 和 _a_。
#include <stdlib.h>
void our_function(int a, int b, int c, int d)
{
char flag;
char buffer[10];
}
void main()
{
our_function(1, 2, 3, 4);
}
总而言之，代码区域运行机器指令，这些指令在机器运行时执行。静态数据区域包含在程序生命周期中持久存在的数据，例如全局变量和局部静态变量。现在，当在 C 程序中调用函数时，会在堆栈上分配一个存储块来跟踪与调用相关的信息。每次调用称为一次激活。放置在堆栈上的存储块称为激活记录，或者称为堆栈帧。激活记录由五个区域组成：传入参数、返回值空间、用于评估表达式的临时存储、用于激活终止的已保存状态信息以及传出参数。传入参数是传递到激活的参数。传出参数是传递给激活中调用的函数的参数。一个激活记录的传出参数成为下一个放置在堆栈上的激活记录的传入参数。函数调用的激活记录会一直保留在堆栈上，直到该调用终止。现在考虑计算 4! 时会发生什么。
调用 _fact_ 会导致一个激活记录被放置在堆栈上，传入参数为 n = 4。由于此激活记录不满足函数的任何终止条件，因此 _fact_ 会以 n = 3 递归调用。这会在堆栈上放置 _fact_ 的另一个激活，但传入参数为 n = 3。此处，n = 3 也是第一个激活的传出参数，因为该激活调用了第二个激活。该过程持续进行，直到 n = 1，此时遇到终止条件，_fact_ 返回 1。一旦 n = 1 的激活终止，n = 2 激活中的递归表达式将被计算为 (2)(1) = 2。因此，n = 3 激活中的递归表达式返回 6。最后，n = 4 激活中的递归表达式计算为 (4)(6) = 24，n = 4 激活终止，返回值为 24。此时，函数已从原始调用返回，递归过程完成。
堆栈和队列
现在，为了证明概念，我们将探讨堆栈和队列。读者可能会想，我为什么不使用 C#、Java、Visual C++ 或 ISO C++ 这样的语言？原因在于 C 是编写操作系统的第一门语言。它是由 Dennis Ritchie 和 Brain Kernaum 编写的，作为 B 语言的解决方案。C 语言不是在互联网时代编写的，因此不被认为是安全威胁。它是为了编写 UNIX 系统，以及后来的 Windows 系统而编写的。C 语言直接编译为机器级代码，输出一个对象（模块）文件（或资源文件）。头文件由预定义的函数组成，其中函数的类型与头文件的名称类型相同。C 库是静态的，链接器将对象文件链接到源代码文件，以通过将这些预定义的函数复制到可执行文件中来构建可执行文件。如果这些函数不是预定义的，那么它们的定义将涉及通过硬件 I/O 端口进行字符串提取过程，这个过程比编写程序和编译要花费更长的时间。但如果能够理解算法的基本原理，那么它们就可以转移到像 C# 这样的更强大的语言中进行严肃的问题解决。它们还可以产生使用强大的 .NET 图形界面的解决方案。
回想一下激活记录。之前我们使用了数据结构这个术语。存储数据很重要，以便在以后检索时，它能自动以某种规定的顺序呈现。检索数据的一种方式是按照与存储数据相反的顺序。例如，考虑程序为跟踪运行时函数调用而维护的数据块。正如我们刚刚看到的，这些块称为激活记录。对于一组函数 {f1, f2, f3}，其中 f1 调用 f2，f2 调用 f3，程序会在每次调用其中一个函数时分配一个激活记录。每个记录会保留到其函数返回为止。由于函数返回的顺序与其被调用的顺序相反，因此激活记录的检索和释放顺序也与其分配顺序相反。另一种常用的数据检索方式是按照与存储数据相同的顺序。例如，这可能对一堆要做的事情有用；我们通常希望先做第一件事，最后做最后一件事。堆栈和队列是简单的数据结构，它们有助于以预定义的方式存储数据，以满足需求。堆栈是用于以先进后出 (LIFO) 的方式存储和检索数据的抽象数据结构。队列是用于以先进先出 (FIFO) 的顺序存储数据结构的数据结构。
这里有一些代码，应该与对堆栈的推入和弹出函数的解释相关联。有两个用户定义的头文件 _stack.h_ 和 _list.h_，以及三个源文件：_stack.c_、_list.c_ 和 _main_stack.c_。最后一个文件包含主入口点。前两个文件必须作为模块进行编译，但它们在编译 _main_stack.c_ 文件之前相互依赖。这些头文件可以复制并粘贴到您使用的任何版本的 Visual Studio 的 include 目录中
// file: list.h
#ifndef LIST_H
#define LIST_H
#include <stdlib.h>
typedef struct ListElmt_ {
void *data;
struct ListElmt_ *next;
} ListElmt;
typedef struct List_ {
int size;
int (*match)(const void *key1, const void *key2);
void (*destroy)(void *data);
ListElmt *head;
ListElmt *tail;
} List;
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list)->size)
#define list_head(list) ((list)->head)
#define list_tail(list) ((list)->tail)
#define list_is_head(list, element) ((element) == (list)->head ? 1 : 0)
#define list_is_tail(element) ((element)->next == NULL ? 1 : 0)
#define list_data(element) ((element)->data)
#define list_next(element) ((element)->next)
#endif
这是第二个头文件，_stack.c_
//File: stack.h
#ifndef STACK_H
#define STACK_H
#include <stdlib.h>
#include "list.h"
typedef List Stack;
#define stack_init list_init
#define stack_destroy list_destroy
int stack_push(Stack *stack, const void *data);
int stack_pop(Stack *stack, void **data);
#define stack_peek(stack) ((stack)->head == NULL ? NULL : (stack)->head->data)
#define stack_size list_size
#endif
其他头文件随任何版本的 Visual C++ 提供。这是 _list.c_ 文件
#include <string.h>
#include <stdlib.h>
#include "list.h"
void list_init(List *list, void (*destroy)(void *data)) {
//Initialize the list.
list->size = 0;
list->destroy = destroy;
list->head = NULL;
list->tail = NULL;
return;
}
void list_destroy(List *list) {
void *data;
while (list_size(list) > 0) {
if (list_rem_next(list, NULL, (void **)&data) == 0 &&
list->destroy != NULL) {
list->destroy(data);
}
}
memset(list, 0, sizeof(List));
return;
}
int list_ins_next(List *list, ListElmt *element, const void *data) {
ListElmt *new_element;
if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
return -1;
new_element->data = (void *)data;
if (element == NULL) {
if (list_size(list) == 0)
list->tail = new_element;
new_element->next = list->head;
list->head = new_element;
}
else {
if (element->next == NULL)
list->tail = new_element;
new_element->next = element->next;
element->next = new_element;
}
list->size++;
return 0;
}
int list_rem_next(List *list, ListElmt *element, void **data) {
ListElmt *old_element;
if (list_size(list) == 0)
return -1;
if (element == NULL) {
*data = list->head->data;
old_element = list->head;
list->head = list->head->next;
if (list_size(list) == 1)
list->tail = NULL;
}
else {
if (element->next == NULL)
return -1;
*data = element->next->data;
old_element = element->next;
element->next = element->next->next;
if (element->next == NULL)
list->tail = element;
}
free(old_element);
list->size--;
return 0;
}
此文件编译如下：_>cl /LD list.c_。现在是 _stack.c_ 文件
#include <stdlib.h>
#include "list.h"
#include "stack.h"
int stack_push(Stack *stack, const void *data) {
return list_ins_next(stack, NULL, data);
}
int stack_pop(Stack *stack, void **data) {
return list_rem_next(stack, NULL, data);
}
此文件 _stack.c_ 作为模块（对象文件）进行编译，其依赖项为 _list.obj_。为什么？结构 _Stack_ 是堆栈数据结构。实现堆栈的一种方法是将其用作链表。一种简单的方法是使用 _typedef_ 将 _Stack_ 定义为 _List_。除了简单性之外，使用 _typedef_ 还有一个好处是使堆栈在某种程度上具有多态性。非正式地说，多态性是通常与面向对象语言相关的原理，它允许一种类型的对象（变量）用作另一种类型的替代品。这意味着，因为堆栈是一个链表，因此它具有与链表相同的属性，我们可以对其使用链表操作以及堆栈的操作。因此，当我们需要时，堆栈可以表现得像一个链表。下面是编译
c:\Program Files\Microsoft Visual Studio 9.0\VC\bin>cl /LD stack.c /link list.obj
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 15.00.30729.01 for 80x86
Copyright (C) Microsoft Corporation. All rights reserved.
stack.c
/out:stack.dll
/dll
/implib:stack.lib
list.obj
stack.obj
这里是主文件 _main_stack.c_。它被分解成使用模块（对象，函数定义）文件中定义的函数来解决问题或执行计算的部分
//File: main_stack.c
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "stack.h"
static void print_stack(const Stack *stack) {
ListElmt *element;
int *data,
size,
i;
fprintf(stdout, "Stack size is %d\n", size = stack_size(stack));
i = 0;
element = list_head(stack);
while (i < size) {
data = list_data(element);
fprintf(stdout, "stack[%03d]=%03d\n", i, *data);
element = list_next(element);
i++;
}
return;
}
int main(int argc, char **argv) {
Stack stack;
int *data,
i;
stack_init(&stack, free);
fprintf(stdout, "Pushing 10 elements\n");
for (i = 0; i < 10; i++) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = i + 1;
if (stack_push(&stack, data) != 0)
return 1;
}
print_stack(&stack);
fprintf(stdout, "Popping 5 elements\n");
for (i = 0; i < 5; i++) {
if (stack_pop(&stack, (void **)&data) == 0)
free(data);
else
return 1;
}
print_stack(&stack);
fprintf(stdout, "Pushing 100 and 200\n");
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = 100;
if (stack_push(&stack, data) != 0)
return 1;
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = 200;
if (stack_push(&stack, data) != 0)
return 1;
print_stack(&stack);
if ((data = stack_peek(&stack)) != NULL)
fprintf(stdout, "Peeking at the top element...Value=%03d\n", *data);
else
fprintf(stdout, "Peeking at the top element...Value=NULL\n");
print_stack(&stack);
fprintf(stdout, "Popping all elements\n");
while (stack_size(&stack) > 0) {
if (stack_pop(&stack, (void **)&data) == 0)
free(data);
}
if ((data = stack_peek(&stack)) != NULL)
fprintf(stdout, "Peeking at an empty stack...Value=%03d\n", *data);
else
fprintf(stdout, "Peeking at an empty stack...Value=NULL\n");
print_stack(&stack);
fprintf(stdout, "Destroying the stack\n");
stack_destroy(&stack);
return 0;
}
如果我们使用命令行，这是编译这些文件的方式
c:\Program Files\Microsoft Visual Studio 9.0\VC\bin>cl stack.c /link stacks.obj list.obj
main_stack.c
Microsoft (R) Incremental Linker Version 9.00.30729.01
Copyright (C) Microsoft Corporation. All rights reserved.
/out:main_stack.exe
stacks.obj
list.obj
main_stack.obj
Pushing 10 elements
Stack size is 10
stack[000]=010
stack[001]=009
stack[002]=008
stack[003]=007
stack[004]=006
stack[005]=005
stack[006]=004
stack[007]=003
stack[008]=002
stack[009]=001
Popping 5 elements
Stack size is 5
stack[000]=005
stack[001]=004
stack[002]=003
stack[003]=002
stack[004]=001
Pushing 100 and 200
Stack size is 7
stack[000]=200
stack[001]=100
stack[002]=005
stack[003]=004
stack[004]=003
stack[005]=002
stack[006]=001
Peeking at the top element...Value=200
Stack size is 7
stack[000]=200
stack[001]=100
stack[002]=005
stack[003]=004
stack[004]=003
stack[005]=002
stack[006]=001
Popping all elements
Peeking at an empty stack...Value=NULL
Stack size is 0
Destroying the stack
要理解队列，最有效的方法是想象一下商店里的排队。随着队伍变长，顾客会在队尾加入。当收银员完成与一位顾客的服务并空闲时，队列的队首顾客会继续。当我们向队尾添加一名顾客时，我们称之为“入队”(enqueue)。当我们从队首移除一名顾客时，我们称之为“出队”(dequeue)。为了编写队列，我们使用 _list.h_ 和 _list.c_ 文件，以及另外三个文件：_queue.h_ 文件、_queue.c_ 文件和 _main_queue.c_ 文件
File:// queue.h
#ifndef QUEUE_H
#define QUEUE_H
#include <stdlib.h>
#include "list.h"
typedef List Queue;
#define queue_init list_init
#define queue_destroy list_destroy
int queue_enqueue(Queue *queue, const void *data);
int queue_dequeue(Queue *queue, void **data);
#define queue_peek(queue) ((queue)->head == NULL ? NULL : (queue)->head->data)
#define queue_size list_size
#endif
这是 _queue.c_ 文件
#include <stdlib.h>
#include "list.h"
#include "queue.h"
/*****************************************************************************
* *
* ----------------------------- queue_enqueue ---------------------------- *
* *
*****************************************************************************/
int queue_enqueue(Queue *queue, const void *data) {
/*****************************************************************************
* *
* Enqueue the data. *
* *
*****************************************************************************/
return list_ins_next(queue, list_tail(queue), data);
}
/*****************************************************************************
* *
* ----------------------------- queue_dequeue ---------------------------- *
* *
*****************************************************************************/
int queue_dequeue(Queue *queue, void **data) {
/*****************************************************************************
* *
* Dequeue the data. *
* *
*****************************************************************************/
return list_rem_next(queue, NULL, data);
}
文件 _queue.c_ 再次作为模块或对象文件进行编译。当然，它是使用 _list.obj_ 文件作为依赖项来完成的。之后，我们需要编写代码来执行在头文件中定义并在 C 源文件（原型）中声明的函数
cl /LD queue.c /link list.obj
现在，在构建了这些模块之后，我们可以编译 _main_queue.c_ 文件。这是 _main_queue.c_ 文件
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
#include "queue.h"
/*****************************************************************************
* *
* ------------------------------ print_queue ----------------------------- *
* *
*****************************************************************************/
static void print_queue(const Queue *queue) {
ListElmt *element;
int *data,
size,
i;
/*****************************************************************************
* *
* Display the queue. *
* *
*****************************************************************************/
fprintf(stdout, "Queue size is %d\n", size = queue_size(queue));
i = 0;
element = list_head(queue);
while (i < size) {
data = list_data(element);
fprintf(stdout, "queue[%03d]=%03d\n", i, *data);
element = list_next(element);
i++;
}
return;
}
/*****************************************************************************
* *
* --------------------------------- main --------------------------------- *
* *
*****************************************************************************/
int main(int argc, char **argv) {
Queue queue;
int *data,
i;
/*****************************************************************************
* *
* Initialize the queue. *
* *
*****************************************************************************/
queue_init(&queue, free);
/*****************************************************************************
* *
* Perform some queue operations. *
* *
*****************************************************************************/
fprintf(stdout, "Enqueuing 10 elements\n");
for (i = 0; i < 10; i++) {
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = i + 1;
if (queue_enqueue(&queue, data) != 0)
return 1;
}
print_queue(&queue);
fprintf(stdout, "Dequeuing 5 elements\n");
for (i = 0; i < 5; i++) {
if (queue_dequeue(&queue, (void **)&data) == 0)
free(data);
else
return 1;
}
print_queue(&queue);
fprintf(stdout, "Enqueuing 100 and 200\n");
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = 100;
if (queue_enqueue(&queue, data) != 0)
return 1;
if ((data = (int *)malloc(sizeof(int))) == NULL)
return 1;
*data = 200;
if (queue_enqueue(&queue, data) != 0)
return 1;
print_queue(&queue);
if ((data = queue_peek(&queue)) != NULL)
fprintf(stdout, "Peeking at the head element...Value=%03d\n", *data);
else
fprintf(stdout, "Peeking at the head element...Value=NULL\n");
print_queue(&queue);
fprintf(stdout, "Dequeuing all elements\n");
while (queue_size(&queue) > 0) {
if (queue_dequeue(&queue, (void **)&data) == 0)
free(data);
}
if ((data = queue_peek(&queue)) != NULL)
fprintf(stdout, "Peeking at an empty queue...Value=%03d\n", *data);
else
fprintf(stdout, "Peeking at an empty queue...Value=NULL\n");
/*****************************************************************************
* *
* Destroy the queue. *
* *
*****************************************************************************/
fprintf(stdout, "Destroying the queue\n");
queue_destroy(&queue);
return 0;
}
以下是编译这些文件的方式：_cl.exe main_queue /link list.obj queue.obj_。
输出如下
Enqueuing 10 elements
Queue size is 10
queue[000]=001
queue[001]=002
queue[002]=003
queue[003]=004
queue[004]=005
queue[005]=006
queue[006]=007
queue[007]=008
queue[008]=009
queue[009]=010
Dequeuing 5 elements
Queue size is 5
queue[000]=006
queue[001]=007
queue[002]=008
queue[003]=009
queue[004]=010
Enqueuing 100 and 200
Queue size is 7
queue[000]=006
queue[001]=007
queue[002]=008
queue[003]=009
queue[004]=010
queue[005]=100
queue[006]=200
Peeking at the head element...Value=006
Queue size is 7
queue[000]=006
queue[001]=007
queue[002]=008
queue[003]=009
queue[004]=010
queue[005]=100
queue[006]=200
Dequeuing all elements
Peeking at an empty queue...Value=NULL
Destroying the queue