Javascript-数据结构与算法之栈

网络上关于栈的说明相比大家已经看过很多了，接下来我用这张图来简单的表示一下什么是栈

栈.gif
它的数据结构为后进先出（Last Input First Output - LIFO）先入栈的元素会被放到栈底，出栈的话从栈顶先出。举个生活的例子：子弹夹（最先被压入的子弹总是最后才被发射出去）

接下来我们整理一下栈这个数据结构有哪些方法
1.入栈 push
2.出栈 pop
3.查看栈顶元素 top
4.查看栈的大小 getSize
5.查看栈是否为空 isEmpty
6.清除栈 clean
接下来我们用代码来实现一个栈

function Stack() {
  let data = [];
  this.push = function(item) {
    data.push(item)
  }
  this.pop = function() {
    if(this.isEmpty()) {
      return false;
    } else {
      return data.pop();
    }
  }
  this.top = function() {
    return data[data.length];
  }
  this.getSize = function() {
    return data.length;
  }
  this.isEmpty = function() {
    return data.length === 0;
  }
  this.clean = function() {
    data = [];
  }
}

看到这里不知道大家会不会有疑惑。栈里面的方法数组里面都有，那我为什么不直接用数组去解决？而要用栈呢？
那接下来我给大家出到题目
判断字符串括号的合法性：
((123)(aaa(cc)ddd)()) - 合法
(()123(aa))(c)(c))( - 不合法
解题思路：先循环字符串，找到"("将其压入栈中去，找到")"判断栈内是否为空，不为空的话使用pop()方法出栈，如果栈内为空则程序不合法。如果遍历完成栈内还有元素的话说明不合法。

接下来就是栈的实战演练代码

function legal(items) {
  let stack = new Stack();
  for(let i=0; i<items.length; i++) {
    let item = items[i];
    if(item === '(') {
      stack.push(item);
    } else if(item === ')') {
      if(stack.isEmpty()) return false;
      else stack.pop();
    }
  }
  return stack.isEmpty();
}
console.log(legal('((123)(aaa(cc)ddd)())'))    // result = true
console.log(legal('(()123(aa))(c)(c))('))      // result = false

好了，今天的分享就到这里了。有说明问题的话小伙伴们可以给我留言。（第一次写简书写的不是很好，大家请见谅~~）