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

一时失言乱红尘 2022-03-25 02:42 150阅读 0赞

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

#include<stdio.h>
    #include<stdlib.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;

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

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

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

/*压栈操作*/ 
    Status PushStack(SqStack *S,Elemtype e)
    {
    	
    	if( S->top - S->base >= S->StackSize )
    	{   /*栈满，追加空间*/
    		S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*sizeof(Elemtype));
    		if(!S->base)                           //扩容失败 
    		{
    			return ERROR;
    		}
    		S->top=S->StackSize+S->base;           //修改栈顶指针 
    		S->StackSize=S->StackSize+INCREMENT;   //扩容后栈的存储容量 
    	}
    	*(S->top)=e;                               //将e入栈 
    	S->top++;                                  //入栈后栈顶指针指向下一个栈顶元素的地址 
    	return OK;
    }

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

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

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

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

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

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

**七、清空栈：**

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

**八、销毁栈：**

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

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

/*弹栈操作*/
    Status PopStack(SqStack *S,Elemtype *e)
    {
    	if(S->top == S->base)    //判断是否栈空 
    	{
    		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<10;i++)
    	PushStack(&S,i);
    	printf("栈中的元素为：\n");
    	StackTraverse(S,Print);
    	
    	value=StackEmpty(&S);
    	if(value)printf("\n非空栈！");
    	else printf("空栈！");
    	length=StackLength(&S);
    	printf("当前长度为：%d\n",length);
    	
    	PopStack(&S,&e);
    	printf("\n弹出的栈顶元素为：%d\n",e);
    	GetTop(&S,&e);
    	printf("新的栈顶元素为：%d\n当前栈长度为：%d\n",e,StackLength(&S));
    	
    	ClearStack(&S);
    	printf("\n\n清空栈后：\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 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70]: /images/20220325/18231dab0ad84c19b10faa4a0d07eeb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNTUyNTMz_size_16_color_FFFFFF_t_70 1]: /images/20220325/67651febbdc04fdf84a4c5687653799c.png