栈结构
初识栈结构
栈(stack) 又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素，从一个栈删除元素称作出栈或退栈，它是把栈顶元素删除掉使其相邻的元素成为新的栈顶元素。
简而言之，栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待删除的元素都保存在栈的 同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。 注：LIFO：last in first out 图例：
JavaScript 中可以通过数组实现栈数据结构。栈是一种遵循后进先出（LIFO）原则的数据结构，它只允许在栈顶进行插入和删除操作。
栈结构的封装
栈声明方法举例
push(element(s))：添加一个（或几个）新元素到栈顶。
pop()：移除栈顶的元素，同时返回被移除的元素。
peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返 回它）。
isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
clear()：移除栈里的所有元素。
size()：返回栈里的元素个数。这个方法和数组的length属性很类似。
封装-function
添加
实现添加的可以使用push。这个方法负责往栈里添加新元素，有一点很重要：该方法只添加元素到栈顶，也就是栈的末尾。 push 方法可以这样写：
this.push = function(element){
items.push(element);
};
移除
接着来实现移除，主要用来移除栈里的元素，使用的是pop方法。 栈遵从LIFO原则，因此移出的是最后添加进去的元素。 栈的pop方法可以这样写：
this.pop = function(){
return items.pop();
};
查看
查看栈顶元素
因为栈顶就是最后进入的元素，类内部是用数组保存元素的，所以访问数组的最后一个元素可以用 length - 1,或者使用 at(-1)
this.peek = function(){
// return items[items.length-1];
return items.at(-1)
};
检查栈是否为空
可以直接使用length == 0判断，如果栈为空的话将返回true，否则就返回false
this.isEmpty = function(){
return items.length == 0;
};
检查栈的长度
类似于数组的length属性，我们也能实现栈的length。对于集合，最好用size代替length。 因为栈的内部使用数组保存元素，所以能简单地返回栈的长度
this.size = function(){
return items.length;
};
示例代码
function Stack() {
//保存栈里的元素
let items = [];
//添加新元素
this.push = function(element){
items.push(element);
};
//移除元素
this.pop = function(){
return items.pop();
};
//查看栈顶元素
this.peek = function(){
return items[items.length-1];
};
//检查栈是否为空
this.isEmpty = function(){
return items.length == 0;
};
//检查栈的长度
this.size = function(){
return items.length;
};
//各种属性和方法的声明
}
封装-Class
代码示例
<script>
class Stack {
constructor() {
this.items = []
}
pop() {
return this.items.pop()
}
push(data) {
this.tiems.push(data)
}
peek() {
// return this.items[items.length - 1]
return this.item.at(-1)
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
clear() {
this.items = []
}
toString() {
console.log(items.toString())
}
}
let stack = new Stack()
</script>
栈结构的应用
封装栈结构来实现十进制到二进制的转换
代码示例
<script>
class Stack {
constructor() {
this.items = []
}
pop() {
return this.items.pop()
}
push(data) {
this.items.push(data)
}
peek() {
// return this.items[items.length - 1]
return this.item.at(-1)
}
isEmpty() {
return this.items.length === 0
}
size() {
return this.items.length
}
clear() {
this.items = []
}
toString() {
console.log(items.toString())
}
}
function convert(decNumber, base) {
let remStack = new Stack()
let number = decNumber
let string = ""
let baseString = "0123456789ABCDEF"
while (number > 0) {
remStack.push(number % base)
number = Math.floor(number / base)
}
while (!(remStack.isEmpty())) {
string += remStack.pop()
}
return string
}
convert(50, 2) // 二进制转换
convert(50, 8) // 八进制转换
convert(500, 16) // 十六进制转换
</script>
---控制台---
convert(50, 2)
110010
convert(50, 8)
62
convert(500, 16)
1F4
实现进制转换关键点
辗转相除法
50 % 2 0
25 % 2 1
12 % 2 0
6 % 2 0
3 % 2 1
1 % 2 1
110010
50 % 8 2
6 % 8 6
62
500 % 16 4
31 % 16 (15) => 对应 F
1 % 16 1
1F4
实现16进制转换关键点
baseString = "0123456789ABCDEF" 的设置
在 JavaScript 中使用栈数据结构的好处
实现递归调用：函数调用过程中，每次函数调用都会将新的函数帧（frame）压入栈中，待函数返回时再从栈中弹出。这就是递归调用所依赖的栈结构。 实现浏览器的前进后退功能：浏览器的前进后退功能依赖于两个栈，分别用来维护已经访问过的网页和下一个要访问的网页；用户点击“后退”时，将当前网页从已访问网页的栈中弹出，并将其压入下一个要访问的网页栈中。 对表达式求值：使用栈可以方便地对表达式进行求值，例如判断表达式中括号是否匹配、转换中缀表达式为后缀表达式等。 实现回溯算法：在搜索算法中，一般使用栈数据结构来保存路径信息，当搜索到某一层无解时，直接从栈中弹出该状态并回溯到上一层。
