第 12 章 栈与队列

12.1 数据结构的概念

数据结构是数据的组织方式，数据的组织方式包含了存储方式和访问方式这两层意思，二者是紧密联系的。把同一类型的数据组织成数组，或者把描述同一对象的各成员组织成结构体。例如：

数组的各元素是一个挨一个存储的，并且每个元素的大小相同，因此数组可以提供按下标访问的方式，结构体的各成员也是一个挨一个存储的，但是每个成员的大小不同，所以只能用.运算符加成员名来访问，而不能按下标访问。

 本章主要介绍栈和队列这两种数据结构以及它们的应用。从本章的应用实例可以看出，一个问题中数据的存储方式和访问方式就决定了解决问题可以采用什么样的算法，要设计一个算法就要同时设计相应的数据结构来支持这种算法。所以Pascal语言的设计者Niklaus Wirth提出：算法+数据结构=程序

12.2 堆栈

什么是堆栈？

堆栈是一组元素的集合，类似于数组，不同之处在于，数组可以按下标随机访问，这次访问a[5]下次可以访问a[1]，但是堆栈的访问规则被限制为Push和Pop两种操作，Push（入栈或压栈）向栈顶添加元素，Pop（出栈或弹出）则取出当前栈顶的元素，也就是说，只能访问栈顶元素而不能访问栈中其它元素。如果所有元素的类型相同，堆栈的存储也可以用数组来实现，访问操作可以通过函数接口提供。

例 12.1. 用堆栈实现倒序打印

#include 
char stack[512];
int top = 0;
void push(char c)
{
	stack[top++] = c;
}
char pop(void)
{
	return stack[--top];
}
int is_empty(void)
{
	return top == 0;
}
int main(void)
{
	push('a');
	push('b');
	push('c');
	while(!is_empty())
		putchar(pop());
	putchar('\n');
	return 0;
}

运行结果是cba。运行过程图示如下： 

数组stack是堆栈的存储空间，变量top总是保存数组中栈顶的下一个元素的下标，我们说“top总是指向栈顶的下一个元素”，或者把top叫做栈顶指针（Pointer）。在第 2 节 “插入排序”中介绍了Loop Invariant的概念，可以用它检验循环的正确性，这里的“top总是指向栈顶的下一个元素”其实也是一种Invariant，Push和Pop操作总是维持这个条件不变，这种Invariant描述的对象是一个数据结构而不是一个循环，在DbC中称为Class Invariant。Pop操作的语义是取出栈顶元素，但上例的实现其实并没有清除原来的栈顶元素，只是把top指针移动了一下，原来的栈顶元素仍然存在那里，这就足够了，因为此后通过Push和Pop操作不可能再访问到已经取出的元素，下次Push操作就会覆盖它。putchar函数的作用是把一个字符打印到屏幕上，和printf的%c作用相同。布尔函数is_empty的作用是防止Pop操作访问越界。这里我们预留了足够大的栈空间（512个元素），其实严格来说Push操作之前也应该检查栈是否满了。

在main函数中，入栈的顺序是'a'、'b'、'c'，而出栈打印的顺序却是'c'、'b'、'a'，最后入栈的'c'最早出来，因此堆栈这种数据结构的特点可以概括为LIFO（Last In First Out，后进先出）。