coolliyong.github.io

数据结构 栈

特点

• js 中没有栈这种数据结构（只是 api 层面没有），底层还是会有函数调用栈或者其他内部的地方用到的

• 栈也是一种线性结构，和数组非常相似，但是数组是有两个头，但是栈只有一个口，从一个口入栈和出栈，后进先出（last in first out）

• 举个例子：书桌，咱们会把最大、最厚的书放在最下面，然后依次放书，然后要拿书的时候要先把上面的拿开，才能拿到最下面一本。 例子 2：15 号线望京西站，人非常多，大家不断的往地铁里面走，先进来的走到最里面了，到了望京站，大家都下车，这时候最方便的是外面的人，这种情况就成为先进后出，后进先出

栈的模拟实现

function Stack() {
  this._stack = []
  // 1. add 添加到栈顶
  // 2. pop 弹出栈顶
  // 3. peek 查看栈顶元素
  // 4. isEmpty 是否为空
  // 5. size 长度
  // 6. toString 返回 所有栈元素 string格式
}

Stack.prototype.add = function(el) {
  this._stack.unshift(el)
}

Stack.prototype.pop = function() {
  return this._stack.shift()
}

Stack.prototype.peek = function() {
  return this._stack[0]
}

Stack.prototype.isEmpty = function() {
  return this._stack.length === 0
}

Stack.prototype.size = function() {
  return this._stack.length
}

Stack.prototype.toString = function() {
  return this._stack.join(' ')
}

栈 155 最小栈

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) – 将元素 x 推入栈中。 pop() – 删除栈顶的元素。 top() – 获取栈顶元素。 getMin() – 检索栈中的最小元素。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个解法并非最优解，

/**
 * initialize your data structure here.
 */
var MinStack = function() {
  this._stack = []
  this.min = []
}

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  const list = this._stack
  // 如果min 为空 或者 val 小于 栈顶
  if (!this.min.length || x < this.min[0]) {
    this.min.unshift(x)
  }

  list.unshift(x)
}

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  const list = this._stack
  // 移除栈顶元素
  const k = this._stack.shift()

  if (list.length <= 0) {
    return k
  }

  // 每出栈一个元素，清空最小栈，并排序得到最小数进栈
  this.min = []
  let min = list[0]
  for (let i = 1; i < list.length; i++) {
    if (list[i] < min) min = list[i]
  }
  this.min.unshift(min)
  return k
}

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
  return this._stack[0]
}

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.min[0]
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */