栈的动态顺序存储表示

采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。
◆ 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。
◆ 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。
◆ 结点进栈：首先将数据元素保存到栈顶(top所指的当前位置)，然后执行top加1，使top指向栈顶的下一个存储位置;
◆ 结点出栈：首先执行top减1，使top指向栈顶元素的存储位置，然后将栈顶元素取出。
下图是一个动态栈的变化示意图。

基本操作的实现
1 栈的类型定义

#define  STACK_SIZE  100    /*  栈初始向量大小  */
#define STACKINCREMENT 10   /*  存储空间分配增量  */
#typedef  int  ElemType ;
typedef struct sqstack
{   ElemType  *bottom;     /*  栈不存在时值为NULL  */
ElemType  *top;      /*  栈顶指针  */
int   stacksize ;      /*  当前已分配空间，以元素为单位  */
}SqStack ;

2 栈的初始化

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

3 压栈(元素进栈)

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

4 弹栈(元素出栈)

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

最后

以上就是风趣狗为你收集整理的栈的动态顺序存储表示的全部内容，希望文章能够帮你解决栈的动态顺序存储表示所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。