栈的动态分配顺序存储的基本操作（top为指针且指针指向栈顶元素）

￡神魔★判官ぃ 2022-03-25 05:07 174阅读 0赞

**top为指针且指针指向栈顶元素**  
![在这里插入图片描述][20190118211420346.png]  
**一、栈的动态分配顺序存储的结构定义：**

#include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    
    #define ERROR 0
    #define OK    1
    
    #define INIT_SIZE  10      /*栈的初始分配容量*/ 
    #define INCREMENT   2      /*栈的分配量增量*/ 
    
    typedef int  Status;
    typedef int  Elemtype;
    typedef struct SqStack{
    	Elemtype *base;       //栈底指针，始终指向栈底的位置 
    	Elemtype *top;        //栈定指针，可以指向栈顶元素下一个位置或栈顶元素 
    	int StackSize;        //栈的初始可使用分配存储量 
    }SqStack;

**二、栈的初始化：**

/*栈的动态分配顺序存储初始化,且top指针指向栈顶元素 */
    Status InitStack(SqStack *S)
    {
    	S->base=(Elemtype*)malloc(sizeof(Elemtype)*INIT_SIZE);
    	if(!S->base)
    	{
    		return ERROR;
    	}
    	S->top = S->base-1;            
    	S->StackSize=INIT_SIZE;
    	return OK;
    }

**三、入栈（压栈）操作：**

/*压栈操作*/ 
    void PushStack(SqStack *S,Elemtype e)
    {
    	
    	if( S->top - S->base + 1 >= S->StackSize )
    	{   /*栈满，追加空间*/
    		S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*sizeof(Elemtype));
    	    assert(S->base != NULL);                //判断是否扩容成功 
    		S->top = S->base + S->StackSize -1;    //修改栈顶指针 
    		S->StackSize=S->StackSize+INCREMENT;   //扩容后栈的存储容量 
    	}
    	
    	*++S->top=e;                               //将e入栈 
    }

**四、栈的当前长度：**

/*栈的当前长度*/
    Status StackLength(SqStack *S)
    {
    	if( S->top >= S->base -1 )
    	{
    		return S->top - S->base +1;
    	} 
    	else return ERROR;
    }

**五、获取栈顶元素：**

/*取栈顶元素*/
    Status GetTop(SqStack *S,Elemtype *e)
    {
    	if(S->top > S->base -1 )
    	{
    		*e = *S->top;
    		return OK;
    	}
    	else return ERROR;
    }

**六、判断栈是否为空栈：**

/*判断一个栈是否为空*/
    Status StackEmpty(SqStack *S)
    {
    	if( S->top == S->base - 1 ) return ERROR;
    	else return OK;
    }

**七、清空栈：**

/*清空栈*/
    void ClearStack(SqStack *S)
    {
    	S->top = S->base-1;
    }

**八、销毁栈：**

/*销毁栈*/
    void DestroyStack(SqStack *S)
    {
    	if(S != NULL)
    	{
    		free(S->base);
    		S->base = S->top=NULL;
    		S->StackSize=0;
    	}
    }

**九、出栈（弹栈）操作：**

/*弹栈操作*/
    Status PopStack(SqStack *S,Elemtype *e)
    {
    	if(S->top == S->base -1)    //判断是否栈空 
    	{
    		return ERROR;
    	}
    	*e = *S->top--;
    	return OK;
    }

**十、遍历栈：**

/*遍历栈*/ 
    void StackTraverse(SqStack S,void (*visit)(Elemtype))
    {
    	while(StackEmpty(&S))
    	{
    		visit(*S.base++);
    	}
    }
    void Print(Elemtype e)
    {
    	printf("%d ",e);
    }

**十一、主函数：**

int main()
    {
    	int i,value,length;
    	Elemtype e;
    	SqStack S;
    	
    	value=InitStack(&S);
    	if(value)
    	{
    		printf("初始化栈成功！\n\n");
    	}
    	else  
    	{
    		puts("error!");
    		return ERROR;
    	}
    	
    	for(i=1;i<12;i++)
    	PushStack(&S,i);
    	printf("栈中的元素为：\n");
    	StackTraverse(S,Print);
    	
    	value=StackEmpty(&S);
    	if(value)
    	{
    		printf("\n非空栈！\n");
    	}
    	else
    	{
    		printf("空栈！");
    	} 
    	length=StackLength(&S);
    	printf("当前长度为：%d\n",length);
    	
    	value=PopStack(&S,&e);
    	if(value)
    	{
    		printf("\n弹出的栈顶元素为：%d\n",e);
    	}
    	else
    	{
    		printf("空栈！\n");
    		return ERROR;
    	}	
    		
    	value=GetTop(&S,&e);
    	if(value)
    	{
    		printf("当前栈顶元素为：%d\n当前栈长度为：%d\n",e,StackLength(&S));
    	} 
    	else
    	{
    		printf("error! Stack Empty\n");
    		return ERROR;
    	} 
    	
    	ClearStack(&S);
    	printf("\n\n清空栈后：\n");
    	value=StackEmpty(&S);
    	if(value)
    	{
    		printf("\n非空栈！");
    	}
    	else
    	{
    		printf("空栈！\n");
    	} 
    	length=StackLength(&S);
    	printf("当前长度为：%d\n",length);
    	
    	DestroyStack(&S);
    	printf("\n销毁栈后：\n top=%u,base=%u,StackSize=%d",S.top,S.base,S.StackSize);
    	
    	return 0;
    }

十二、运行截图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]

[20190118211420346.png]: /images/20220325/7ef4478a0e804f9f8b3731adc3dedbd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220325/8c03d43017914e8c8f6168cd4a278880.png