JavaScript数据结构之栈

[heyushuo]

栈的定义

栈 是一种遵从先进后出或者说后进先出(LIFO,last-in-first-out)原则的有序集合;由于栈具有先进后出(后进先出)的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元
素，必须先拿掉上面的元素。

咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。

栈的实现

在 JavaScript 中数组专门提供了push()和 pop()方法，以便
实现类似栈的行为,接下来咱们使用ES6的class实现一个栈

首先我们需要知道栈常用的几个方法如下

• push 添加一个元素到栈顶
• pop 弹出栈顶元素
• peek 返回栈顶元素
• size 返回栈里元素的个数
• clear 清空栈

代码实现如下:

class stack {
  constructor(){
    this.stackArr=[]
  }
  push(elm){
    this.stackArr.push(elm); //向栈中添加一个数据
  }
  pop(elm){
    return this.stackArr.pop(); //把栈顶的元素移除,并返回栈顶元素
  }
  peek(){
    return this.stackArr[this.stackArr.length]; //返回栈顶元素但是不会移除栈顶元素
  }
  size() {
    return this.stackArr.length; // 返回栈的大小
  }
  clear() {
    this.stackArr = []; // 清空栈
  }
}

接下来使用一下咱们定义的栈

var stack = new Stack();

stack.push(1)
stack.push(3)

console.log(stack.peek()); //3
console.log(stack.size()); //2
console.log(stack.pop()); //3
//使用栈的pop后,返回栈顶元素并移除栈顶元素
console.log(stack.size()); //1

通过上边栈的实现我们也发现了,栈不会像数组那样通过索引可以获取到元素,栈提供的方法只允许你操作栈顶的元素，也就是数组的最后一个元素.

栈的应用

1.假设想将数字 n 转换为以 b 为基数的数字，实现转换的算法如下(可以将数字转化为二至九进制的数字)

function mulBase(num, base) {
  var s = new Stack();
  do {
    s.push(num % base) //把第一个余数放入栈中
    num = Math.floor(num / base); //拿到接下来需要计算的值
  } while (num > 0);
  var result = "";
  while (s.size() > 0) {
    result += s.pop()
  }
  return result;
}
console.log(mulBase(5, 2)); //101

2.回文的判断

平时大家判断回文都会用如下的方法

function isPalindrome(word){
 return word.split('').reverse().join('')==word
}

接下来咱们使用栈来实现

function isPalindrome(word) {
  var s = new Stack();
  for (let i = 0; i < word.length; i++) {
    s.push(word[i])
  }
  var result = "";
  while (s.size() > 0) {
    result += s.pop();
  }
  // console.log(result);
  // console.log(word);
  return result == word
}
console.log(isPalindrome('101'));
console.log(isPalindrome('abc'));

3.给定一个字符串(([]()[])[]),逐个提取出()/[],并输出出来

解题思路

• 循环字符串把( 或 [ 压入栈中
• 当不是( 或 [的时候,和栈中最后一个进行比较

var str = "(([]()[])[])";
var stack = [];
for (let i = 0; i < str.length; i++) {
  var item = str[i]
  if (item == '(' || item == '[') {
    stack.push(item)
  } else {
    var lastItem = stack[stack.length - 1]
    if (countNum(item) + countNum(lastItem) == 0) {
      console.log(lastItem + item);
      stack.pop(); //抵消之后需要把队列中的删除
    } else {
      stack.push(item)
    }
  }
}
//为了方便匹配每个字符，将字符用数字表示
function countNum(chr) {
  switch (chr) {
    case '(':
      return 1;
      break;
    case ')':
      return -1;
      break;
    case '[':
      return 2;
      break;
    case ']':
      return -2;
      break;
    default:
      return 0;
  }
}

4.判断这段字符串()ss()ss(sss(ss)(ss)ss)里边的括号是否是成对出现的

()ss()ss(sss(ss)(ss)ss) 合法 ()ss()ss(sss(ss)(ss)ss)) 不合法

此题的思路可以用对象的思路,分别在对象中存左括号和右括号的个数,如果相等则正确,或者使用数组两个数组分别保存左括号和右括号,如果两个数组长度相等则正确

下边咱们使用栈来解决这个问题

• 遍历字符串
• 如果是左括号，就压入栈中
• 如果是右括号，判断栈是否为空，如果不为空，则把栈顶元素移除(也就是在栈中存放的左括号)，这对括号就抵消了；如果不为空，就说明缺少左括号，返回 false
• 循环结束后，看栈的大小是否为 0，如果不为 0，就说明没有成对出现，为 0，就说明全部抵消了。

function isDouuble(str) {
  const stack = new Stack();
  const len = str.length;
  for (let i = 0; i < len; i++) {
    const item = str[i];
    if (item === "(") {
      stack.push(item); // 入栈
    } else if (item === ")") {
      if (stack.size() === 0) {
        return false;
      } else {
        stack.pop(); // 出栈
      }
    }
  }
  return stack.size() === 0;
}

参考

《JavaScript 数据结构与算法》

JavaScript 数据结构之栈