栈
栈就像弹夹一样，例如我们浏览网页时时常会用到回退这个选项，而回退不是正好对应的就是栈结构，当我们打开一个新的网页时就是将一颗新子弹压进弹夹，当我们使用回退功能时就是将最外面的那颗子弹取出，这样读取的就是之前的网页了。
进栈和出栈
- 向栈内添加元素，此过程叫做“
进栈”; - 从栈内提取出指定元素，此过程被称为出栈;
栈的具体实现
栈分为两类顺序栈和链栈：
- 顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；
- 链栈：采用链式存储结构实现栈结构；
顺序栈
顺序栈用通俗的方法理解就是用顺序表的方法来实现栈的存储结构。
如果你仔细观察顺序表和栈结构你就会发现，他们的存在高度相似，只不过栈对数据的存取过程有特殊限制，而顺序表没有。
在顺序表设定一个实时指向栈顶元素的变量(一般命名为top),top的初始值为-1，表示栈中没有存储任何数据元素，也就是常说的“空栈”一旦有数据进入，则top就做+1操作；反之，如果元素出栈则执行top-1的操作。
入栈
比如我们模拟一下向栈中存储{1,2,3,4}的过程，最初栈是空的“空栈”，top=-1
我们向栈中添加元素1，我们默认数组下标为0一端表示栈底，因此元素1被存储在数组a[0]处，同时top值+1。
采用以上的方式，依次将剩下的元素存入，最后top的值等于3；
按照这种理解方式我们可以将这种方式用代码实现出来：
//元素elem进栈，a为数组，top值为当前栈的栈顶位置
int push(int* a, int top, int elem){
a[++top]=elem;
return top;
}
出栈
其实top这个变量对于入栈没有帮助，在出栈时会体现出它的用处：
当然这两张图是让大家更容易理解这个意思，如果真的想将栈中元素全部消失，我们可以直接令top=-1即可，因为你以后再添加元素时就会将以前存储的元素替换掉将旧元素覆盖。
用代码实现：
//数据元素出栈
int pop(int *a, int top){
if(top==-1){
printf("空栈");
return -1;
}
printf("出栈元素：%d\n", a[top--]);
return top;
}
这段代码中的if能有效防止明明没有数据要出栈还要数据出栈的错误操作，最后只需要top的值等于-1即可。
我们将上面的代码总结一下:
#include <stdio.h>
int push(int* a, int top, int elem){
a[++top]=elem;
return top;
}
int pop(int* a,int top){
if(top==-1){
printf("空栈");
return -1;
}
printf("出栈元素：%d\n", a[top--]);
return top;
}
int main(){
int a[100];
int top=-1;
top=push(a,top,1);
top=push(a,top,2);
top=push(a,top,3);
top=push(a,top,4);
top=pop(a,top);
top=pop(a,top);
top=pop(a,top);
top=pop(a,top);
top=pop(a,top);
return 0;
}
链栈
链栈，就是用链表实现栈的存储结构。
顺序栈用顺序表的方式来理解，链栈也一样用链表的方式来理解：
链表的头部作为栈顶，意味着：
- 在实现数据“入栈”操作时，需要将数据从链表的头部插入；
- 在实现数据“出栈”操作时，需要删除链表头部的首元节点；
因此，链栈实际上就是一个只能采用头插法插入或删除数据的链表。
入栈
实现代码：
//链表中的节点结构
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;
//stack为当前的链栈，a表示入栈元素
lineStack* push(lineStack * stack, int a){
//创建存储新元素的节点
lineStack * line=(lineStack*)malloc(sizeof(lineStack));
line->data=a;
//新节点与头节点建立逻辑关系
line->next=stack;
//更新头指针的指向
stack=line;
return stack;
}
出栈
//栈顶元素出链栈的实现函数
lineStack * pop(lineStack * Stack){
if(stack){
//声明一个新指针指向栈顶节点
lineStack * p = stack;
//更新头指针
stack=stack->next;
printf("出栈元素:%d",p->data);
if(stack){
printf("新栈顶元素:%d\n",stack->data);
}
else{
printf("栈已空\n");
}
free(p);
}
else{
printf("栈内没有元素")；
return stack;
}
return stack;
}
if和顺序栈是同样的作用，都是用来控制栈内没有元素了还要往外出的情况。
我将上面两段程序整合一下：
#include <stdio.h>
#include <stdlib.h>
typedef struct lineStack{
int data;
struct lineStack * next;
}lineStack;
lineStack * push(lineStack * Stack, int a){
lineStack * line = (lineStack *)malloc(sizeof(lineStack));
line->data=a;
line->next=stack;
stack=line;
return stack;
}
lineStack * pop(lineStack * Stack){
if(stack){
lineStack * p = stack;
stack = stack->next;
printf("出栈元素：%d\n",p->data);
if(stack){
printf("栈顶元素:%d\n",stack->data);
}
else{
printf("栈已空\n");
}
free(p);
}
else{
printf("栈内没有元素\n");
return stack;
}
return stack;
}
int main(){
lineStack * stack = NULL;
stack=push(stack,1);
stack=push(stack,2);
stack=push(stack,3);
stack=push(stack,4);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
stack=pop(stack);
}