栈

栈是一种后入先出（LIFO）的数据结构。
与队列不同，栈是一个 LIFO 数据结构。通常，插入操作在栈中被称作入栈 push 。与队列类似，总是在堆栈的末尾添加一个新元素。但是，删除操作，退栈 pop ，将始终删除队列中相对于它的最后一个元素。

后入先出的数据结构

入栈与出栈
在 LIFO 数据结构中，将首先处理添加到队列中的最新元素。

栈-实现

为了实现栈，在 js 中可以使用数组。根据栈的特点， 栈有以下可用的方法：

• push(element(s)) ：添加一个（或几个）新元素到栈顶。
• pop() ：移除栈顶的元素，成功返回 true，失败返回 false。
• top() ：返回栈顶的元素，不对栈做任何修改（这个方法不会移除栈顶的元素，仅仅返回它）。
• isEmpty() ：如果栈里没有任何元素就返回 true，否则返回 false。
• clear() ：移除栈里的所有元素。
• size() ：返回栈里的元素个数。这个方法和数组的 length 属性很类似。

var Stack = function() {
  this.items = [];
};
Stack.prototype.push = function(element) {
  this.items.push(element);
};
Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return false;
  }
  this.items.pop();
  return true;
};
Stack.prototype.top = function(element) {
  return this.items[this.items.length - 1];
};
Stack.prototype.isEmpty = function(element) {
  return this.items.length === 0;
};
Stack.prototype.clear = function(element) {
  this.items = [];
};
Stack.prototype.size = function(element) {
  return this.items.length;
};

最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

var MinStack = function() {
  this.items = [];
};
MinStack.prototype.push = function(x) {
  this.items.push(x);
};
MinStack.prototype.pop = function() {
  this.items.pop();
};
MinStack.prototype.top = function() {
  return this.items[this.items.length - 1];
};
MinStack.prototype.getMin = function() {
  if (this.items.length > 0) {
    var min = this.items[0];
    this.items.forEach(function(item) {
      min = Math.min(item, min);
    });
    return min;
  } else {
    return false;
  }
};

有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']'  的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例  2:
输入: "()[]{}"
输出: true

示例  3:
输入: "(]"
输出: false

示例  4:
输入: "([)]"
输出: false

示例  5:
输入: "{[]}"
输出: true

var isValid = function(s) {
  if (s.length % 2 !== 0) {
    return false;
  }
  function isPaired(a, b) {
    var pairedList = ['()', '[]', '{}'];
    return pairedList.includes(a + b + '');
  }
  var stack = [];
  var left = ['(', '[', '{'];
  var right = [')', ']', '}'];
  var res = true;
  for (var i = 0; i < s.length; i++) {
    if (i === 0 && right.includes(s[i])) {
      res = false;
      break;
    }
    if (left.includes(s[i])) {
      stack.push(s[i]);
    }
    if (right.includes(s[i])) {
      if (!isPaired(stack.pop(), s[i])) {
        res = false;
        break;
      }
    }
  }
  if (stack.length > 0) {
    res = false;
  }
  return res;
};

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/queue-stack/ghqur/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。