在第 3 節 “遞歸”中我們已經對堆棧這種資料結構有了初步認識。堆棧是一組元素的集合，類似於數組，不同之處在於，數組可以按下標隨機訪問，這次訪問a[5]下次可以訪問a[1]，但是堆棧的訪問規則被限製為Push和Pop兩種操作，Push（入棧或壓棧）向棧頂添加元素，Pop（出棧或彈出）則取出當前棧頂的元素，也就是說，只能訪問棧頂元素而不能訪問棧中其它元素。如果所有元素的類型相同，堆棧的存儲也可以用數組來實現，訪問操作可以通過函數介面提供。看以下的示常式序。

#include <stdio.h>

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。運行過程圖示如下：

圖 12.1. 用堆棧實現倒序打印

數組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，後進先出）。我們也可以寫一個遞歸函數做倒序打印，利用函數調用的棧幀實現後進先出：

#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]);

對於數組來說確實沒必要搞這麼複雜，因為數組既可以從前向後訪問也可以從後向前訪問，甚至可以隨機訪問，但有些資料結構的訪問並沒有這麼自由，下一節你就會看到這樣的資料結構。