2. 堆栈

第 3 节 “递归”中我们已经对栈这种数据结构有了初步认识。堆栈是一组元素的集合,类似于数组,不同之处在于,数组可以按下标随机访问,这次访问a[5]下次可以访问a[1],但是堆栈的访问规则被限制为Push和Pop两种操作,Push(入栈或压栈)向栈顶添加元素,Pop(出栈或弹出)则取出当前栈顶的元素,也就是说,只能访问栈顶元素而不能访问栈中其它元素。如果所有元素的类型相同,堆栈的存储也可以用数组来实现,访问操作可以通过函数接口提供。看以下的示例程序。

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

#include <stdio.h>

char stack[512];
int top = 0;

void push(char c)
{
	stack[top] = c;
	top++;
}

char pop(void)
{
	top--;
	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。运行过程图示如下:

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

用堆栈实现倒序打印

数组stack是堆栈的存储空间,top用作数组stack的索引,注意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,后进先出)。我们也可以写一个递归函数来倒序打印,这是利用函数调用的栈帧实现后进先出的:

例 12.2. 用递归实现倒序打印

#include <stdio.h>
#define LEN 3

char buf[LEN]={'a', 'b', 'c'};

void print_backward(int pos)
{
     if(pos == LEN)
	  return;
     print_backward(pos+1);
     putchar(buf[pos]);
}

int main(void)
{
     print_backward(0);
     putchar('\n');
     
     return 0;
}

也许你会说,又是堆栈又是递归的,倒序打印一个数组犯得着这么大动干戈吗?写一个简单的循环不就行了:

for (i = LEN-1; i >= 0; i--)
	putchar(buf[i]);

对于数组来说确实没必要搞这么复杂,但对于某些数据结构就没这么简单了,下一节你就会看到这种思想的实际应用了。