顺序栈的基本操作——C语言

阳光穿透心脏的1/2处 2022-09-16 08:40 157阅读 0赞

#include <stdio.h>
    #include <stdlib.h>
    
    #define Stack_Init_Size 10 // 初始化栈的最大长度
    #define StackIncrement 10 //若栈的空间不够大，需要增加的长度
    
    typedef int ElemType;
    typedef int Status;
    
    typedef struct { 
    	ElemType *base;	//栈底指针
    	ElemType *top;	// 栈顶指针
    	int stack_size;	//栈的最大长度
    } SqStack;
    
    // 初始化栈
    Status InitStack(SqStack *S) { 
    	//分配初始空间
    	S->base = (ElemType *)malloc(Stack_Init_Size * sizeof(ElemType));
    	if(!S->base) { 
    		exit(0);
    	}
    	S->top = S->base;	//栈顶和栈底相同
    	S->stack_size = Stack_Init_Size;	//栈的最大长度等于初始长度
    	return 1;
    }
    
    // 判断栈是否为空，只需要判断栈顶指针和栈底指针是否相等
    Status IsEmpty(SqStack *S) { 
    	printf("栈为空！\n");
    	return S->base == S->top;
    }
    
    
    // 获取栈的实际长度，栈顶减去栈底指针
    Status LengthStack(SqStack *S) { 
    	if(S->top == S->base) { 
    		printf("栈为空！\n");
    		return 0;
    	}
    	return (Status)(S->top - S->base);
    }
    
    //获取栈顶元素，参数e用来存放栈顶元素
    Status GetStack(SqStack *S,ElemType *e) { 
    	if(S->base == S->top) { 
    		return 0;
    	}
    	*e = *(S->top - 1);
    	return 1;
    }
    
    // 进栈，参数e是要进栈的元素
    Status EnStack(SqStack *S,ElemType e) { 
    	//若栈的最大长度不够用是，重新开辟增大长度
    	if(S->top - S->base >= S->stack_size) { 
    		S->base = (ElemType *)realloc(S->base,(S->stack_size + StackIncrement) *sizeof(ElemType));
    		if(!S->base) { 
    			return 0;
    		}
    		//栈顶指针为栈底指针加上栈之前最大长度
    		S->top = S->base + S->stack_size;
    		//栈当前最大长度等于栈之前的最大长度加上增加的长促
    		S->stack_size += StackIncrement;
    	}
    	*S->top ++ = e; // 先赋值，后栈顶指针上移
    	return 1;
    }
    
    // 出栈，参数e用来存放出栈的元素
    Status DeStack(SqStack *S,ElemType *e) { 
    	if(S->base == S->top) { 
    		return 0;
    	}
    	*e = *--S->top; //栈顶指针下移，后赋值
    	return 1;
    }
    
    // 销毁栈，释放栈空间，栈顶栈底指针为NULL，长度为0
    Status DestroyStack(SqStack *S) { 
    	S->top = S->base = NULL;
    	S->stack_size = 0;
    	return 1;
    }
    
    // 遍历栈，依次打印每个元素
    Status PrintStack(SqStack *S) { 
    	ElemType *p;
    	if(S->top == S->base) { 
    		printf("栈为空！\n");
    		return 0;
    	}
    	p = S->top;
    	//由栈顶依次向下遍历
    	while(p>S->base) { 
    		p--;
    		printf("%d ",*p);
    	}
    	printf("\n");
    	return 1;
    }
    
    int main() { 
    	SqStack q,*S;
    	S = &q;
    	int i,n,e;
    	printf("\n-----主菜单-----\n");
    	printf(" 1 初始化栈 \n");
    	printf(" 2 入队操作 \n");
    	printf(" 3 出队操作 \n");
    	printf(" 4 输出栈 \n");
    	printf(" 5 销毁栈 \n");
    	printf(" 6 求栈的长度 \n");
    	printf(" 7 退出程序 \n");
    	do { 
    		printf("请输入要进行的操作：");
    		scanf("%d",&n);
    		switch(n) { 
    			case 1:
    				InitStack(S) ;
    				break;
    			case 2:
    				printf("请输入要入栈的元素：e = ",e);
    				scanf("%d",&e);
    				EnStack(S,e);
    				PrintStack(S);
    				break;
    			case 3:
    				DeStack(S,&e);
    				printf("出队的元素：e = %d\n",e);
    				break;
    			case 4:
    				PrintStack(S);
    				break;
    			case 5:
    				DestroyStack(S);
    				break;
    			case 6:
    				printf("栈的长度为：%d",LengthStack(S));
    				break;
    		}
    	} while(n<=6);
    	return 0;
    }