栈结构

[conan1992]

栈结构

是一种运算受限的线性表,后进先出(LIFO)

• LIFO(last in first out)表示就是后进入的元素, 第一个弹出栈空间. 类似于自动餐托盘, 最后放上的托盘, 往往先把拿出去使用.
• 其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。
• 向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；
• 从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈结构实现

栈的操作

-push(element): 添加一个新元素到栈顶位置.

• pop()：移除栈顶的元素，同时返回被移除的元素。
• peek()：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
• isEmpty()：如果栈里没有任何元素就返回true，否则返回false。
• clear()：移除栈里的所有元素。

• size()：返回栈里的元素个数。这个方法和数组的length属性很类似。

  代码实现

  // 栈类
  function Stack() {
  // 栈中的属性
  var items = []
  
  // 栈相关的方法
  // 压栈操作
  this.push = function (element) {
      items.push(element)
  }
  
  // 出栈操作
  this.pop = function () {
      return items.pop()
  }
  
  // peek操作
  this.peek = function () {
      return items[items.length - 1]
  }
  
  // 判断栈中的元素是否为空
  this.isEmpty = function () {
      return items.length == 0
  }
  
  // 获取栈中元素的个数
  this.size = function () {
      return items.length
  }
  }

  应用

  1. 十进制转二进制

     function test(num){
     var stack = new Stack();
     var result = 0;
     while(num>0){
     var a = num%2;
     num = (num-a)/2;
     stack.push(a)
     }
     console.log(stack.get())
     while(!stack.isEmpty()){
     result += stack.pop() * Math.pow(10, stack.size())
     }
     return result
     }

  2. 匹配括号

     var isValid = function (s) {
     let map = {
     '(': -1,
     ')': 1,
     '[': -2,
     ']': 2,
     '{': -3,
     '}': 3
     }
     let stack = []
     for (let i = 0; i < s.length; i++) {
     if (map[s[i]] < 0) {
     stack.push(s[i])
     } else {
     let last = stack.pop()
     if (map[last] + map[s[i]] != 0) return false
     }
     }
     if (stack.length > 0) return false
     return true
     };

参考链接

• 数据结构(三)之栈结构