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

一、定义

采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。

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

◆ 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。

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

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

 1 栈的类型定义

 1 基本操作的实现
 2 
 3 1 栈的类型定义
 4 #define  STACK_SIZE  100    /*  栈初始向量大小  */
 5 #define STACKINCREMENT 10   /*  存储空间分配增量  */
 6 #typedef  int  ElemType ;
 7 typedef struct sqstack
 8 {   ElemType  *bottom;     /*  栈不存在时值为NULL  */
 9 ElemType  *top;      /*  栈顶指针  */
10 int   stacksize ;      /*  当前已分配空间，以元素为单位  */
11 }SqStack ;

2 栈的初始化

1 Status Init_Stack(void)
2 {   SqStack  S ;
3 S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType));
4 if (! S.bottom) return  ERROR;
5 S.top=S.bottom ;    /*  栈空时栈顶和栈底指针相同  */
6 S. stacksize=STACK_SIZE; 
7 return OK ;
8 }

3 压栈(元素进栈)

 1 Status push(SqStack S , ElemType  e)
 2    {  if  (S.top-S.bottom>=S. stacksize-1) 
 3 {   S.bottom=(ElemType *)realloc((S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType));   /*  栈满，追加存储空间  */
 4 if (! S.bottom)  return  ERROR; 
 5 S.top=S.bottom+S. stacksize ;
 6 S. stacksize+=STACKINCREMENT ;
 7 }  
 8 *S.top=e;  S.top++ ; /*  栈顶指针加1，e成为新的栈顶 */
 9 return OK;
10 }

4 弹栈(元素出栈)

1 Status pop( SqStack   S, ElemType  *e )      
2 /*弹出栈顶元素*/
3 {   if ( S.top== S.bottom )  
4 return ERROR ;       /*  栈空，返回失败标志  */
5 S.top-- ; e=*S. top ;  
6 return  OK ; 
7 }