栈————顺序栈和链式栈

栈

顺序栈

1、初始化顺序栈

2、判栈空

3、进栈

4、出栈

5、读栈顶元素

6、遍历

链式栈

1、初始化链式栈

2、断链式栈是否为空判

3、入栈(插入)

编辑编辑

4、出栈(删除)

5、读取栈顶元素

6、输出链式栈中各个节点的值（遍历）

栈

作为一种数据结构，是一种只能在同一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，最先进入的数据被压入栈底，最后进入的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）也就是后进先出（LIFO）或者先进后出（FILO）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

1.什么是栈，我们引用图例来帮助理解：

顺序栈

1、初始化顺序栈

SqStack *initStack(){SqStack *s; s = (SqStack*)malloc(sizeof(SqStack)); //划分内存空间if(!s){//判断内存空间的划分是否成功printf("空间不足\n");return NULL;}else{s->top = -1;//栈空以-1标记return s;  //返回栈}
}

2、判栈空

//判栈空
int stackEmpty(SqStack *s){	if(s->top==-1){         return 1;       }else{return 0;      }
}

3、进栈

//进栈 
int push(SqStack *s,datatype x){//入栈操作，s代表栈，x代表我们入栈的值 if(s->top==MAXSIZE-1){printf("\nThe squence stack is full!");return 0;}else{s->data[++s->top]=x;//指针先加一，在入栈 return 1; }		    
}

4、出栈

//出栈 
int pop(SqStack *s,datatype *x){//出栈操作，s代表栈，指针x代表输出的值，指针实参为地址if(stackEmpty(s))          //栈空,报错 {printf("\nThe squence stack is empty!");return 0;}else{*x=s->data[s->top--];//先出栈，指针在减一 return 1;}	    
}

5、读栈顶元素

//读栈顶元素 
int getTop(SqStack *s){if(stackEmpty(s))          //栈空,报错 {printf("\n栈是空的!");exit(1);}else{return s->data[s->top];} 
}

6、遍历

//遍历 
int display(SqStack *s){int i;printf("当前栈中的元素:\n");for(i = s->top; i >= 0; i--)printf("%3d", s->data[i]);printf("\n");return 0;
}

链式栈

链式栈是一种数据存储结构，可以通过单链表的方式来实现。

其优点在于它能够克服用数组实现的顺序栈空间利用率不高的特点，且除了存放每个栈元素的数据域，还需要额外分配指针空间用来存放指针的指针域。也就是有一个栈顶指针，指向了一个单链表，单链表存数据，栈顶指针取，放数据。

什么是链式栈?

链式栈，其实和单链表很相似，进栈可以理解为单链表的头插法，出栈可以理解为带头结点的单链表输出，只不过它的头结点就是我们的栈顶，栈顶用来输入和输出。