使用链表实现栈
首先思考一下，数组与链表的实现过程有何差异？
是否还需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