顺序栈的9大基本操作C语言详解

淡淡的烟草味﹌ 2023-07-17 15:31 12阅读 0赞

1.  有些书，top=0时表示空栈，有些书top= -1时表示空栈，我这里参考严蔚敏老师一书top=0时为空栈。
2.  有些书，栈非空时top指向栈顶元素，有些书非空时top指向栈顶元素的下一个位置，我这里参考严蔚敏老师一书，top指向栈顶元素的下一个位置。

## 代码如下,编译环境vc6.0: ##

#include <stdio.h>
    #include <stdlib.h>
    #define STACK_INIT_SIZE 100 //存储空间初始分配量
    #define STACKINCREMENT 10 //存储空间分配的增量
    
    
    typedef struct
    { 
    	int* base;					//在构造之前和销毁之后，base的值为NULL
    	int* top;					//栈顶指针
    	int stacksize;				//当前已分配的存储空间，以元素为单位
    }SqStack;
    
    //**********************1、初始化**********************
    int InitStack(SqStack* s)
    { 
    	s->base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
    	if (!s->base)										 //动态内存申请失败
    		exit(0);
    	s->top = s->base;									//空找
    	s->stacksize = STACK_INIT_SIZE;						//栈的初始化大小
    	return 1;
    }
    
    //**********************2、销毁**********************
    int DestoryStack(SqStack* s)
    { 
    	s->top = NULL;
    	free(s->base);
    	s->base = NULL;
    	return 1;
    }
    
    //**********************3、清空**********************
    int ClearStack(SqStack* s)
    { 
    	s->top = s->base;
    	return 1;
    }
    
    //**********************4、判断是否非空**********************
    int StackEmpty(SqStack s)
    { 
    	if (s.top == s.base)                   //是空返回1
    		return 1;
    	else return 0;							//非空返回0
    }
    
    //**********************5、求栈元素个数**********************
    int stacklength(SqStack s)
    { 
    	if (s.top == s.base)
    		return 0;
    	else return s.top - s.base;          //顺序存储，指针差值，等于他们之间的元素个数差
    }
    
    //**********************6、获取栈顶元素**********************
    int GetTop(SqStack s, int* e)
    { 
    	if (s.top == s.base)        //栈空
    		return 0;
    	e = s.top - 1;
    	return 1;
    }
    
    //**********************7、入栈**********************
    int Push(SqStack* s, int e)
    { 
    	if (s->top - s->base == s->stacksize)    //栈满
    	{ 
    		s->base = (int*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(int));
    		if (s->base == NULL)
    			return 0;               //存储分配失败
    		s->top = s->base + s->stacksize; //重定位栈顶
    		s->stacksize += STACKINCREMENT;    //更改栈当前大小
    	}
    	*(s->top++) = e;
    	return 1;
    }
    
    //**********************8、出栈**********************
    int Pop(SqStack s, int* e)
    { 
    	if (s.top == s.base)			//栈空
    		return 0;
    	e = --s.top;                 //top指针下移后出栈
    	return 1;
    }
    
    //**********************9、遍历输出**********************
    int StackTraverse(SqStack s)
    { 
    	int* p = s.base;
    	if (s.base == NULL || s.top == s.base)    //没有初始化或栈空
    		return 0;
    	while (p > s.top)                         
    	{ 
    		printf("%-5d", *p);
    		p++;
    	}
    	return 1;
    }
    
    //**********************主函数测试**********************
    int main()
    { 
    	SqStack s;
    	int i,e, n;                        //e入栈元素,n入栈个数
    	if (InitStack(&s))
    		printf("初始化成功\n");
    	else printf("初始化失败\n");
    
    	printf("输入入栈元素个数\n");
    	scanf("%d", &n);
    	for (i = 0; i < n; i++)
    	{ 
    		printf("输入第%d个入栈元素值\n", i + 1);
    		scanf("%d", s.top++);
    	}
    
    	printf("栈的长度为%d\n", stacklength(s));
    	printf("请输入,入栈元素值\n");
    	scanf("%d", &e);
    	if (Push(&s, e))
    		printf("入栈成功\n");
    	else printf("入栈失败\n");
    	StackTraverse(s);
    
    	GetTop(s, &e);
    	printf("栈顶元素值为%d\n", e);
    
    	if (Pop(s, &e))
    		printf("出栈成功，元素值为%d\n", e);
    	else
    		printf("出栈失败\n");
    
    	if (ClearStack(&s))
    		printf("清空成功\n");
    
    	return 0;
    }

**测试案例：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTc5MTY2NQ_size_16_color_FFFFFF_t_70]: /images/20230528/b80185decb914b218bf13cc454b22b98.png