第三章 栈和队列 ——栈的静态顺序存储表示（3）

一、定义

采用静态一维数组来存储栈。栈底固定不变的，而栈顶则随着进栈和退栈操作变化的，

◆ 栈底固定不变的；栈顶则随着进栈和退栈操作而变化，用一个整型变量top(称为栈顶指针)来指示当前栈顶位置。

◆ 用top=0表示栈空的初始状态，每次top指向栈顶在数组中的存储位置。

◆ 结点进栈：首先执行top加1，使top指向新的栈顶位置，然后将数据元素保存到栈顶(top所指的当前位置)。

◆ 结点出栈：首先把top指向的栈顶元素取出，然后执行top减1，使top指向新的栈顶位置。

若栈的数组有Maxsize个元素，则top=Maxsize-1时栈满。图3-3是一个大小为5的栈的变化示意图。

二、基本操作的实现

1 1   栈的类型定义
2 # define  MAX_STACK_SIZE  100      /*  栈向量大小  */
3 # typedef  int  ElemType ;
4 typedef struct  sqstack
5 {  ElemType   stack_array[MAX_STACK_SIZE] ;
6 int  top;
7 }SqStack ;

1 2 栈的初始化
2 SqStack Init_Stack(void)
3 {    SqStack  S ;
4 S.bottom=S.top=0 ;  return(S) ;
5 }

1 压栈(元素进栈)
2 Status push(SqStack S , ElemType  e)
3    /*  使数据元素e进栈成为新的栈顶  */
4 {  if  (S.top==MAX_STACK_SIZE-1) 
5 return  ERROR;      /*  栈满，返回错误标志    */
6 S.top++ ;      /*  栈顶指针加1  */
7 S.stack_array[S.top]=e  ;   /* e成为新的栈顶  */
8 return OK;        /*  压栈成功    */
9 }

1 弹栈(元素出栈)
2 Status  pop( SqStack   S, ElemType  *e )
3       /*弹出栈顶元素*/
4 {  if ( S.top==0 )
5 return ERROR ;       /*  栈空，返回错误标志    */
6 *e=S.stack_array[S.top] ;  
7 S.top-- ;  
8 return OK ;  
9 }

当栈满时做进栈运算必定产生空间溢出，简称“上溢”。上溢是一种出错状态，应设法避免。 当

栈空时做退栈运算也将产生溢出，简称“下溢”。下溢则可能是正常现象

，因为栈在使用时，其初态或终态都是空栈，所以下溢常用来作为控制转移的条件。