前言
这两天不知道有点咋了，心里乱糟糟的，今天正好整理一下栈的知识，然后顺顺心，主要就是理解一下栈这个数据结构
一、什么是栈？
栈是一种特殊的线性表，它只允许在一端进行操作，所以它具有 先进后出或者叫后进先出的特性，这就是栈
那么同样都是数据结构，我们为什么要使用这种，操作受限，因为在特定的环境下需要使用特定的数据结构，在一些先进后出的场合，理所应当的使用栈这种结构
二、栈的实现
栈的实现有两种，一种是基于数组事项的栈叫顺序栈，另一种是基于链表实现的栈链式栈
- 顺序栈(java实现)
public class ArrayStack{
private String [ ] items;//数组变量
private int count;//栈中元素变量
private int n; //栈的大小
//初始化数组，定义一个为n的空间
public ArrayStack（int n）{
this.items=new String [n];
this.n=n;
this.count=0;
}
//入栈，传入一个数组
public boolean push （String item）{
if（count==n）
return false；//数组空间不够，入栈失败
//将item放入到count的位置，并起count+1，返回成功
item[count]=item;
count++;
return true;
}
//出栈
public String pop( ){
//如果栈为空，返回null
if(count==o)
return null;
//放回下标为count-1位置的数，并起count-1
String temp= item[count-1];
count--；
return temp；
}
}
- 链式栈
和数组类似，具体可参看 链式栈 java实现
三、栈的应用
1.函数调用栈
有这么一个栈的内存，用来存储栈的数据结构，每进入一个函数，就会将临时变量当做一个栈帧入栈，当函数使用完成以后，这个函数对应的栈帧出栈
有这么一段代码
int main（）{
int a =1;
int ret=0;
int res=0;
ret=add(1,9)
res=a+ret;
return 0;
}
int add(int x,int y){
int sum=0;
sum=x+y;
return sum;
}
入栈和出栈的顺序为
a=1
res=0 main栈帧
ret=0
.....
y=1
x=9 add栈帧
sum=0
...
2.栈在表达式求值中的应用
利用栈来实现表达式求值
编译器通过两个栈来实现，分别是保存操作数的栈和保存运算符的栈
实现过程是这样的
1.遍历表达式，如果遇到操作数，则存入操作数栈，如果遇到运算符，则和存在运算符栈的栈顶的运算符比较（已经预先存了 + - * /）
2.如果优先级大于运算符栈 栈顶的优先级，则将当前运算符压入栈，如果低于栈顶运算符的优先级，则返回
3.从操作数栈中取数，从运算符栈中取运算符--》计算
3.栈在匹配中的应用
我们还可以使用栈来检查表达式中是否匹配
- 我们先假定一个条件只有匹配到 “[ ]”{ }“( )”，两个括号都有才算正确，否则都算匹配不正确
- 接下来从左向右依次扫描字符串，如果遇到“[”{““(””就存入栈中，如果遇到另一半的右括号，就从栈顶取出左括号进行匹配，只有左右是同一中括号才匹配成功，如果匹配成功，就继续进行扫描，如果匹配不成功，就说明字符串格式不正确
- 当然还有一种情况就是，当栈为空的时候，也是匹配成功，因为栈里所有的都已经完成匹配
