1.栈的介绍 　　在许多算法设计中都需要一种"先进后出(First Input Last Output)"的数据结构，因而一种被称为"栈"的数据结构被抽象了出来。 　　栈的结构类似一个罐头：只有一个开口；先被放进去的东西沉在底下，后放进去的东西被放在顶部；想拿东西必须按照从上到下的顺序进行操作。 　　 示意图来自《大话数据结构》 　　对于一个类似罐头的栈，用户能对其进行的操作很少：仅仅可以对栈顶开口处元素进行操作，因而栈的使用方式非常简单。 2.栈的ADT接口 复制代码 /** * 栈ADT 接口定义 * */ public interface Stack{ /** * 将一个元素 加入栈顶 * @param e 需要插入的元素 * @return 是否插入成功 * */ boolean push(E e); /** * 返回栈顶元素，并且将其从栈中移除(弹出) * @return 当前栈顶元素 * */ E pop(); /** * 返回栈顶元素，不将其从栈中移除(窥视) * @return 当前栈顶元素 * */ E peek(); /** * @return 返回当前列表中元素的个数 */ int size(); /** * 判断当前列表是否为空 * @return 如果当前列表中元素个数为0，返回true；否则，返回false */ boolean isEmpty(); /** * 清除栈中所有元素 * */ void clear(); /** * 获得迭代器 * */ Iterator iterator(); } 复制代码 3.栈的实现 　　如果我们将开口朝上的栈旋转90度，会发现栈和先前我们介绍过的线性表非常相似。栈可以被视为一个只能在某一端进行操作的，被施加了特别限制的线性表。 3.1 栈的向量实现 　　栈作为一种特殊的线性表，使用向量作为栈的底层实现是很自然的(向量栈)。 　　jdk的栈结构(Stack)是通过继承向量类(Vector)来实现的，这一栈的实现方式被java集合框架(Collection Framework)的作者Josh Bloch在其所著书籍《Effective Java》中所批评，Josh Bloch认为这是一种糟糕的实现方式，因为继承自向量的栈对使用者暴露了过多的细节。 原文部分摘录： 复制代码 复合优先于继承 　　继承打破了封装性。 　　java对象中违反这条规则的：stack不是vector，所以stack不应该扩展vector。如果在合适用复合的地方用了继承，会暴露实现细节。 　　继承机制会把超类中所有缺陷传递到子类中，而复合则允许设计新的API来隐藏这些缺陷。 复制代码 　　考虑到这一点，我们的向量栈采用复合的方式实现。通过使用之前我们已经实现的向量数据结构作为基础，实现一个栈容器。 向量基本属性和接口： 复制代码 /** * 向量为基础实现的 栈结构 * */ public class VectorStack implements Stack{ /** * 内部向量 * */ private ArrayList innerArrayList; /** * 默认构造方法 * */ public VectorStack() { this.innerArrayList = new ArrayList<>(); } /** * 构造方法,确定初始化时的内部向量大小 * */ public VectorStack(int initSize) { this.innerArrayList = new ArrayList<>(initSize); } @Override public int size() { return innerArrayList.size(); } @Override public boolean isEmpty() { return innerArrayList.isEmpty(); } @Override public void clear() { innerArrayList.clear(); } @Override public Iterator iterator() { return innerArrayList.iterator(); } @Override public String toString() { return innerArrayList.toString(); } } 复制代码 　　由于我们的向量容器已经具备了诸如自动扩容等特性，因而向量栈的许多接口都可以通过简单的调用内部向量的接口来实现，不需要额外的操作。 栈的特有接口实现： 复制代码 @Override public boolean push(E e) { //:::将新元素插入内部向量末尾(入栈) innerArrayList.add(e); return true; } @Override public E pop() { if(this.isEmpty()){ throw new CollectionEmptyException("Stack already empty"); } //:::内部向量末尾下标 int lastIndex = innerArrayList.size() - 1; //:::将向量末尾处元素删除并返回(出栈) return innerArrayList.remove(lastIndex); } @Override public E peek() { if(this.isEmpty()){ throw new CollectionEmptyException("Stack already empty"); } //:::内部向量末尾下标 int lastIndex = innerArrayList.size() - 1; //:::返回向量末尾处元素(窥视) return innerArrayList.get(lastIndex); } 复制代码 　　栈的FIFO的特性，使得我们必须选择内部线性表的一端作为栈顶。 　　我们知道向量在头部的插入/删除由于需要批量移动内部元素，时间复杂度为O(n)；而向量尾部的插入/删除由于避免了内部元素的移动，时间复杂度为O(1)。 　　而位于栈顶的元素是需要频繁插入(push)和删除(pop)的。出于效率的考虑，我们将向量的尾部作为栈顶，使得向量栈的出栈、入栈操作都达到了优秀的常数时间复杂度O(1)。 3.2 栈的链表实现 　　链表和向量同为线性表，因此栈的链表实现和向量实现几乎完全雷同。 　　由于链表在头尾出的增加/删除操作时间复杂度都是O(1)，理论上链表栈的栈顶放在链表的头部或者尾部都可以。为了和向量栈实现保持一致，我们的链表栈也将尾部作为栈顶。 复制代码 /** * 链表为基础实现的 栈结构 * */ public class LinkedListStack implements Stack{ /** * 内部链表 * */ private LinkedList innerLinkedList; /** * 默认构造方法 * */ public LinkedListStack() { this.innerLinkedList = new LinkedList<>(); } @Override public boolean push(E e) { //:::将新元素插入内部链表末尾(入栈) innerLinkedList.add(e); return true; } @Override public E pop() { if(this.isEmpty()){ throw new CollectionEmptyException("Stack already empty"); } //:::内部链表末尾下标 int lastIndex = innerLinkedList.size() - 1; //:::将链表末尾处元素删除并返回(出栈) return innerLinkedList.remove(lastIndex); } @Override public E peek() { if(this.isEmpty()){ throw new CollectionEmptyException("Stack already empty"); } //:::内部链表末尾下标 int lastIndex = innerLinkedList.size() - 1; //:::返回链表末尾处元素(窥视) return innerLinkedList.get(lastIndex); } @Override public int size() { return innerLinkedList.size(); } @Override public boolean isEmpty() { return innerLinkedList.isEmpty(); } @Override public void clear() { innerLinkedList.clear(); } @Override public Iterator iterator() { return innerLinkedList.iterator(); } @Override public String toString() { return innerLinkedList.toString(); } } 复制代码 4.栈的应用 　　前面说到，栈在许多算法中被广泛的使用。我们在这里举一个简单的例子，来介绍栈的应用场合。 算术表达式括号匹配校验 　　在算术表达式中，通过添加括号来设置运算符的优先级，进而控制计算的顺序。如果粗心大意导致括号没有匹配，会导致算术表达式语法错误，无法计算出正确结果。因此需要一种括号匹配的校验，来防止这种错误。 　　我们的算术表达式支持：小括号"()"、中括号"[]"、大括号"{}"。简单起见，当前括号匹配算法实现不支持括号优先级的校验。 常量及辅助方法： 复制代码 /** * 括号匹配 工具类 * */ public final class ParenthesisMatchingUtil { /** * 左 小括号 * */ private static final char PARENTHESES_OPEN = '('; /** * 右 小括号 * */ private static final char PARENTHESES_CLOSE = ')'; /** * 左 中括号 * */ private static final char BRACKET_OPEN = '['; /** * 右 中括号 * */ private static final char BRACKET_CLOSE = ']'; /** * 左 大括号 * */ private static final char BRACES_OPEN = '{'; /** * 右 右括号 * */ private static final char BRACES_CLOSE = '}'; /** * 判断当前字符是否是 左括号 * */ private static boolean isParenthesisOpen(char target){ return (target == PARENTHESES_OPEN) || (target == BRACKET_OPEN) || (target == BRACES_OPEN); } /** * 判断当前字符是否是 右括号 * */ private static boolean isParenthesisClose(char target){ return (target == PARENTHESES_CLOSE) || (target == BRACKET_CLOSE) || (target == BRACES_CLOSE); } /** * 判断左右括号是否匹配 * */ private static boolean isMatch(char left, char right){ return (left == PARENTHESES_OPEN && right == PARENTHESES_CLOSE) || (left == BRACKET_OPEN && right == BRACKET_CLOSE) || (left == BRACES_OPEN && right == BRACES_CLOSE); } } 复制代码 校验算法实现： 复制代码 　　/** * 判断表达式中的括号是否匹配 * @param expression 表达式 * */ public static boolean bracketsMatch(String expression){ Stack stack = new VectorStack<>(); //:::将字符串转换为字符数组，进行遍历 char[] expressionChars = expression.toCharArray(); for(char targetChar : expressionChars){ //:::如果当前字符是 左括号 if(isParenthesisOpen(targetChar)){ //:::左括号 压入栈中 stack.push(targetChar); //:::如果当前字符是 右括号 }else if(isParenthesisClose(targetChar)){ //:::如果当前栈为空 if(stack.isEmpty()){ //:::左括号少于右括号 (校验失败) return false; } //:::查看栈顶左括号 char leftParenthesis = stack.peek(); //:::"栈顶左括号" 和 "当前右括号" 匹配 if(isMatch(leftParenthesis,targetChar)){ //:::栈顶左括号出栈 stack.pop(); }else{ //:::左右括号类型不匹配 (校验失败) return false; } } 　　　　　　　//:::其它字符不进行处理 } //:::遍历结束 if(stack.isEmpty()){ //:::如果栈为空,说明括号完全匹配 (校验成功) return true; }else{ //:::如果栈不为空，左括号多于右括号 (校验失败) return false; } } 复制代码 5.栈的性能 　　栈作为线性表的限制性封装，其性能和其内部作为基础的线性表相同。 　　空间效率： 　　　　向量栈的空间效率和内部向量相似，效率很高。 　　　　链表栈的空间效率和内部链表相似，效率略低于向量栈。 　　时间效率： 　　　　栈的常用操作，pop、push、peek都是在线性表的尾部进行操作。因此无论是向量栈还是链表栈，栈的常用操作时间复杂度都为O(1)，效率很高。 6.栈的总结 　　虽然从理论上来说，栈作为一个功能上被限制了的线性表，完全可以被线性表所替代。但相比线性表，栈结构屏蔽了线性表的下标等细节，只对外暴露出必要的接口。栈的引入简化了许多程序设计的复杂度，让使用者的思维能够聚焦于算法逻辑本身而不是其所依赖数据结构的细节。 　　通常，暴露出不必要的内部细节对于使用者是一种沉重的负担。简单为美，从栈的设计思想中可见一斑。 　　这篇博客的代码在我的 github上：https://github.com/1399852153/DataStructures ，文章还存在许多不足之处，请多指教。https://www.cnblogs.com/xiaoxiongcanguan/p/10061255.html