[小撒学算法]堆、栈、链表

小撒是一只好学的小鸭子，这天，小撒在学习算法

今天我们就来介绍几个常见的数据结构吧。

栈（stash）

栈是一种先进后出（FILO，first-in-last-out）的数据结构，提供了压栈（push）、出栈（pop）的操作。在js中可以使用数组以及pop和push方法来实现。

相应的，队列（Queue）则是一种先进先出（FIFO，first-in-first-out）的数据结构，提供了入队（enqueue）与出队（dequeue）的操作。在js中可以使用数组以及push和shift方法来实现。

最小栈

今天我们进来实现一段小程序：我们将观察一个栈的出栈以及入栈行为，并且在任一时刻获得这个栈中最小元素的值。

一个最直观的想法是，在需要获取最小元素时，扫描栈并记录最小的元素，这样的话时间复杂度是O(n)。

而我们则要来实现O(1)的算法。也许有些同学会提出这样的想法：使用一个变量记录当前栈内最小的元素。这个做法的问题在于，如果当前最小的元素出栈了，我们怎么获取到接下来的最小的元素呢？

当然我们实现最小栈的算法也是基于这个思想的，只是我们将不止记录一个最小元素，而是一系列最小元素。为此我们将建立一个额外的栈（最小栈）：

• 当元素入栈时，如果新元素不大于最小栈的栈顶元素，则同样将该元素入栈最小栈
• 当元素出栈时，如果出栈元素的值与最小栈栈顶元素相同，则最小栈栈顶元素出栈
• 在任意时刻，最小栈栈顶的元素即是栈中最小的元素。

最小栈

class MinStack {
  constructor() {
    this.stack = [];
    this.minStack = [Math.min()];
  }

  push(item) {
    this.stack.push(item);
    if (item <= this.min()) this.minStack.push(item);
  }

  pop() {
    const item = this.stack.pop();
    if (item === this.min()) this.minStack.pop();
    return item;
  }

  min() {
    return this.minStack[this.minStack.length - 1];
  }
}

const data = [11, 7, 9, 5, 5, 2, 3, 1];
const minStack = new MinStack();

while (data.length) {
  const item = data.shift();
  minStack.push(item);
  console.log('push', item, minStack.min(), minStack.stack.join(','));
}

while (minStack.stack.length) {
  const item = minStack.pop();
  console.log('pop', item, minStack.min(), minStack.stack.join(','));
}

在这里小撒在minStack中提前放入了Math.min()这一最大值，这样的手段称为『哨兵』，是一种简化边际处理的技巧。

链表（linked list）

链表是一种类似数组的数据结构，链表分为单向链表和双向链表，其中的每一项不仅包含值还包含指向相邻元素的指针。链表的优势在于插入或删除元素时，只要修改相邻元素的指针指向、而不必移动元素，因此具有更好的插入与删除性能。不过相应的如获得链表第n项的值这样的操作将没有那么直观了。

这里我们将进行的小练习是，反转一个单向链表。

我们通过图示来了解一下这个过程：

反转单向链表

即我们只要按次序将一个个元素放到新链表的头部就可以了。

const arr2list = function (arr) {
  const head = {
    val: arr[0],
  };

  let current = head;

  for (let i = 1; i < arr.length; i++) {
    const next = {
      val: arr[i],
    };
    current.next = next;
    current = next;
  }
  return head;
};

const list = arr2list([1, 2, 3, 4, 5, 6]);

const logList = function (list) {
  const arr = [];
  let head = list;

  while (head.next) {
    arr.push(head.val);
    head = head.next;
  }
  arr.push(head.val);

  console.log(arr);
}

const reverse = function (list) {
  let head = list;
  let next = list.next;
  let nextNext = list.next.next;

  head.next = null;

  let newHead = next;
  newHead.next = head;

  while (true) {
    next = nextNext;
    if (!next) break;
    nextNext = next.next;
    const oldHead = newHead;
    newHead = next;
    newHead.next = oldHead;
  }

  return newHead;
}

logList(list);
logList(reverse(list));