一.简介

概念
栈是一种操作受限的线性表只允许从一端插入和删除数据。

存储方式
即线性存储和链接存储（链表）。

操作方式
每个栈都有一个栈顶指针，它初始值为-1，且总是指向最后一个入栈的元素，栈有两种处理方式，即进栈（push）和出栈（pop），因为在进栈只需要移动一个变量存储空间，所以它的时间复杂度为O(1)，但是对于出栈分两种情况，栈未满时，时间复杂度也为O(1)，但是当栈满时，需要重新分配内存，并移动栈内所有数据，所以此时的时间复杂度为O(n)。

注意
栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行，所以每次删除的元素都是最后进栈的元素，故栈也被称为后进先出（LIFO）表。

以下举例栈结构的两种实现方式，线性存储和链接存储。

图片.png

栈的顺序方式的实现是一个数组。

二.栈的操作

栈的插入（push）

p = new Node(e,stack.top);
stack.top = p;
size ++;

栈（链式结构）的出栈

释放栈顶节点，并将栈顶下移，
p =stack->top;
stack->top = p->next; 
free(p);
stack -> conut--;

图片.png

三.栈的应用

链表反转 (链式结构进栈)

头节点放栈底，尾节点放栈顶
p = first;
stack.top = p;
size++;
first = first.next;

图片.png

递归算法
1.首先来看一道例题，这个函数当n输入为3时，打印是什么？

    public void fun(int n){  //3
        System.out.println(n);
        if(n<0){
            return;
        }else{
            fun(n-1);
            System.out.println(n);
        }
    }

.
3
2
1
0
-1
1
2
3
.
思考完了的可以一起看下执行过程，如下图
黑色为顺序执行，红色为逆序执行

图片.png

2.斐波拉契数列

    public int fact(int n){
        if(n<=1){
            return 1;
        }else{
            return n*fact(n-1);
        }
    }

3.汉诺塔算法
如何将第一根柱子上的盘子全部挪到第三根柱子上

图片.png

    /**
     * @param n      盘子的个数
     * @param start   开始的柱子
     * @param middle   中介柱子
     * @param end      结果柱子
     */
public static void hanoi(int n,int start,int middle,int end){
        if(n<=1){
            System.out.println(start+"----->"+end);
        }else{
            hanoi(n-1,start,end,middle);
            System.out.println(start+"----->"+end);
            hanoi(n-1,middle,start,end);
        }
    }

4.伊波兰表达式
这个感兴趣的童鞋可以自己去了解一下