2.2堆栈

1.堆栈：具有一定操作约束的线性表

只在一端(栈顶，Top)做 插入、删除
插入数据:入栈(Push)
删除数据:出栈(Pop)
后入先出:Last In First Out(LIFO)

2.抽象数据描述
类型名称: 堆栈(Stack) 数据对象集:一个有0个或多个元素的有穷线性表。
操作集:长度为MaxSize的堆栈S Stack，堆栈元素item ElementType

1、Stack CreateStack( int MaxSize ): 生成空堆栈，其最大长度为MaxSize;
2、int IsFull( Stack S, int MaxSize ):判断堆栈S是否已满;
3、void Push( Stack S, ElementType item ):将元素item压入堆栈;
4、int IsEmpty ( Stack S ):判断堆栈S是否为空;
5、ElementType Pop( Stack S ):删除并返回栈顶元素;

3.存储实现

//#define MaxSize <储存数据元素的最大个数>
typedef struct {
ElementType Data[MaxSize];
int Top;
} Stack;

//入栈
void Push( Stack *PtrS, ElementType item ) {
if ( PtrS->Top == MaxSize-1 ) {
 printf(“堆栈满”); return;
}else {
PtrS->Data[++(PtrS->Top)] = item; 
return;
}
}

//出栈
ElementType Pop( Stack *PtrS ) {
if ( PtrS->Top == -1 ) {
 printf(“堆栈空”);
return error  ERROR是ElementType的特殊值，标志错误
} else 
 return ( PtrS->Data[(PtrS->Top)--];
}
}

4. 堆栈的链式存储实现
   栈的链式存储结构实际上就是一个单链表，叫做链栈。插入和删 除操作只能在链栈的栈顶进行

栈顶指针Top应该在链表的头部。

typedef struct Node{ 
ElementType Data;
struct Node *Next;
 } LinkStack;
LinkStack *Top;

//初始化
LinkStack *CreateStack()
{ /* 构建一个堆栈的头结点，返回指针 */
   LinkStack *S;
   S = malloc( sizeof(struct Node ));
   S->Next = NULL;
   return S;
}

//判断是否为空
int IsEmpty( LinkStack *S )
{ /*判断堆栈S是否为空，若为空函数返回整数 1，否则返回0 */
   return ( S->Next == NULL );
}

/入栈
void Push( ElementType item, LinkStack *S ) { /* 将元素item压入堆栈S */
struct Node *TmpCell;
TmpCell = malloc( sizeof( struct Node ) );
TmpCell->Element = item;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}

// 出栈
ElementType Pop( LinkStack *S ) { /* 删除并返回堆栈S的栈顶元素 */
   struct Node *FirstCell;
   ElementType TopElem;
 if( IsEmpty( S ) ) {
printf(“堆栈空”); return NULL; 
} else {
FirstCell = S->Next;
S->Next = FirstCell->Next; 
TopElem = FirstCell ->Element; free(FirstCell);
return TopElem;
} 
}

5.堆栈的应用

算术表达式的运算。
函数的调用， 以及递归实现。
深度优先搜索
回溯算法