最简单的栈

旧城等待， 2021-11-11 08:14 326阅读 0赞

## 一。什么是栈（stack） ##

stack是一种特殊的线性表，是一种**只允许在表的一端进行插入操作或者是删除操作的线性表**（现实生活中的拿取盘子，在一叠盘子的上方选择拿和取）

**特点：后进先出**

## 二。栈的基本操作： ##

1.  初始化栈InitStack()，构造一个空栈
2.  判断一个是否为空IsEmpty(s)
3.  销毁张DestroyStack(s)
4.  进栈操作Push(s,x)
5.  退栈操作Pop(s)
6.  读取栈顶元素GetTop(s)

## 三。栈的基本操作具体代码分析： ##

#include<stdio.h>
    #include<stdlib.h>
    #define StackInitSize 100//给存取栈分配100个元素的储存空间 
    typedef int StackElemType;//使用typedef关键字，将StackElemType定义成int类型 
    typedef struct{
    	StackElemType data[StackInitSize];//栈的空间用一个数组来实现 
    	int top;//栈顶指针 
    }SeqStack;
    /* SeqStack是这个顺序栈结构体的名字，要定义一个顺序栈：SeqStack *s; 就可以了。
     
    1可以这么理解： 你定义了一个   人   的结构体，要声明李磊是人 ：人 *李磊； 
    2为什么要使用指针？  因为使用指针是元素地址联系在一起的，这样操作它的值，
    才会是本质的改变 
    3结构体里面是什么：是这个结构体需要具备的特性，
    就如你定义了 人 这个结构体，你按照你的需求可能需要在结构体中声明它的特性，
    如：人会说话，会思考。。。 
    
     */ 
    //顺序栈的初始化 
    SeqStack *InitStack(){
    	SeqStack *s;
    	s = (SeqStack *)malloc(sizeof(SeqStack));
    	if(s!=NULL){
    		s->top=-1;//默认栈为空栈时，栈顶指针指向-1 
    		return s;
    	}
    	else{
    		printf("没有足够的内存空间，申请失败");
    		exit(0); 
    	}
    }
    //判断顺序栈是否为空
    int IsEmpty(SeqStack *s){
    	return (s->top==-1)?1:0;//栈为空就返回1，否则返回0 
    } 
    //销毁栈
    void DestroyStack(SeqStack *s){
    	free(s);//释放顺序栈所占的空间 
    	printf("栈已经销毁");
    	return ; 
    } 
    //进栈操作
    void Push(SeqStack *s, StackElemType x){
    	if(s->top==StackInitSize){
    		printf("栈满了，栈发生上溢，程序运行终止\n");
    		exit(0);
    	}
    	else{
    		s->top++;//栈顶指针加1，指向新的栈顶 
    		s->data[s->top]=x;//将数据元素x压入栈 
    	}
    	return; 
    } 
    //退栈操作
    StackElemType Pop(SeqStack *s){
    	StackElemType temp;
    	if(IsEmpty(s)){
    		printf("栈空，发生下溢\n");
    		exit(0);
    	}
    	else{
    		temp = s->data[s->top];//将要退栈的元素的值给temp,一遍取出来 
    		s->top--;//栈顶指针减1，实现退栈 
    		return temp;//将退栈元素的值返回 
    	}
    }
    //读取栈顶元素
    StackElemType GetTop(SeqStack *s){
        if(IsEmpty(s)){
    		printf("栈空\n");
    		exit(0);
    	}
    	else{
    		return s->data[s->top];
    	}	
    } 
    
    
    //遍历栈中的所有元素并输出
    void display(SeqStack *s){
    	int p;
    	for(p=s->top;p>=0;p--){
    		printf("%d",s->data[p]);
    		printf("\b\b\n");//清除最后输出 
    	}
    } 
    int main(){
    	int i;
    	SeqStack *stack;
    	stack = InitStack();
    	for(i=1;i<10;i++){
    		Push(stack,i*i);
    	}
    	printf("将所有元素遍历一遍：\n");
    	display(stack);
    	printf("栈顶元素出栈");
    	Pop(stack);
    	printf("\n第二次栈顶元素出栈");
    	Pop(stack);
    	printf("\n将999压入栈：");
    	Push(stack,999);
    	printf("当前栈顶元素=%d\n",GetTop(stack));
    	display(stack);
    	printf("\n销毁栈！");
    	DestroyStack(stack);
    	return 0;
    }