数据结构与算法 3.3 栈ADT

3.3.1 栈模型

栈（stack）是限制插入与删除只能在一个位置进行的表。 该位置是表的末端，叫做栈顶（top）。对栈的基本操作有Push（进栈）和Pop（出栈），前者相当于插入，后者则是删除最后插入的元素。

+----------+    Pop(S)  |          | Push(X,S)  <-------  | Stack S  | <--------    Top(S)  |          |            +----------+		 图3-37 栈模型：通过Push向栈输入，通过Pop从栈输出

栈有时又叫做LIFO（后进先出）表。在图3-37中描述的模型只象征这Push是输入操作而Pop和Top是输出操作。普通的清空栈的操作与判断是否空栈的测试都是栈的操作指令系统的一部分，但是对栈所能够做的，基本也就是Push和Pop操作。

|            |       Top  |     2      |    ------->|------------|            |   {
   {4}}    |            |------------|            |   {
   {1}}    |            |------------|            |   {
   {3}}    |            +------------+       图3-38 栈模型：只有栈顶元素是可访问的

图3-38表示在进行若干操作后的一个抽象的栈。一般的模型是，存在某个元素位于栈顶，而该元素是唯一的可见元素。

3.3.2 栈的实现

由于栈是一个表，因此任何实现表的方法都可以实现栈。我们将给出两个流行的实现方法，一种方式是使用指针，而另一个方法则使用数组。

栈的链表实现

栈的第一种实现方法是使用单链表。我们通过在表顶端插入来实现Push，通过删除表顶端元素实现Pop。Top操作只是考查表顶端元素并返回它的值。

头文件

struct StackNode;typedef struct StackNode *PtrToStackNode;typedef PtrToStackNode Stack;// 判断是否空栈extern int IsEmptyStack(Stack);// 建栈extern Stack CreateStack(void);// 清空栈extern void MakeEmptyStack(Stack);// Push入栈extern void Push(int, Stack);// Pop出栈extern void Pop(Stack);// Top操作extern int Top(Stack);// 栈输出extern void PrintStack(Stack);

源文件

#include 
    
     #include "stack.h"#define FatalError( Str )   fprintf( stderr, "%s\n", Str ), exit( 1 )struct StackNode {	int Element;	PtrToStackNode Next;};/** * 判断是否空栈 * @param S * @return  */int IsEmptyStack(Stack S) {	return S->Next == NULL;}/** * 建栈 * @return  */Stack CreateStack(void) {	Stack S;		S = malloc(sizeof(struct StackNode));	S->Next = NULL;	MakeEmptyStack(S);	return S;} /** * 清空栈 * @param S */void MakeEmptyStack(Stack S) {	if (S == NULL) {		FatalError("Must use CreateStack first.");	} else {		while (! IsEmptyStack(S)) {			Pop(S);		}	}}/** * Push入栈 * @param X * @param S */void Push(int X, Stack S) {	PtrToStackNode TmpCell;	TmpCell = malloc(sizeof(struct StackNode));	if (TmpCell == NULL) {		FatalError("Out of space.");	}	TmpCell->Element = X;	TmpCell->Next = S->Next;	S->Next = TmpCell;}/** * Pop出栈 * @param S */void Pop(Stack S) {	PtrToStackNode FirstCell;		if (IsEmptyStack(S)) {		FatalError("Empty Stack.");	}	FirstCell = S->Next;	S->Next = S->Next->Next;	free(FirstCell);}/** * Top操作 * @param S * @return  */int Top(Stack S) {	if (IsEmptyStack(S)) {		FatalError("Empty Stack.");	}	return S->Next->Element;}/** * 输出栈 * @param  */void PrintStack(Stack S) {	if (IsEmptyStack(S)) {		FatalError("Empty Stack.");	}		PtrToStackNode P;	P = S->Next;	while(P != NULL) {		printf("|%d|%x|", P->Element, P->Next);		P = P->Next;				if (P != NULL) {			printf("-->");		}	}	printf("\n");}
    

调用示例

#include 
    
     #include 
     
      #include "ext/s15/stack.h"int main(int argc, char** argv) {	Stack S = CreateStack();	Push(3, S);	PrintStack(S);	Push(4, S);	PrintStack(S);	Push(5, S);	PrintStack(S);	Pop(S);	PrintStack(S);	return (EXIT_SUCCESS);}