结构体模拟实现栈

比眉伴天荒 2022-05-28 13:06 211阅读 0赞

栈是很基本也很重要的数据结构，这里通过结构体模拟实现顺序栈，使用上节的顺序表实现，还有链栈（使用链表），本篇仅包含顺序栈的实现。我们知道C++的STL中有对栈的实现，直接提供了栈操作的所有函数，使用起来更简洁，但是作为一个好的Programmer，应该是个多面手，只是会用还是不行的。

栈的基本思想：先进后出

行为：初始化、判空、元素入栈、出栈、销毁栈、栈顶元素

入栈思想：top指针先加一再赋值

出栈思想：先取值再使top指针减一

代码如下：

#include<cstdio>
    #include<cstdlib>
    #define MaxSize 100
    #define Elemtype int
    using namespace std;
    
    typedef struct{
    	Elemtype data[MaxSize];
    	int top;
    }SqStack;
    //建立栈 
    SqStack createStack(){
    	SqStack *stack = (SqStack*)malloc(sizeof(SqStack));
    	return *stack;
    }
    //初始化栈
    bool InitStack(SqStack &S){
    	S.top = -1;
    	printf("成功初始化\n"); 
    }
    //判空
    bool StackEmpty(SqStack &S){
    	if(S.top == -1){
    		printf("栈为空\n"); 
    		return true;
    	}
    	printf("栈不为空\n");
    	return false;
    } 
    //进栈
    bool Push(SqStack &S){
    	int num;
    	printf("请输入要入栈的元素，按0退出：\n");
    	while(scanf("%d\n",&num),num){
    		if(S.top == MaxSize-1){
    			printf("栈空间已满\n"); 
    			return false;
    		}
    		S.data[++S.top] = num;
    		printf("%d成功入栈\n",num);
    	}
    	return true;
    }
    //出栈
    bool Pop(SqStack &S,Elemtype &val){
    	if(S.top==-1){
    		printf("栈为空，不能出栈操作\n");
    		return false;
    	}
    	val = S.data[S.top--];
    	printf("%d已成功出栈\n",val);
    	return true;
    } 
    //读取栈顶元素 
    bool GetTop(SqStack &S,Elemtype &val){
    	if(S.top == -1){
    		printf("栈为空，没有栈顶元素\n");
    		return false;
    	}
    	val = S.data[S.top];
    	printf("栈顶元素为%d\n",val);
    	return true;
    }
    bool ClearStack(SqStack &S){
    	S.top = -1; 
    	printf("很遗憾，不良栈已被和谐\n");
    	return true;
    }
    int main(){
    	//建立栈 
    	SqStack stack = createStack();
    	int x;
    	while(scanf("%d",&x),x){//x为0时推出循环
    		switch(x){
    			case 1:
    				InitStack(stack);//初始化 
    				break;
    			case 2:
    				StackEmpty(stack);//判空 
    				break;
    			case 3:
    				Push(stack);//入栈 
    				break;
    			case 4:
    				Pop(stack,x);//出栈 
    				break;
    			case 5:
    				GetTop(stack,x);//栈顶元素 
    				break;
    			default :
    				ClearStack(stack);//伪销毁 
    		} 
    	} 
    	printf("程序执行完毕\n");
    	return 0;
    }

程序截图：

![20180406135212800][]

貌似有点bug，入栈后不能及时显示成功入栈，不清楚是哪的问题，这就要向大家求助了QAQ~

[20180406135212800]: /images/20220528/10935ccd42df4c69bba321873f63fe9c.png