第三章 栈

---

ps：整个文章所涉及的源代码我都发布在我的Github主页上，大家可以自行下载，如果对您有一丢丢的帮助的话，记得在我的github项目上点上【star】哟，当然不要忘了在本篇文章下方【点赞】哟~，你们的支持将是我最大的动力！

（利他之心是每个优秀开发者的传统美德！——@惜墨的少年）

---

对栈的操作

栈是一种特殊的列表，栈内元素只能通过列表的一端访问，这一端称为栈顶。栈是被称为一种后进先出的数据结构。所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。

对栈的两种操作：入栈和出栈。入栈使用push() 方法，出栈使用pop() 方法。另一个常用操作是预览栈顶的元素。pop() 可以访问栈顶的元素，同时栈顶元素被永久性删除。peek() 方法则只返回栈顶元素，而不删除它。

栈的实现

实现一个栈，首先要决定存储数据的底层数据结构。这里采用数组。

Stack类的构造函数

实现push方法，向栈中压入新元素时，保存到top所对应的位置，top+1，指向数组下一个空位置：

实现push方法

pop与push相反，返回栈顶元素，同时top自减1：

实现pop方法

peek方法返回数组第top-1位置的元素，即栈顶元素。如果空栈调用peek() ，结果为undefined。

实现peek方法

length方法可以知道栈内存储了多少个元素，返回top值：

length()

将top的值设为0，可以清空一个栈

clear()

测试Stack类的实现：

Stack类的实例化测试

测试代码输出结果：

测试结果

将数字转换为二进制和八进制：

进制转换算法 测试转换为二进制和八进制数 测试结果

回文

参加过竞赛的小伙伴们应该知道，回文就是指一个单词、短语或数字，从前往后写和从后往前写都是一样的现象。比如“dad”，“racecar”就是回文，数字10001也是回文。通过对栈的操作很容易判断字符串是否回文。

判断是否回文算法实现 测试回文算法逻辑 测试结果

用栈模拟递归

常规的递归函数，计算任何数字的阶乘：

普通的递归函数计算阶乘

使用栈模拟递归过程

栈模拟递归算法