使用C语言实现顺序栈

目录

1.顺序栈

2.顺序栈的相关操作

（1）数据结构定义

（2）初始化

（3）重新申请空间和判空操作

（4）入栈

​编辑

（5）出栈和获取栈顶元素

（6）主函数

---

1.顺序栈

栈：限定仅在表尾进行插入或删除操作的线性表。

顺序栈：顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。

 栈的应用：

使用栈将十进制转换为八进制

使用栈判断括号是否匹配

使用栈判断是否为回文串

注：栈的大小不可变，然而在我们的这个程序中当元素量达到MAXSIZE时，又重新申请空间，存储更多的元素（动态存储）。

2.顺序栈的相关操作

（1）数据结构定义

#include
#include
 
#define MAXSIZE 5
 
typedef int ElemType;
 
typedef struct SqStack {
	ElemType *data;
	int top;
	int Maxsize;
}SqStack;
 
//菜单栏
void MenuSqStack(){
	printf("----------1.入栈元素--------\n");
	printf("----------2.获取栈顶元素----\n");
	printf("----------3.弹出栈顶元素----\n");
	printf("----------4.重新初始化------\n");
	printf("----------5.退出操作--------\n");
} 

（2）初始化

//初始化 
void InitSqStack(SqStack&s){
	s.data=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));
	if(s.data==NULL){
		printf("申请空间失败!\n");
		return ;
	}
	s.Maxsize=MAXSIZE;
	s.top=0;
}

（3）重新申请空间和判空操作

//重新申请空间
void reMalloc(SqStack&s,int len){
	ElemType*newbase=(ElemType*)realloc(s.data,(s.Maxsize+len)*sizeof(ElemType));
	s.data=newbase;
	s.Maxsize=s.Maxsize+len; 
} 
 
//判空
bool StackEmpty(SqStack s){
	if(s.top==0){
		return true;
	}else{
		return false;
	}
}

（4）入栈

 

注：如果当前栈空间已满，那么重新申请空间（在原来的基础上加上申请的空间）。

//入栈
void Push(SqStack&s,ElemType e){
	if(s.top>=s.Maxsize){
		printf("栈已满!\n");
		int len=0;
		printf("请输入申请空间的大小: ");
		scanf("%d",&len);
		reMalloc(s,len);
		return ;
	}
	s.data[s.top]=e;
	s.top=s.top+1;
	printf("入栈成功!\n");
} 

 

（5）出栈和获取栈顶元素

//出栈
bool Pop(SqStack&s,ElemType&e){
	if(StackEmpty(s)){
		printf("栈已空!\n");
		return false;
	}
	s.top--;
	e=s.data[s.top];
	return true;
} 
//获取栈顶元素
void GetTopElem(SqStack s,ElemType&e){
	if(StackEmpty(s)){
		printf("栈已空!\n");
		return;
	}
	e=s.data[--s.top]; 
}

（6）主函数

int main(){
	SqStack s;
	ElemType e;
	InitSqStack(s);
	while(1){
		int flag=0;
		bool popFlag=false;
		MenuSqStack();
		printf("请输入操作: ");
		scanf("%d",&flag);
		switch(flag){
			case 1:
				printf("请输入元素(-1_end): ");
				scanf("%d",&e);
				while(e!=-1){
					Push(s,e);	
					printf("请输入元素(-1_end): ");
					scanf("%d",&e);
				}
				break;
			case 2:
				GetTopElem(s,e);
				printf("栈顶元素 = %d\n",e);
				break;
			case 3:
				popFlag=Pop(s,e);
				if(popFlag){
					printf("弹出栈顶元素 = %d\n",e);
				}
				break;
			case 4:
				InitSqStack(s);
				break;
			default:
				printf("结束操作\n");
		}
		if(flag==5){
			break;
		}
	}
	return 0;
}

测试