1、定义
栈是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）,不含任何数据元素的栈称为空栈。栈又称为后进先出的线性表。
2、栈顶和栈底
图片.png
如图所示，栈的底部叫栈底，栈的顶部叫栈顶。
3、入栈和出栈
向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；
图片.png
如图所示，两个蓝色的箭头分别表示入栈和出栈。
4、Stack
Java中使用Stack做为栈类，它的父类是Vector， 在Java 1.2之后被ArrayList替代。ArrayList就是去掉了线程安全的Vector。
使用Stack操作栈的代码如下：
Stack<String> stack = new Stack(); // 创建一个栈
boolean isEmpty = stack.empty(); // 是否是空栈
stack.push("A"); // 将字母A压入栈中
stack.push("B"); // 将字母B压入栈中
stack.push("C"); // 将字母C压入栈中
String data = stack.pop(); // 将栈顶的数据弹出
5、四则运算
假设有一个小学数学题： a / 2，经过人们口算之后会很快得出答案。
但是，电脑是怎么计算的呢？
该四则运算在计算机中是通过`逆波兰表达式`得来。
除法运算 a / 2 可以使用 a >> 1 得出结果，然而前者在计算机中需要6个以上的指令集才能完成计算，
后者在计算机中只需要一个指令即可完成，所以后者在计算中中的计算速度要快于前者。
在Java中，四则运算是用`逆波兰表达式`计算的，即`中缀表达式`转成`后缀表达式`，a / 2 是`中缀表达式`，逆波兰表达式是`后缀表达式`。
下面讲解一下四则运算在计算机中是如何计算的？
第一步：中缀表达式转后缀表达式
假如有一个四则运算：6+(1+5)*2-15/3，它是`中缀表达式`，转换成`后缀表达式`之前需要先了解以下运算符号的优先级：
运算符合的优先级从低到高分别是：+ - * / ( ) #
中缀转后缀的原则是：从左往右，数字输出，运算符进栈，括号匹配时出栈，比栈顶优先级低或者相同就出栈
此时，我们需要一个栈
1、栈底压入符号 #
| |
| |
| # |
-----
2、数字6直接输出：6
3、运算符 + 入栈
| |
| + |
| # |
-----
4、左括号 `(` 不做比较，直接入栈
| |
| ( |
| + |
| # |
-----
5、数字1直接输出：6 1
6、`(` 不做比较，所以将 `+` 入栈：
| + |
| ( |
| + |
| # |
-----
7、数字5直接输出：6 1 5
8、右括号 `)` 与栈中的 `(` 对应， 所以将运算符依次出栈，左括号和右括号移除，此时输出结果为： 6 1 5 +
栈为：
| |
| |
| + |
| # |
-----
9、运算符 `*` 比栈顶 `+` 优先级高，所以运算符 `*` 入栈：
| |
| * |
| + |
| # |
-----
10、数字2直接输出：6 1 5 + 2
11、运算符 `-` 比栈顶 `*` 优先级低，所以运算符 `*` 出栈并输出：6 1 5 + 2 *
此时，栈为：
| |
| |
| + |
| # |
-----
运算符 `-` 继续与栈顶运算符 `+`比较，运算符 `-` 的优先级比 `+` 高，所以运算符 `-` 入栈：
| |
| - |
| + |
| # |
-----
12、数字15直接输出：6 1 5 + 2 * 15
13、运算符 `/` 比栈顶运算符 `-` 优先级高，所以运算符 `/` 入栈：
| |
| / |
| - |
| + |
| # |
-----
14、数字3直接输出：6 1 5 + 2 * 15 3
15、将栈中的运算符依次出栈并输出：6 1 5 + 2 * 15 3 / - +
所以最终输出的后缀表达式为：6 1 5 + 2 * 15 3 / - +，也可以称之为逆波兰表达式。
第二步：计算
后缀表达式为：6 1 5 + 2 * 15 3 / - +，计算原则是：遇到数字直接入栈，遇到运算符出栈两个操作数并计算
1、将 6 1 5 依次入栈
| |
| |
| 5 |
| 1 |
| 6 |
-----
2、遇到运算符 `+` ，将 5 和 1 依次出栈，并计算： 1 + 5 = 6，将6入栈：
| |
| |
| |
| 6 |
| 6 |
-----
3、数字 2 入栈
| |
| |
| 2 |
| 6 |
| 6 |
-----
4、遇到运算符 `*`， 将 2 和 6 依次出栈，并计算： 6* 2 = 12，将12入栈：
| |
| |
| |
| 12 |
| 6 |
------
5、数字 15 和 3 依次入栈
| |
| 3 |
| 15 |
| 12 |
| 6 |
------
6、遇到运算符 `/`，将数字 3 和 15 依次出栈，并计算 15 / 3 = 5，将数字 5 入栈
| |
| |
| 5 |
| 12 |
| 6 |
------
7、遇到运算符 `-`，将数字 5 和 12 依次出栈，并计算 12 - 5 = 7，将数组 7 入栈
| |
| |
| |
| 7 |
| 6 |
------
8、遇到运算符 `+`，将数字 7 和 6 依次出栈，并计算 6 + 7 = 13，栈中没有任何数据，所以最终输出结果是：13。
6、递归
递归也可以用栈来理解。
案例[一]： 阶层运算
从数字1一直乘到n：1*2*3*4*...*n，我们称之为n的阶层，用 n！表示。
代码实现如下：
public int fact(int n){
if(n<=1){
return 1;
}else{
return n*fact(n-1);
}
}
案例[二]：斐波那契数列
斐波那契数列的特点就是，数列中任选一个数（除第一第二位），都是前两位的总和。
使用代码实现如下：
/**
* fibonacciSequence数列 8=7+6 7=6+5 6=5+4
* 1 1 2 3 5 8 13 21 34 55 89 144......
* 返回第n项
*/
public int fibonacciSequence(int n){
if(n==1 || n==2){
return 1;
}else{
return fibonacciSequence(n-1)+fibonacciSequence(n-2);
}
}
案例[三]：汉诺塔算法
有三个柱子，64个盘子，盘子只能把小的放在大的上面，从左边移动到最右边。
代码实现如下：
/**
* @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);
}
}
调用自己一次的情况：调用位置前面的代码是正循环，调用位置后面的代码是反循环。
调用自己两次的情况：他是一个二叉树的中序遍历过程。
[本章完...]
网友评论