美文网首页
算法与数据结构知识汇总(三、栈)

算法与数据结构知识汇总(三、栈)

作者: NoBugException | 来源:发表于2021-08-28 12:35 被阅读0次
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);
    }
}

调用自己一次的情况:调用位置前面的代码是正循环,调用位置后面的代码是反循环。
调用自己两次的情况:他是一个二叉树的中序遍历过程。

[本章完...]

相关文章

网友评论

      本文标题:算法与数据结构知识汇总(三、栈)

      本文链接:https://www.haomeiwen.com/subject/tzznvltx.html