0、引入
通常来说，决定采用何种方式来存储数据是非常重要的，这样便于稍后检索数据时，数据会自动按照某种规定的顺序给出。用于检索数据的一种常用结构称为栈，它检索元素的顺序与存储元素的顺序相反。例如：一个记录函数调用轨迹的数据块。这些数据块称为活跃记录。有一个函数集{f1, f2, f3}，其中f1调用f2，f2调用f3，每次当函数调用发生时，程序就会分配空间来记录此激活信息。这些记录会一直存在直到相应的函数返回。因为函数调用与函数返回是一个相反的过程，所以活跃记录的获取与释放的顺序也是相反的。用于检索数据的另一种常用结构称为队列，它是按照元素到达的先后顺序来释放元素的。例如：我们可能有一堆事情要做，这时我们会按顺序做第一件事，接着第二件……直到最后一件事完成。栈和队列就是这样一种常见而简单的数据结构。
简单来说，
栈：按照后进先出(LIFO)的顺序存储和检索数据的高效数据结构，它检索元素的顺序与存储元素的顺序相反。
队列：按照先进先出(FIFO)的顺序存储和检索数据的高效数据结构，它按照存储元素的先后顺序检索元素。
1、栈的描述
栈的一个显著特点是它按照后进先出(LIFO)的方式存储和删除元素。这意味着，最后一个存入栈中的元素将会第一个被删除。我们可以把栈形象地看做一筒网球。当往筒里放球时，球从筒底向上排到筒口；当从筒里拿球时，球从筒口往下依次被拿出，直到筒底的球最后一个被拿出。并且，如果我们想拿到处于筒底的那个球，那么就必须把筒底那个球之上的球全部拿出才行。在计算机中，要把元素存储到栈中，就“压入”元素；要删除栈中的元素，就“弹出”元素(见下图)。有时候，可以通过检查栈顶元素(而不是实际删除它)来获取元素的某些信息。
2、栈的接口定义
stack_init
——————
void stack_init(Stack *stack, void (*destroy)(void *data));
返回值：无
描述：初始化由stack指定的栈。在对栈进行其他操作之前，必须调用初始化函数。参数destroy是一个函数指针，通过调用destroy来释放动态分配的内存空间。例如：如果一个栈包含用malloc动态分配内存的数据，那么此栈销毁时，destroy会调用fee来释放内存空间。当一个结构化数据包含若干动态分配内存的数据成员时，destroy应该指向一个用户自定义的函数来释放每个动态分配的数据成员和结构本身的内存空间。如果不需要释放栈中的数据，那么destroy应该指向NULL。
复杂度：O(1)
stack_destroy
——————
void stack_destroy(Stack *stack);
返回值：无
描述：销毁由stack指定的栈。在调用stack_destroy之后不再允许进行其他操作，除非再次调用stack_init。stack_destroy会删除栈中的所有元素，如果传递给stack_init的参数destroy不为NULL，每次移除一个元素时，都要调用destroy一次。
复杂度：O(n)，n为栈中元素的个数。
stack_push
——————
int stack_push(Stack *stack, const void *data);
返回值：如果元素入栈成功则返回0；否则返回-1。
描述：向stack指定的栈中压入一个元素。新元素包含一个指向data的指针，因此只要元素仍然在栈中，data引用的内存就一直有效。与data相关的存储空间将由函数的调用者来管理。
stack_pop
——————
int stack_pop(Stack *stack, void **data);
返回值：如果元素出栈成功则返回0；否则返回-1。
描述：从stack指定的栈中弹出一个元素。返回时，data指向已弹出元素中存储的数据。与data相关的存储空间将由函数的调用者来管理。
复杂度：O(1)
stack_peek
——————
void *stack_peek(const Stack *stack);
返回值：栈顶部元素中存储的数据；如果栈为空，则返回NULL。
描述：获取stack指定的栈顶部元素中存储的数据的宏。
复杂度：O(1)
stack_size
——————
int stack_size(const Stack *stack);
返回值：栈中元素的个数。
描述：获取stack指定的栈中元素个数的宏。
复杂度：O(1)
3、栈的实现与分析
结构Stack是栈的数据结构。实现栈的方法有很多，其中之一是用链表来实现。可以通过typedef List Stack这种简单的方法来做到这一点。这种方法不仅简单，而且可以使栈具有多态的特性。通俗地讲，多态通常是面向对象语言的一种特性，它允许某种类型的对象(变量)在使用时用其他类型的对象(变量)代替。这意味着，除了使用栈本身的操作外，还可以使用链表中的操作，这是因为栈本身就是一种链表，它与链表有相同的特性。因此，很多时候可以像使用链表一样使用栈。
这里有一个例子，假设要遍历一个栈中的元素，通过这种方式来显示栈中的元素或者判断元素是否属于这个栈。为此，首先获取链表的头元素list_head，然后用list_next遍历它。在这里仅仅使用了栈的操作，将元素以一个一个地弹出，检查元素，并将它们临时压入另外一个栈中。在处理完所有元素之后，要重新建立原始栈，可以将临时栈中的元素一个一个弹出，并将它们压入原始栈中。但我们要清楚，这种方法并不高效，且在实际的程序中也不常见。
// 栈抽象数据类型的头文件 /* stack.h */ #ifndef STACK_H #define STACK_H #include <stdlib.h> #include "list.h" /* Implement stacks as linked lists. */ typedef List Stack; /* Public Interface */ #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 // STACK_H // 栈抽象数据类型的实现 /* stack.c */ #include <stdlib.h> #include "list.h" #include "stack.h" /* stack_push */ int stack_push(Stack *stack, const void *data) { /* Push the data onto the stack. */ return list_ins_next(stack, NULL, data); } /* stack_pop */ int stack_pop(Stack *stack, void **data) { /* Pop the data off the stack. */ return list_rem_next(stack, NULL, data); }
stack_init
栈通过stack_init初始化，经过初始化的栈才能进行其他操作。因为栈本身就是一个链表，并且初始化过程相同，所以将stack_init定义成list_init。
stack_init的运行时复杂度与list_init相同，都是O(1)。
stack_destroy
栈通过stack_destroy销毁。因为栈本身就是一个链表，并且销毁过程相同，所以将stack_destroy定义成list_destroy。
stack_destroy的运行时复杂度与list_destroy相同，都是O(n)，n为栈包含元素的个数。
stack_push
栈通过stack_push往栈顶压入元素。stack_push调用list_ins_next方法来插入指向链表头部中data的元素。
stack_push的运行时复杂度与list_ins_next相同，都是O(1)。
stack_pop
栈通过stack_pop从栈顶弹出元素。stack_pop调用list_rem_next方法来删除链表的头元素，并将data指向已删除元素中的数据。
stack_pop的运行时复杂度与list_rem_next相同，都是O(1)。
stack_peek与stack_size
这是栈的两个宏定义，实现了栈的两种简单操作。stack_peek用来获取栈顶元素的信息而并不弹出栈顶元素；stack_size用来获取栈的大小。这两种操作都是通过访问Stack结构的成员来实现的。
由于访问结构的成员变量是一种简单的操作，只会消耗固定的运行时间，因此，这两种宏的运行时复杂度为O(1)。
4、队列的描述
队列的一个显著特征是它按照先进先出(FIFO)的方式存储和检索元素。这意味着首先存入队列的元素将首先被删除。我们可以把队列形象地看成在邮局排队办业务的一队人。当新的人一个一个排到队尾时，队伍在不停变化。当队伍最前面的人完成服务后，将首先离开，接着是下一个，再下一个……在计算机中，将一个元素放置到队尾，称为“入队”操作；将一个元素从队列头删除，称为“出队”操作(如下图)。我们可以通过检查队列头元素(而不是实际删除它)来获取元素的某些信息。
5、队列的接口定义
queue_init
——————
void queue_init(Queue *queue, void (*destroy)(void *data));
返回值：无
描述：初始化由queue指定的队列。在队列进行其他操作之前，必须调用初始化函数。参数destroy是一个函数指针，通过调用destroy来释放动态分配的内存空间。如果队列中的数据不需要释放，那么destroy应该指向NULL。
复杂度：O(1)
queue_destroy
——————
void queue_destroy(Queue *queue);
返回值：无
描述：销毁由queue指定的队列。在调用queue_destroy之后队列不允许进行其他操作，除非再次调用queue_init。queue_destroy会删除队列中的所有元素，同时如果queue_init中参数destroy不为NULL，会调用destroy释放成员所占用的内存空间。
复杂度：O(n)，n为队列中元素的个数。
queue_enqueue
——————
int queue_enqueue(Queue *queue, const void *data);
返回值：如果元素入队成功则返回0；否则返回-1。
描述：向queue指定的队列末尾中插入一个元素。新元素包含一个指向data的指针，因此只要元素仍然在于队列中，data引用的内存就一直有效。与data相关的存储空间将由函数的调用者来管理。
复杂度：O(1)
queue_dequeue
——————
int queue_dequeue(Queue *queue, void **data);
返回值：如果元素出队成功则返回0；否则返回-1。
描述：从queue指定的队列头部删除一个元素。返回时，data指向已出队元素中存储的数据。与data相关的存储空间将由函数的调用者来管理。
复杂度：O(1)
queue_peek
——————
void *queue_peek(const Queue *queue);
返回值：队列头部元素中存储的数据；如果队列为空，则返回NULL。
描述：获取由queue指定的队列头部元素中存储数据的宏。
复杂度：O(1)
queue_size
——————
返回值：队列中元素的个数。
描述：获取由queue指定的队列元素个数的宏。
复杂度：O(1)
6、队列的实现与分析
结构Queue是队列的数据结构。同栈一样，也用typedef List Queue来定义它。
// 队列抽象数据类型的头文件 /* queue.h */ #ifndef QUEUE_H #define QUEUE_H #include <stdlib.h> #include "list.h" /* Implementation queues as linked lists. */ typedef List Queue; /* Public Interface */ #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_H // 队列抽象数据类型的实现 /* 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_init
队列通过queue_init初始化，经过初始化的队列才能进行其他的操作。因为队列本身是一个链表，并且初始化过程相同，所以将queue_init定义成list_init。
queue_init的运行时复杂度与list_init相同，都是O(1)。
queue_destroy
队列通过queue_destroy销毁。因为队列本身就是一个链表，并且销毁过程相同，所以将queue_destroy定义成list_destroy。
queue_destroy的运行时复杂度与list_destroy相同，都是O(n)，n为队列包含元素的个数。
queue_enqueue
队列通过queue_enqueue往队列尾部插入元素。queue_enqueue调用list_ins_next方法来将指向data的元素插入链表尾部。
queue_enqueue的运行时复杂度与list_ins_next相同，都是O(1)。
queue_dequeue
队列通过queue_dequeue从队列头部删除元素。queue_dequeue调用list_rem_next方法来删除链表的头元素，并将data指向已删除元素中的数据。
queue_dequeue的运行时复杂度与list_rem_next相同，都是O(1)。
queue_peek与queue_size
这是队列的两个宏定义，实现队列的两种简单操作。queue_peek用来获取队列头元素的信息而并不使头元素出队；queue_size用来获取队列的大小。这两种操作都是通过访问Queue的结构成员来实现的。
由于访问成员变量是一种简单的操作，只消耗固定的运行时间，所以这两种宏的运行时复杂度为O(1)。
7、队列示例：事件处理
在事件驱动的应用中利用队列来处理事件是一种常见的方法。事件驱动的应用主要遵循实时事件发生的顺序来执行。例如，在Java、X或Windows中开发图形用户界面，应用程序的行为主要取决于键盘操作、鼠标移动等一些由用户触发的事件。其他一些事件驱动应用的例子还包括飞机或工厂设备中的控制系统等。
在很多事件驱动的应用中，事件可能随时发生，因此在能够处理这些已发生的事件之前，有序地存储和管理这些事件是非常重要的。由于系统处理事件的顺序基本上是按照事件发生的先后顺序进行的，因此队列是处理这种情况的较好方法。
下面的代码中列举了两个用于事件处理的函数：receive_event和process_event。两个函数都用于处理包含Event类型事件的队列。Event在event.h中定义，在此没有列举出来，因为每个人的Event结构体都不大相同。一个应用程序调用receive_event将一个将要处理的事件入队。有很多种方式可以用来告知应用程序将有事件要进行处理，最常用的是通过硬件中断的方式告知。当应用程序认为是时候来处理一个事件时它就会调用process_event函数。在process_event函数内部，事件从队列出队，并转交由应用程序指定的具体的调度函数处理。调度函数作为参数dispatch传递给process_event。使用调度函数目的是采取适当的行动来处理事件。一般有两种常用的调度方法：同步地处理事件，即在处理的事件未处理完成之前无法进行下一个操作；异步地处理事件，即在事件处理的过程中，还能另外启动进程来处理其他事件。通常异步处理事件效率更高，但在处理主从进程之间的关系时需要特别小心，以免冲突。
receive_event的运行时复杂度为O(1)，因为它只调用了复杂度为O(1)的队列操作queue_enqueue。process_event的运行时复杂度取决于它所调用的调度函数，process_event剩下部分运行固定的时间。
// 处理事件函数的实现 /* events.c */ #include <stdlib.h> #include <string.h> #include "event.h" #include "events.h" #include "queue.h" /* receive_event */ int receive_event(Queue *events, const Event *event) { Event *new_event; /* Allocate space for the event. */ if((new_event = (Event *)malloc(sizeof(Event))) == NULL) return -1; /* Make a copy of the event and enqueue it. */ memcpy(new_event, event, sizeof(Event)); if(queue_enqueue(events, new_event) != 0) return -1; return 0; } /* process_event */ int process_event(Queue *events, int (*dispatch)(Event *event)) { Event *event; if(queue_size(events) == 0) { /* Return that there are no events to dispatch. */ return -1; } else { if(queue_dequeue(events, (void **)&event) != 0) { /* Return that an event could not be retrieved. */ return -1; } else { /* Call a user-defined function to dispatch the event. */ dispatch(event); free(event); } } return 0; }
