【js版数据结构学习之栈】

一、认识栈

栈是一种限定仅在表尾进行插入和删除作的线性数据结构，也称为“后进先出”（Last In First Out，LIFO）的数据结构。栈的特点是只允许在一端进行插入和删除操作，这个一端被称为栈顶，另一端被称为栈底。

栈的插入操作被称为入栈（Push），删除操作被称为出栈（Pop）。在栈中，元素的插入和删除操作都是在栈顶进行的，这是因为每次插入和删除元素时，都要保证最后插入的元素最先被删除，也就是所谓的“后进先出”原则。

如果允许在栈的中间位置进行插入或删除操作，那么就无法保证栈的“后进先出”的特性了，同时也会增加栈的复杂度。因此，栈被设计为仅允许在表尾进行删除和插入操作，从而保证了数据的有序性和栈的操作效率。

二、栈的封装

class Stack{
    items = []

    push(data){
        this.items.push(data)
    }

    pop(){
        return this.items.pop()
    }
//peek操作允许我们获取栈顶元素的值，而不改变栈的结构
    peek(){
        //    return this.items[this.items.length-1]
        return this.items.at(-1)
    }
    isEmpty(){
        return this.items.length===0
    }

    size(){
        return this.items.length
    }

    clear(){
        this.items = []
    }

    toString(){
        return this.items.join("")
    }
}

三、栈的应用

1. 括号匹配

LeetCode原题：

解题代码：

function isValid(s) {
 const stack = []; // 创建一个空数组作为栈
 const brackets = { '(': ')', '{': '}', '[': ']' }; // 定义一个对象，存储括号类型和相应的右括号字符

 // 遍历字符串的每个字符
 for (let i = 0; i < s.length; i++) {
   // 如果当前字符是左括号，则将其推入栈中
   if (brackets[s[i]]) {
     stack.push(s[i]);
   } 
   // 如果当前字符是右括号，则需要检查其与栈顶元素是否匹配
   else if (Object.values(brackets).includes(s[i])) {
     // 如果栈为空，或者栈顶元素所对应的右括号与当前字符不匹配，则说明括号不匹配，直接返回 false
     if (stack.length === 0 || brackets[stack.pop()] !== s[i]) {
       return false;
     }
   }
 }

 // 如果遍历完成后栈中还有剩余的左括号，则说明括号不匹配，返回 false，否则返回 true
 return stack.length === 0;
}
js

2. 进制转换

function convertToBase7(num) {
 // 处理特殊情况：当 num 为 0 时，直接返回 "0"
 if (num === 0) {
   return "0";
 }

 const stack = [];
 let isNegative = false;

 // 判断 num 是否为负数，并取其绝对值
 if (num < 0) {
   isNegative = true;
   num = Math.abs(num);
 }

 // 将 num 转化为 7 进制数并压入栈中
 while (num > 0) {
   stack.push(num % 7);
   num = Math.floor(num / 7);
 }

 let result = "";

 // 如果是负数，则在结果前加上负号
 if (isNegative) {
   result += "-";
 }

 // 从栈中弹出元素并拼接到结果字符串中
 while (stack.length > 0) {
   result += stack.pop();
 }

 return result;
}
js

3. 函数调用栈模拟

函数调用栈模拟是指使用栈来模拟函数的调用过程。在程序执行时，每当一个函数被调用时，就会将该函数的相关信息（如函数名、参数等）压入栈中，并在函数执行完毕后弹出栈顶元素，回到上一个调用该函数的位置继续执行。

函数调用栈模拟通常用于深入了解函数调用的内部机制，以及调试函数相关的问题。例如，当一个函数出现了递归调用，或者多个函数之间相互调用时，使用函数调用栈模拟可以更好地理解函数之间的执行顺序和调用关系。

下面是一个简单的示例代码，演示了使用函数调用栈模拟来实现阶乘计算：

function factorial(n) {
  // 创建一个栈，用于存储函数调用的相关信息
  const stack = [];

  // 将初始调用的相关信息压入栈中
  stack.push({ n: n });

  let result = 1;

  // 不断从栈中取出元素并执行函数，直到栈为空
  while (stack.length > 0) {
    const frame = stack.pop();

    // 当 n 等于 0 时，则说明已经计算完成，将结果保存在变量 result 中
    if (frame.n === 0) {
      result = frame.result;
    } else {
      // 否则，将当前调用的相关信息压入栈中，并继续递归调用函数
      stack.push({
        n: frame.n - 1,
        result: frame.result * frame.n,
      });
    }
  }

  // 返回计算结果
  return result;
}

// 调用函数，计算 5 的阶乘并输出结果
console.log(factorial(5)); // 输出 120