栈结构

[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
};

参考链接

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