JS 算法与数据结构之栈
列表是一种最自然的数据组织方式，如果数据存储的顺序不重要，且无需对数据进行查找，那么列表是一种再好不过的数据结构，但对于其它一些应用，列表就显得太过简陋，我们需要一种更复杂的数据结构——栈
一、 什么是栈
栈是一种后入先出（LIFO，Last-in-first-out） 的数据结构，其数据只能在栈顶添加或删除，因此操作高效快速。
栈顶：栈内的元素只能通过列表的一端访问，这一端称为栈顶。
由于栈后入先出的特点，所以任何不在栈顶的元素都无法访问，要得到栈底的元素，需要先拿掉上面的元素。
二、栈的操作
1、入栈
使用 push() 方法，将一个元素压入栈。
2、出栈
使用 pop() 方法，将一个元素弹出栈。
3、预览栈顶元素
pop() 方法虽然可以访问栈顶元素，但调用后栈顶元素即被删除了，
而 peek() 方法则只返回栈顶元素，不删除它，用来预览栈顶元素。
4、记录栈顶元素位置
我们用变量 top 来记录栈顶元素的位置，标记哪里可以加入新元素；
当向栈内压入元素时，top 值增大，当从栈内弹出元素时，top 值减小。
5、清除栈内所有元素
用 clear() 方法来清除栈内所有元素
6、记录栈内元素个数
用变量 length 来记录栈内元素的个数
7、表示栈内是否含有元素
用 empty 属性来表示栈内是否含有元素，用 length 也可达到同样的目的
三、栈的实现
1、定义 Stack 类
function Stack() {
this.dataStore = []
this.top = 0
this.push = push
this.pop = pop
this.peek = peek
}这里用数组 dataStore 保存栈内元素，构造函数将其初始化为一个空数组。
变量 top 记录栈顶位置，被构造函数初始化为 0，表示栈顶对应数组的起始位置 0。
2、实现 push 方法
当向栈中压入一个新元素时，需要将其保存在数组中变量 top 所对应的位置，然后将 top 值加 1，让其指向数组中下一个空位置。
function push(element) {
this.dataStore[this.top++] = element
}3、实现 pop 方法
pop 和 push 相反——返回栈顶元素，同时将变量 top 的值减 1。
function pop() {
return this.dataStore[--this.top]
}关于 i++ 和 ++i 使用 i++ 时，i 先将自身的值赋值给变量 a，然后再自增 1 使用 ++i 时，i 先将自身的值自增 1，再将自增后的值赋值给变量 a
4、实现 peek 方法
peek 方法返回数组的第 top-1 个位置的元素，即栈顶元素。
function peek() {
return this.dataStore[this.top - 1]
}如果对一个空栈调用 peek 方法，结果为 undefined（因为栈是空的，栈顶没有任何元素）。
5、实现 length 方法
length 方法通过返回变量 top 值的方法返回栈内的元素个数，可用来了解栈内存储了多少个元素。
function length() {
return this.top
}6、实现 clear 方法
clear 方法将变量 top 的值设为 0，用来清空一个栈。
function clear() {
this.top = 0
}7、测试 Stack 类的实现
var s = new Stack()
s.push('a')
s.push('b')
s.push('c')
console.log(s.length()) // 3
console.log(s.peek()) // "c"
var poped = s.pop()
console.log(poped) // "c"
console.log(s.peek()) // "b"
s.push("d")
console.log(s.peek()) // "d"
s.clear()
console.log(s.length()) // 0
console.log(s.peek()) // undefined四、栈的实例
1、回文判断
回文：指的是一个单词、短语或数字，从前往后写和从后往前写是一样的，比如：“dad”、“racecar”。
使用栈可以轻松判断一个字符串是否是回文：
将字符串的每个字符按从左到右的顺序压入栈，栈内就保存了一个反转后的字符串，尾字符在栈顶，而首字符在栈底；
通过持续弹出栈内的每个元素就可以得到一个新的字符串，这个字符串与原字符串的顺序相反；
只需比较新字符串和原字符串是否相等即可。
function isPalindrome(word) {
var s = new Stack()
for (var i = 0; i < word.length; ++i) {
s.push(word[i])
}
var rword = ''
while (s.length() > 0) {
rword += s.pop()
}
if (word == rword) {
return true
} else {
return false
}
}
var word1 = 'hello'
var word2 = 'racecar'
console.log(isPalindrome(word1)) // false
console.log(isPalindrome(word2)) // true2、阶乘计算
递归可以用来实现阶乘运算
① 普通函数递归实现阶乘
function factorial(n) {
if (n === 0) {
return 1
} else {
return n * factorial(n - 1)
}
}
console.log(factorial(5)) // 120② 栈模拟递归实现阶乘
使用栈来模拟递归实现阶乘，先将数字从 5 到 1 压入栈，然后使用一个循环，将数字挨个弹出连乘即可。
function factorial(n) {
var s = new Stack()
while (n > 1) {
s.push(n--)
}
var product = 1
while (s.length() > 0) {
product *= s.pop()
}
return product
}
console.log(factorial(5)) // 120