文章目录使用链表实现栈 算法实战——括号匹配算法实战——行编辑器算法实战——简单寻路算法
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 = http://www.kingceram.com/post/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 = http://www.kingceram.com/post/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];}