1.通过浏览器的前进后退理解栈

文章目录 使用链表实现栈 算法实战——括号匹配算法实战——行编辑器算法实战——简单寻路算法

1.通过浏览器的前进后退理解栈

浏览器是如何实现进退的？

​ 以我们当前页面为例，我们点击底部文章链接跳转到别的文章，反复多次，我们便实现了栈的存储；之后，我们点击后退，返回到的是我们倒数第二篇文章，此时我们便将最后打开的篇文章从栈中弹出。

​ 当我们不断后退，退回到我们当前的文章时，我们便实现了栈的清空。此时，如果我再点击一篇别的文章，之后无论我如何再点击前进后退，我也无法再回到之前的栈中的文章了，除非我通过之前的路径重新储存栈。

​ 后进者先出，先进者后出，这就是栈的特点。

2.栈的实现

​ 栈的特性在本质上与数组和链表无异，都是用于存储一批相同类型的数据，因此他的底层实现无非就是两种：数组和链表。

使用数组实现栈

​ 实现栈需要三个核心的方法：push（添加栈顶元素），peek（获取栈顶元素），pop（弹出栈顶元素）。

栈的初始化

​ 我们知道，数组是固定的长度，因此我们再添加栈元素的时候需要先初始化一个数组。代码如下：

public class YKDStack {String[] data;int size;// #1. 初始化栈，默认大小为20public YKDStack(){this.initData(20);}// #2. 初始化栈，并传入栈空间大小public YKDStack(int size){this.initData(size);}// 初始化数组private void initData(int size){this.size = size;this.data = new String[this.size];}
}

#1，#2表示此栈支持创建一个默认空间为20的栈，也支持自定义空间的栈。

push方法

首先我们需要添加一个top变量来记录栈顶在数组中的位置。

当栈为空的时候，top 为 -1。

当只有 1 个元素时，top 为 0。

当有 10 个元素时，top 为 9。

push方法的核心逻辑有三点：

优先判断是否数组越界；更改变量top的值；往数组中添加一个元素.

代码如下：

// 添加元素
public boolean push(String value) {// 数组越界了if (this.top >= this.size - 1) {return false;}// top 栈顶 +1this.top++;// 设置栈顶元素this.data[this.top] = value;return true;
}

peek方法

获取栈顶元素，我们需要考虑栈是否为空，如果为空则返回null。

代码如下：

// 获取栈顶元素public String peek() {if (this.top == -1) {return null;}return this.data[this.top];}

pop方法

​ 弹出栈顶元素同样需要判断是否为空，而与peek不同的是，我们需要将top指针后移，代表此时的栈顶元素变为前一项元素，在下一次添加时则会将此元素覆盖。

代码如下：

// 弹出栈顶元素public String pop() {if (this.top == -1) {return null;}String item = this.data[this.top];this.top--;return item;}

此时我们便完成了一个完整的栈。完整代码如下：

public class YKDStack {String[] data;int size;// 栈顶位置int top = -1;// 初始化栈，默认大小为20public YKDStack() {this.initData(20);}// 初始化栈，并传入栈空间大小public YKDStack(int size) {this.initData(size);}// 初始化数组private void initData(int size) {this.size = size;this.data = new String[this.size];}// 添加元素public boolean push(String value) {// 数组越界了if (this.top >= this.size - 1) {return false;}// top 栈顶 +1this.top++;// 设置栈顶元素this.data[this.top] = value;return true;}// 弹出栈顶元素public String pop() {if (this.top == -1) {return null;}String item = this.data[this.top];this.top--;return item;}// 获取栈顶元素public String peek() {if (this.top == -1) {return null;}return this.data[this.top];}

使用链表实现栈

首先思考一下，数组与链表的实现过程有何差异？

是否还需size标记栈的大小？

不需要，链表不像数组一样，需要声明长度空间，链表本身具备无限扩容的能力。

链表如何表示栈顶元素？

我们使用数组时，是将数组尾作为栈顶元素实现的。而在链表中，链表头操作的时间复杂度为O(1)，链表尾操作的时间复杂度为O(N)。由于 我们操作的基本都是操作栈顶，，所以将链表头作为栈顶是最佳的选择。

关于链表如何实现，参见我的文章：基于节点的数据结构——链表

实现代码如下：

package com.youkeda;public class YKDStack {//对象为创建的Node类，用来实现链表节点的创建Node header;public YKDStack() {}// 添加元素public boolean push(String value) {if (this.header == null) {// 当前为空的时候，添加headerthis.header = new Node(value);} else {// 当前不为空的时候，构建一个新的头部节点this.header = new Node(value, this.header);}return true;}// 弹出栈顶元素public String pop() {if (this.header == null) {return null;}// 删除链表头部节点Node node = this.header;this.header = node.getNext();node.setNext(null);return node.getContent();}// 获取栈顶元素public String peek() {if(this.header == null){return null;}return this.header.getContent();}

算法实战——括号匹配

​ 接下来我们通过一个算法题目来学习栈的实际场景。场景题目如下：

在运行java代码的时候，运行工具会先帮我们进行语法校验，在语法校验中很重要的一步是——判断括号是否匹配。简单来说，就是有左括号就应该有右括号，有开即有合。

​ 如果使用基础算法，我们可能会这样实现：

​ 通过一个整数来存储括号匹配情况，这个整数初始化为 0，遇到左括号则+1，遇到右括号则-1，最后程序运行结束后，查看整数是否为 0。

int bracketNum = 0;//————> '()'
int bigBracketNum = 0;//————> '{}'

​ 但这种算法有一个漏洞：有一种错误情况它是无法识别的，比如{((})),此时最后的判断依旧为ture，因为最终运算结果都为0。

​ 上面这种问题出现的核心问题在于，我们仅仅用数字来存储括号匹配情况，并没有考虑括号的顺序问题。而这种嵌套性的关系，用栈可以很好的解决，下面我们来看看用栈实现括号匹配的思路。

栈实现括号匹配

核心思路如下：

当遇到左括号(、{、[，则压入栈中;

当遇到右括号)、}、]，将此右括号和栈顶括号进行匹配。如果配套，则将栈顶元素弹出，否则括号不匹配。

我们可以举两个例子加深理解：

例一

查看字符串()({()})括号匹配情况，示意图如下：

具体步骤如下：

1. 扫描到`(`，左括号压入栈中
2. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作
3. 扫描到`(`，左括号压入栈中
4. 扫描到`{`，左括号压入栈中
5. 扫描到`(`，左括号压入栈中
6. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作
7. 扫描到`}`，右括号与栈顶`{`匹配，执行`pop`操作
8. 扫描到`)`，右括号与栈顶`(`匹配，执行`pop`操作

例二

查看字符串{((}))括号匹配情况，具体步骤如下：

1. 扫描到`{`，左括号压入栈中
2. 扫描到`(`，左括号压入栈中
3. 扫描到`(`，左括号压入栈中
4. 扫描到`}`，右括号与栈顶`(`匹配，匹配失败，停止操作

具体的代码实现如下：

//使用我们之前完成的链表栈实现// 判断代码括号是否匹配public static boolean match(String code) {//创建栈对象YKDStack<Character> stack = new YKDStack<>();//遍历字符串，并与栈顶比较for (int i = 0; i < code.length(); i++) {//取出字符串中的元素char c = code.charAt(i);//左括号直接压入栈中if (c == '(' || c == '{' || c == '[') {stack.push(c);continue;}//匹配右括号与栈顶元素，不为成对则返回falseif (c == ')') {if (stack.peek() != null && stack.peek() == '(') {stack.pop();} else {return false;}}if (c == '}') {if (stack.peek() != null && stack.peek() == '{') {stack.pop();} else {return false;}}if (c == ']') {if (stack.peek() != null && stack.peek() == '[') {stack.pop();} else {return false;}}}//匹配成功后栈内元素应为空return stack.peek() == null;}

算法实战——行编辑器

​ 在计算机最初，没有很强大的编辑器，当时只有行编辑器。行编辑器如何使用呢？

​ 用户从终端输入的程序或数据，并将最后结果显示到屏幕上。由于用户输入时，不能保证不出差错，因此，若在编辑程序中，每接受一个字符即输出到屏幕上的做法显然不恰当。较好的做法是，设立一个输入缓冲区，用以接受用户输入的一行字符，然后一次性将其显示到屏幕上。允许用户输入出错并及时改正。

​ 以#表示退格，删除上一个字符。以@表示退行，删除一整行。看几个简单的例子：

输入：abc#dd     输出：abdd
输入：abc@dd     输出: dd
输入：a#b#d#ce   输出：ce
输入：ab##dce    输出：dce

​ 我们通过栈，可以很简单的实现这种编辑器。具体代码如下：

	// 行编辑器的输入public static String input(String source) {YKDStack<Character> stack = new YKDStack<>();// 遍历每个字符for (int i = 0; i < source.length(); i++) {char c = source.charAt(i);// 遇到 # 则 popif (c == '#') {if (stack.peek() != null) {stack.pop();}continue;}// 遇到 @ 则清空，相当于重新 new YKDStack()。if (c == '@') {stack = new YKDStack<>();continue;}stack.push(c);}// 将栈中元素依次pop出来，拼接在字符串前面String result = "";while(stack.peek() != null){result = stack.pop() + result;}return result;}

算法实战——简单寻路算法

自动寻路

​ 在实际游戏场景中，地图是非常复杂的，但是无论什么地图，自动寻路都可以简化为 3 要素：可移动区域，不可移动区域，起点和终点。

​ 如果我把地图划分为多个方格，每个方格表示移动的最小单位，我们便能将整个地图投影成如下二维视觉：

​ 深灰色的区块为障碍物，白色区块表示可行动的区域，图中分别标注了起点和终点。

​ 假设，现在每一步都只能从一个方格移动到其相邻的方格，并且只能上下左右移动，那么如何找寻现一条从起点移动到终点路径呢？

思路

​ 首先我们分析一下我们遇到的问题：

如何存储整个地图信息，包括障碍物，可移动区域？如何存储寻找自动寻路路径？ 地图信息

​ 对于这样的二维地图，我们可以用二维数组进行存储，同时因为每个方格都有不同的状态，为了方便显示，我们可以利用字符存储每个方格信息。

用#表示障碍物，空格表示可移动区域。

代码如下：

char[][] map = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},{'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};

如果我们想获取方格信息，如第三行、第四列方格，代码如下：

int row = 2;
int column = 3;// 第 3 行，第 4 列信息
char content = map[row][column]

​ 我们将整个游戏用Game来表示，在Game这个类中设置一个map属性。

​ 紧接着，那应该如何表示起始和结束点位置呢？

从上面的代码我们知道每个方格有两个属性：row和，用来表示每个方格的位置，因此我们可以新建Point类用于存储位置信息。

整合上面的思路， 整个Game的代码如下：

public class Game {private char[][] map;public Game(char[][] map) {this.map = map;}// 寻找路径public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();return path;}
}

Point的代码如下：

public class Point {private int row = 0;private int column = 0;.....
}

注意其中的方法，返回的是一条从起点到终点的路径。

在这个地图的基础上，我们再来考虑如何寻找路径。

寻找路径

​ 我们假设一个迷宫场景，现在我们自己站在某一个方格上（并且不是上帝视角的情况下），我们应该怎么尝试找到出口呢?

​ 从我们的题目基本信息得知，当我们站在某一个方格上都有4 个方向可以进行探索：上下左右。我们可以考虑一个思路：

当站在某个方格上时候，初始我们都选中一个方向，比如右进行探索。如果右侧元素不是障碍物，则我们移动到右侧方格上，继续进行1步骤。如果右侧元素为障碍物或者已经遍历过的方格，则按下、左、上方向进行探索。如果 4 个方向都不能进一步探索，那没办法了，我们只能回退上一个方格，从新选择方向。

因为我们知道目标终点在起点的右下角，所有我们用这个方向，可以避免很多额外的步骤。

第一个问题：如何描述方向？

​ 我们使用向量来描述方向：假定方向为（0，0），将第一位当作row上的增量, 第二位当做上的增量，那么右下左上分别表示为：

右侧：row 不变， 加 1，所以向量表示为：{0, 1} 下侧：row 加 1， 不变，所以向量表示为：{1, 0} 左侧：row 不变， 减 1，所以向量表示为：{0, -1} 上侧：row 减 1， 不变，所以向量表示为：{-1, 0}

​ 因此我们在Game中添加如下代码，按顺序存储 右下左上 四个方向，代码如下

// 存储4个方向
private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

第二个问题：怎么存储探索的路径呢？还要非常方便我们回退？

大家试想一下这个场景和栈的模式非常像，最开始的起点在栈底，每探索一个方格，则往栈里push一个元素，如果遇到一条死路，则pop回退到上一个元素并且换个方向继续探索。

第三个问题：怎么标记方格是否访问过？方格是否是死路？

为了区分#和空格，我们可以用*表示方格已经被访问过，用@表示方格为死路。

​ 因此我们新建一个Tile对象，表示在栈中的信息，包括方格位置和遍历的方向，代码如下：

public class Tile {// 方格位置private Point point;// 方格当前遍历的方向private int direction = 0;
}

​ 继续在Game中添加变量steps，利用栈存储探索路径中的方格，代码如下：

public class Game {private char[][] map;// 利用栈存储探索的路径节点，元素为Tile对象private YKDStack<Tile> steps = new YKDStack<>();// 存储4个方向private int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};public Game(char[][] map) {this.map = map;}......
}

接下来我们来看看整个实战过程。

实战过程

第 1 步

我们站在起点，将起点位置{1, 1}加入到steps栈中，并将该元素的方向设置为-1，也就是表示还未探索过。

第 2 步

获取栈顶元素，也就是{1, 1}方格，将方格的方向加 1 当做探索方向，也就是右侧(-1 + 1 = 0, 在右下左上中，索引为 0 的是右侧)。探索方格右侧方格{1, 2}，并将其加入到steps栈中，方向设置为-1。

第 3 步

获取栈顶元素，也就是{1, 2}方格，将方格的方向加 1 当做探索方向，同样也是右侧。因为右侧遇到#，无法作为路径，则继续将方向加 1，改为下侧（0 + 1 = 1, 在右下左上中，索引为 1 的是下侧）。探索方格下侧方格{2, 2}，并将其加入到steps栈中，方向设置为-1。

以此类推，可以达到如下情况

这时候我们发现{1, 4}这个方格，上下左右都不能移动了，这是一条死路，因此我们将该方格设置为@，并将此方格从栈顶pop。继续观察此时的栈顶元素{1, 5}，同样也是死路，我们将其也设置为@，并执行pop操作。

直到如下场景：

获取栈顶元素{3, 2}，发现之前的方向是右侧0，首先加 1 探索下侧方向，无法通行。将方向继续加 1，探索左侧方向，因此将{3, 1}加入栈顶。

下面的步骤就不演示，以此内推，最终可以找到结束的节点，如下图所示：

路径回溯

这个时候，栈中存储的刚好是从起点到终点的方格路径，我们只需要依次pop栈顶元素，然后倒叙即可获取路径完整信息。

代码实现

​ 有了思路，接下来便开始完善方法。

// 寻找路径
public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();return path;
}

第一步：将起点添加到栈中

// 寻找路径
public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();// 每次寻路之前将栈清空this.steps = new YKDStack<>();// 将起点添加到栈中，并将其标记为已访问this.steps.push(new Tile(start, -1));this.map[start.getRow()][start.getColumn()] = '*';
}

这一步比较简单，大家需要注意的是每次寻找路径之前，需要将栈清空。

第二步：循环获取栈顶元素，修改方向准备进行探索

// 判断是否为同一个方格，用于判断是否找到结束方格
private boolean isSame(Point point1, Point point2) {return point1.getRow() == point2.getRow() && point1.getColumn() == point2.getColumn();
}// 寻找路径
public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();// 每次寻路之前将栈清空this.steps = new YKDStack<>();// 将起点添加到栈中，并将其标记为已访问this.steps.push(new Tile(start, -1));this.map[start.getRow()][start.getColumn()] = '*';// 循环到栈中元素为空结束，则表示从起点开始未能找到结束点while (this.steps.peek() != null) {// 获取栈顶元素Tile tile = this.steps.peek();Point tilePoint = tile.getPoint();// 判断是不是结束节点if (this.isSame(tilePoint, end)) {break;}// 修改栈顶元素的方向，准备进行探索tile.setDirection(tile.getDirection() + 1);}return path;
}

​ 如上面代码，当栈为空的时候表示没有任何一条路径可以从起点到终点。 我们抽离了方法判断两个方格是否相同。

第三步：根据方向添加新探索节点到栈中，或者设置为死路并 pop 栈顶元素

// 判断是否为同一个方格
private boolean isSame(Point point1, Point point2) {return point1.getRow() == point2.getRow() && point1.getColumn() == point2.getColumn();
}// 判断探索是否可以进行，如果是空格才可以进行
private boolean canStep(Point point) {return this.map[point.getRow()][point.getColumn()] == ' ';
}// 寻找路径
public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();// 每次寻路之前将栈清空this.steps = new YKDStack<>();// 将起点添加到栈中，并将其标记为已访问this.steps.push(new Tile(start, -1));this.map[start.getRow()][start.getColumn()] = '*';// 循环到栈中元素为空结束，则表示从起点开始未能找到结束点while (this.steps.peek() != null) {// 获取栈顶元素Tile tile = this.steps.peek();Point tilePoint = tile.getPoint();// 判断是不是结束节点if (this.isSame(tilePoint, end)) {break;}// 修改栈顶元素的方向，准备进行探索tile.setDirection(tile.getDirection() + 1);// 当方向为 4 的时候，表示所有方向都已经遍历过了，所以标记为死路@，并弹出栈顶元素if (tile.getDirection() == 4) {this.map[tilePoint.getRow()][tilePoint.getColumn()] = '@';this.steps.pop();} else {// 否则探索目标方向的方格int[] direction = directions[tile.getDirection()];// 根据方向向量获取新方格的位置信息Point newPoint = new Point(tilePoint.getRow() + direction[0],tilePoint.getColumn() + direction[1]);// 如果可以通行，则将新探索的方格添加到栈中，并标记为已访问if (this.canStep(newPoint)) {Tile newTile = new Tile(newPoint, -1);this.map[newPoint.getRow()][newPoint.getColumn()] = '*';this.steps.push(newTile);}// 如果不可以通行，则不处理，再次获取栈顶元素，改变方向。}}return path;
}

这部分非常重要，大家需要仔细阅读这部分代码和注释，彻底理解方向探索的核心。

第四步：回溯整个路径

从上面代码可以看出，当while循环执行完成后，只有两种情况

第一种，栈为空，也就是遍历完起点所能走到的所有方格，里面都没有找到终点 第二种，找到终点，break跳出循环

我们需要特别关心第二种情况，大家试想一下这个时候栈中存储的方格是什么特征？

栈中元素全是*元素，因为@将全部pop出栈。*元素表示的是探索的路径，并且从起点开始，终点结束的。如果我们依次pop，这将是一条终点到起点的路径，我们需要倒排即可。

我们来看看最后的代码：

// 寻找路径
public ArrayList<Point> findPath(Point start, Point end) {ArrayList<Point> path = new ArrayList<>();......// 从栈中以此回退方格信息，也就是整个访问路径信息while (this.steps.peek() != null) {//将下一个路径插到前面，已完成路径回溯path.add(0, this.steps.pop().getPoint());}return path;
}

测试一下：

public static void main(String[] args) {char[][] map = {{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', '#', ' ', ' ', ' ', '#', ' ', '#'},{'#', ' ', ' ', ' ', ' ', '#', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', ' ', ' ', '#', ' ', ' ', ' ', ' ', '#'},{'#', ' ', '#', ' ', ' ', ' ', '#', ' ', ' ', '#'},{'#', ' ', '#', '#', '#', ' ', '#', '#', ' ', '#'},{'#', '#', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '#'},{'#', '#', '#', '#', '#', '#', '#', '#', '#', '#'}};Game game = new Game(map);Point start = new Point(1, 1);Point end = new Point(8, 8);ArrayList<Point> path = game.findPath(start, end);for (Point point : path) {System.out.println(point.getRow() + " - " + point.getColumn());}}

最终的结果为：

1 - 1
1 - 2
2 - 2
3 - 2
3 - 1
4 - 1
5 - 1
5 - 2
5 - 3
6 - 3
6 - 4
6 - 5
7 - 5
8 - 5
8 - 6
8 - 7
8 - 8

这就是一条从起点到终点的路径，大家如果不相信可以视图对应每个方格到地图中，最后的路径与我们设想的路径相同。

总结

​ 这道题是一道及其复杂的题目。但是经过一步步分析和实现，其实代码逻辑也不会特别复杂。

​ 这道题的核心就是假设现在我们自己站在某一个方格上，我们应该怎么尝试找到出口。 做到这一点，剩下就迎刃而解了，这其实本质上也是一种分而治之的思想。