小撒是一只好学的小鸭子，这天，小撒在学习算法
今天我们就来介绍几个常见的数据结构吧。
栈（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));
