接下来我将为大家讲解JS中数据结构之栈的完整攻略。
一、栈的定义
栈是一种受限的线性数据结构,它具有先进后出(Last In First Out, LIFO)的特点,即后进入的元素先出来。栈主要有两个操作:入栈和出栈,同时还需要考虑栈空和栈满两种特殊情况。
二、栈的实现
在JS中,可以通过数组来实现栈的功能。下面是一个实现栈的类:
class Stack {
constructor() {
this.items = []; // 存储元素
}
push(element) { // 入栈
this.items.push(element);
}
pop() { // 出栈
return this.items.pop();
}
peek() { // 返回栈顶元素
return this.items[this.items.length - 1];
}
isEmpty() { // 判断栈是否为空
return this.items.length === 0;
}
size() { // 返回栈的大小
return this.items.length;
}
clear() { // 清空栈
this.items = [];
}
}
三、栈的应用
1. 判断括号是否匹配
栈可以用来判断括号是否匹配。例如给定一个字符串,其中包含一些括号,判断这些括号是否匹配。
function isMatchingBrackets(str) {
const stack = new Stack();
for (let i = 0; i < str.length; i++) {
if (str[i] === '(' || str[i] === '[' || str[i] === '{') {
stack.push(str[i]);
} else if (str[i] === ')' && stack.peek() === '(') {
stack.pop();
} else if (str[i] === ']' && stack.peek() === '[') {
stack.pop();
} else if (str[i] === '}' && stack.peek() === '{') {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
console.log(isMatchingBrackets('([]{})')); // true
console.log(isMatchingBrackets('([]{})}')); // false
2. 函数调用栈
栈被广泛应用于函数调用过程中的“调用栈”中。当一个函数被调用时,它的返回地址和参数等信息被压入栈中,当函数执行完毕时,这些信息又被弹出栈。
下面是一个递归函数的示例:
function factorial(n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
console.log(factorial(5)); // 输出 120
这个函数用到了递归,每次调用时都会将当前的n值压入栈中,当递归结束时才开始弹出栈中保存的信息,计算阶乘的值。
四、总结
本文介绍了JS中数据结构之栈,包括栈的定义、实现以及两个示例应用,希望对大家有所帮助。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:JS中数据结构之栈 - Python技术站