数据结构-栈

js 中数组就是一个类栈结构，pop()和 push(方法都符合栈的结构)，
可以采用 length-1 的方式，获取栈顶元素

下面采用构造函数的方式模拟栈结构

栈的特征：

1. 先进后出
2. 栈顶指针
3. 进栈，出栈，获取栈顶元素，清空栈,获取栈长度五个主要方法
   将以上抽象为代码

function Stack() {
  this.dataStore = []
  this.push = push
  this.pop = pop
  this.peek = peek
  this.clear = clear
  this.length = length
  this.top = 0 // 栈顶指针
}

/* 
  push和pop方法都是采用 top栈顶指针去存取数据，并没有修改数据源
 */
function push(element) {
  this.dataStore[this.top++] = element
}
function pop() {
  // 这里只是修改了栈顶指针，并没有对数据原进行修改
  return this.dataStore[--this.top]
}
function peek() {
  return this.dataStore[this.top - 1]
}
function clear() {
  this.top = 0
}
function length() {
  return this.top
}

利用栈结构，进行进制间的转换(下面的只适用 2-9 进制)

function mulBase(num, base) {
  let s = new Stack()
  do {
    s.push(num % base)
    num = Math.floor(num / base)
  } while (num > 0)
  let res = ''
  while (s.length() > 0) {
    res += s.pop()
  }
  return res
}
/* 
  以 8 转二进制 为例
  8 / 2 = 4 余 0 s[0]
  4 / 2 = 2 余 0 s[0,0]
  2 / 2 = 1 余 0 s[0,0,0]
  1 / 2 = 0 余 1 s[0,0,0,1]
  进行出栈操作  得到 1000
 */

利用栈判断是否为回文串

function isPalindrome(word) {
  let s = new Stack()
  for (let i = 0, len = word.length; i < len; i++) {
    s.push(word[i])
  }
  let reWord = ''
  while (s.length() > 0) {
    reWord += s.pop()
  }
  return word === reWord ? true : false
}

栈操作，还可用于解决递归操作, 拿简单的阶乘做例子

function factorial(n) {
  if (n == 0) {
    return 1
  } else {
    return n * factorial(n - 1)
  }
}

// 采用栈结构
function fact(n) {
  let s = new Stack()
  while (n > 1) {
    s.push(n--)
  }
  let res
  while (s.length() > 0) {
    res *= s.pop()
  }
  return res
}

在深度优先查询，也需要采用的栈先进后出的特点

//  深度优先查询
function deep(arr, attr) {
  let dataArr = [...arr]
  let res
  while (dataArr.length > 0) {
    let temp = dataArr.pop() // 数组pop()，尾部删除
    if (temp[attr]) {
      res.push[temp]
    }
    let children = temp.children
    if (children) {
      for (item of children) {
        dataArr.push(item)
      }
    }
  }
  return res
}

// 采用栈处理递归问题

//练习1  将多维数组展平为一维 递归的方式
let arr = [[8,9],1,2,3,[4,5,[6]]]
function flatArr(arr) {
  return [].concat( ...arr.map(item => Array.isArray(item) ? flatArr(item) : item))
}

// 采用 generator的方式
// 这种写法的优势在于 genenator 默认返回一个遍历器对象
// 因此，不需要关心返回的是什么东西
function *flatArrr(arr) {
  for(let i =0; i< arr.length; i++) {
    if(Array.isArray(arr[i])) {
      // generator函数递归调用自身需要 加 * 即 yeild * 
      yield *flatArrr(arr[i])
    } else {
      yield arr[i]
    }
  }
}
const aa = flatArrr(arr)
for(let i of aa) {
  console.log(i);
}

// 采用栈解决
function flatArrr(arr) {
  const r = []
  const stack = arr.slice()
  while(stack.length) {
    const cur = stack.shift()
    if(Array.isArray(cur)) {
      stack.unshift(...cur)
    } else {
      r.push(cur)
    }
  }
  return r
}
console.log(flatArrr(arr));

// 练习3 括号平衡问题
// ()[]{} ， [{}()] 这种平衡的
// ([](), )({}[] 非平衡的
function is_balanced(str) {
  const arr = [...str]
  const stack = [arr.shift()]
  while(arr.length) {
    const n = stack[stack.length-1]
    const c = arr.shift()
    const is_matched = is_match(n,c)
    if(is_matched) {
      stack.pop()
    } else {
      stack.push(c)
    }
  }
  return stack.length === 0
}
function is_match(n,c) {
  return (n==='[' && c === ']') ||  (n==='(' && c === ')') || (n==='{' && c === '}')
}
console.log(is_balanced('[](){}'), is_balanced('[](){}('));

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦