今天开始把大学学过的栈来实现重新温习一遍，讲真的基本上，大学只要是计算机专业的或者更准确一点，说是软件专业的，学过数据结构最后剩下的一些印象估计就剩下栈，队列，链表这些东西了。如果说是学c语言去实现的，那理解起来是非常困难的，当然不是说java就简单了。
其实其他的一些数据结构比如二叉树，图形，等等也会涉及到栈的思想的一些应用的。千里之行始于足下，不积跬步无以至千里，不积小流无以成江河。从要学好那些高深的数据结构等等算法，还是要先把这些基础的学好，才能在这基础上去深入。不多说，开始撸理论了。。
首先是栈的介绍：
1.栈的英文是(Stack,必须记住)
2.栈是一个先入后出的"有序列表"(首先是列表，其次是有序的)。
3.栈是一个限制线性表中元素的插入和删除只能在线性表的同一段进行的一种特殊性表。
允许插入和删除的一段，为变化的一段，称为栈顶，另一端为固定的一段，称为栈底。
4.根据栈的定义可知，最先放入栈中元素的在栈底，后面放入的元素都在栈，而删除元素正好相反。
然后我列举一些栈的应用场景
1.子程序的调用，在跳往子程序前，会先将下一个指令的地址存到栈顶，直到子程序执行完后，以回到原来的程序中。
2.处理递归调用： 和子程序的调用类似，只是除了存储下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
3.表达式的转换与求值。
4.二叉树的遍历。
5.图形的深度优先搜索法。
在java中对于栈有专门提供一个现成的类Stack，但我们主要是为了学习和实现，所以先使用数组来实现一个小demo。
然后这里就讲解一些，我实现这个结构的思路。
首先我打算构建一个栈，使用数组实现，那么栈是有固定大小的，同时需要有一个数表示栈顶位置，还需要一个数组。于是我先构建了一个栈类。
class ArrayStack{
/**栈得大小*/
private int maxSize;
/** 数组，模拟栈*/
private int []stack;
/** top 栈顶，初始化为-1,当栈顶为-1的时候，可以判断此时栈中没有数据 */
private int top=-1;
接着往下走，一个栈需要入栈，出栈，以及遍历这三个功能。那么这三个功能实现之前都分别需要判断栈是空的，还是栈已经满了，所以我们可以先写好两个判断栈空，和栈满的方法。
/**
* 栈空
*/
public boolean isEmpty(){
return top==-1;
}
/**
* 栈满
*/
public boolean isFull(){
return top == this.maxSize-1;
}
好了，接着往下，我们可以先实现入栈还有出栈了，这部分的思路应该比较简单，毕竟是用数组实现的。
/**
* 入栈
*/
public void push(int value){
if(isFull()){
System.out.println("该栈已经满了");
return ;
}else{
top++;
stack[top]=value;
}
}
/**
* 出栈
*/
public int pop(){
if(isEmpty()){
System.out.println("栈空");
throw new RuntimeException("栈空");
}else{
//出栈
return stack[top--];
}
}
最后，我们需要通过打印结果，来判断我们的出入栈是否正确执行了。这里是遍历的实现。
/**
* 遍历时，需要从栈顶开始显示数据
*
*/
public void list(){
if(isEmpty()){
System.out.println("栈空");
return ;
}
for(int i=top;i>=0;i--){
System.out.println(i+" "+stack[i]);
}
}
写了个测试：
public static void main(String[] args) {
ArrayStack arrayStack = new ArrayStack(5);
arrayStack.push(4);
arrayStack.push(5);
arrayStack.pop();
arrayStack.push(1);
arrayStack.push(2);
arrayStack.push(6);
arrayStack.push(7);
arrayStack.list();
}
以上是数组的实现方式，接下来，难度提升，我们将使用单向链表的方式实现栈。使用链表的话，基本上第一步都是要不要使用头链表，这里我还是继续使用头链表(区别不大)。然后由于是单链表，我们还需要考虑，栈的长度是否要设置，还是需要设置的。
