队列和栈的定义

这两个数据结构没有什么可讲的, 这里我就简要说一下, 后面直接用例题说明

• 栈(stack): 先进后出(FILO)
  可以想象一下我们生活中的桶, 我们往桶里面放东西, 后放的东西会在桶的上部, 每次按顺序取东西, 都是从上往下取, 所以后放进去的会被先取出来
• 队列(queue): 先进先出(FIFO)
  对应我们生活中的物品就是管道, 我们从一头往管道里面放东西, 另一头东西出来的顺序跟我们放的顺序是一致的, 先放进去的先出来

例题

用数组实现固定大小的栈

function Stack(arr, len) {
  this.arr = arr
  this.len = len
  this.index = -1
}

Stack.prototype = {
  push(num) {
    if (this.arr.length === this.len) {
      console.log('full')
      return
    }
    this.arr[++this.index] = num

  },
  pop() {
    if (this.arr.length === 0) {
      console.log('empty')
      return
    }
    let tmp = this.arr[this.index--]
    this.arr.length -= 1
    return tmp
  },
  peek() {
    if (this.arr.length === 0) {
      console.log('empty')
      return
    }
    return this.arr[this.index]
  }
}

Stack.prototype.constructor = Stack

用数组实现大小固定的队列

function Queue(arr, len) {
  this.start = 0
  this.end = 0
  this.size = 0
  this.arr = arr
  this.arr.length = len
}

Queue.prototype = {
  add(num) {
    if (this.size === this.arr.length) {
       console.log('queue is full')
       return
    }
    this.size++
    this.arr[this.end] = num
    this.end = this.end === this.arr.length - 1 ? 0 : this.end + 1
 
  },
  poll() {
    if (this.size === 0) {
      console.log('queue is empty')
      return
    }
    this.size--
    tmp = this.start
    this.start = this.start === this.arr.length - 1 ? 0 : this.start + 1
    return this.arr[tmp]
  },
  peek() {
    if (this.size === 0) {
      console.log ('queue is empty')
      return
    }
    return this.arr[this.start]
  }
  
}

Queue.prototype.constructor = Queue

实现一个特殊的栈

在现实栈的基本功能的基础上, 再实现返回栈中最小元素的操作.

1. pop, push, getMin操作的时间复杂度都是O(1)
2. 设计的栈类型可以使用线程的栈结构

思路:

1. 开辟两个栈, 一个data栈用来保存数据, 另一个min栈用来保存最小值
2. 第一次往data栈中push一个数时, 同时往min栈中也push这个数
3. 每次往data栈中push数时, 如果data栈中push的数小于等于min栈顶的值, 那么往min栈中push这个数, 如果data栈中push的数大于当前min栈顶的值, 把min栈顶的值再往min栈中push一次
4. 每次从data栈顶pop一个值时, 同时从min栈中pop一个值, 这样就能保证min栈顶的值永远是data栈的最小值

代码这里就不写了, 留给大家自己动手

矩阵

转圈打印矩阵

.给定一个整型矩阵matrix, 请按照转圈的方式打印它。
例如:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
打印结果为: 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10
要求: 额外空间复杂度为O(1)

思路:
这个题可以用宏观调度的思路来解决
把矩阵分层, 每层都当做是独立的, 互不影响,如图:

那么题目就变成了，从外向内, 依次打印每一层上所有的数，每层都从左上角开始打印, 顺时针打印一圈, 每层的操作互不影响, 例如:

第一层打印 1 2 3 4 5 10 15 5 6 43 22 8 3 16 11 6

进入第二层打印7 8 9 14 6 7 9 12

第三层只打印13

function print(matrix) {
  let c1 = 0
  let r1 = 0
  let c2 = matrix[0].length - 1
  let r2 = matrix.length - 1
  while (c1 <= c2 && r1 <= r2) {
    printEdge(matrix, c1++, r1++, c2--, r2--)
  }
}

function printEdge(matrix, C1, R1, C2, R2) {
  if (R1 === R2) {
    for (let i = C1; i <= C2; i++) {
      console.log(matrix[R1][i])
    }
  } else if (C1 === C2) {
    for (let i = R1; i <= R2; i++) {
      console.log(matrix[i][C1])
    }
  } else {
    let curR = R1
    let curC = C1
    while (curC != C2) {
      console.log(matrix[R1][curC])
      curC++
    }
    while (curR != R2) {
      console.log(matrix[curR][C2])
      curR++
    }
    while (curC != C1) {
      console.log(matrix[R2][curC])
      curC--
    }
    while (curR != R1) {
      console.log(matrix[curR][C1])
      curR--
    }
  }
}

链表

这部分大部分内容来自于《学习JavaScript数据结构和算法（第二版）》这本书

为什么用链表

• 不确定数组解构的容量时:
  1. 数组大小调整的成本非常大， 所以我们需要提前设置容量
  2. 通常我们不知道我们需要多少空间花费
• 添加和移除很多元素时，最好的选择就是链表

链表是什么

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个 元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。下图展 示了一个链表的结构：

用来说明链表的最流行的例子，那就是火车。一列火车是由一系列车厢（也 称车皮）组成的。每节车厢或车皮都相互连接。你很容易分离一节车皮，改变它的位置，添加或 移除它。下图演示了一列火车。每节车皮都是列表的元素，车皮间的连接就是指针：

创建链表

下面是一个LinkedList类的框架:

function LinkedList() {

  let Node = function(element) {
    this.element = element 
    this.next = null
  }

  let length = 0
  let head = null

  this.append = function(element){}
  this.insert = function(position, element){}
  this.removeAt = function(position){}
  this.remove = function(element){}
  this.indexOf = function(element){}
  this.isEmpty = function() {}
  this.size = function() {}
  this.getHead = function(){}
  this.toString = function(){}; this.print = function(){};
}

• 其中Node是一个辅助类, 表示要加入链表的结点, 它包括element, 即结点保存的值和next, 即指向下一个结点的指针
• 同样我们需要一个head, 用来保存链表的第一项
• length用来存储结点的数量
• 剩下的就是一些常用的增删改查方法

向链表尾部追加元素

向LinkedList对象尾部添加一个元素时，可能有两种场景：列表为空，添加的是第一个元 素，或者列表不为空，向其追加元素。

  this.append = function(element) {
    let node = new Node(element)
    let current
    
    if (head === null) { //列表中第一个节点
      head = node
    } else {
      current = head
      
      //循环列表，直到找到最后一项
      while (current.next) {
        current = current.next
      }
      
      //找到最后一项，将其next赋为node，建立链接
      current.next = node
      
    }
    length++ //更新列表的长度
  }

整体流程如下:

• 把element作为值传入，创建Node项

• 若链表为空, 此时head指向null, 我们把head指向node

  
  

列表最后一个节点的下一个元素始终是null。

• 如不是空链表, 要向列表的尾部添加一个元素，遍历链表的每个结点，直到找到最后一项。为此，我们需要一个指向列表中 current项的变量, 循环访问列表时，当current.next元素为null时，我们就知道已经到达列表尾部了。然后 要做的就是让当前（也就是最后一个）元素的next指针指向想要添加到列表的节点。 下图展示了这个行为:

  
  
• 别忘了递增链表的长度，这样就能控制它，轻松地得到链表的长度

从链表中移除元素

移除元素也有两种场景：第一种是移 除第一个元素，第二种是移除第一个以外的任一元素。

this.removeAt = function(position) {

  //检查越界值
  if (position > -1 && position < length) {
    let current = head
    let previous
    let index = 0

    //移除第一项
    if (positon === 0) {
      head = current.next
    } else {
        
      while (index++ < position ) {
        previous = current
        current = current.next
      }

      previous.next = current.next
    }
    length--
    return current.element

  } else {
    return null
  }
}

• 从链表中移除第一个元素的情况
  如果想移除第一个元素， 要做的就是让 head 指向列表的第二个元素。

  
  

• 移除其他项的情况
  要从列表中移除当前元素，要做的就是将previous.next和current.next链接起来。这样，当前元素就会被丢弃在计算机内存中，等着被垃圾回收器清除。

  
  

在任意位置插入元素

this.insert = function(element, position) {

    //检查越界值
    if (position > - 1 && position <= length) {
       let node = new Node(element)
      let current = head
      let index = 0
      let previous
      if (position === 0) { //在第一个位置添加
        node.next = current
        head = node
      } else {
        while (index++ < position) { 
          previous = current
          current = current.next
        }
        previous.next = node
        node.next = current
      }

      length++       
      return true
      
    } else {
      return false
    }
  }

其他方法

toString方法

this.toString = function() {
    let current = head
    let string = ''
    while (current) {
      string += current.element + (current.next ? 'n' : '')
      current = current.next
    }
    return string
  }

indexOf方法

this.indexOf(element) {
  let current = head
  let index = 0 
   
  while(current) {
    if (element === current.element) {
      return index
    }
    index++
    current = current.next
  }
  return -1
}

isEmpty、size和getHead方法

this.isEmpty = function() {
  return length === 0
}
  
this.getLength() {
  return length
}
  
this.getHead() {
  return head
}

双向链表

双向链表和普通链表的区别在于，在链表中， 一个节点只有链向下一个节点的链接，而在双向链表中，链接是双向的：一个链向下一个元素， 另一个链向前一个元素，如下图所示：

双向链表提供了两种迭代列表的方法：从头到尾，或者反过来。我们也可以访问一个特定节点的下一个或前一个元素。在单向链表中，如果迭代列表时错过了要找的元素，就需要回到列表起点，重新开始迭代。这是双向链表的一个优点。

DoublyLinkedList类所需的变动:

function DoublyLinkedList() {

  let Node = function(element){
    this.element = element
    this.next = null
    this.prev = null //新增的 
  }

  let length = 0
  let head = null
  let tail = null //新增的

  //这里是方法
  ...
}

在任意位置插入新元素

向双向链表中插入一个新项跟（单向）链表非常类似。区别在于，链表只要控制一个next 指针，而双向链表则要同时控制next和prev（previous，前一个）这两个指针。

this.insert = function(postion, element) {
  if (position > -1 && position <= length) {
    let node = new Node(element)
    let current = head
    let previous
    let index = 0
    
    if (position === 0) { //在第一个位置添加
      if (!head) { //新增的
        head = node
        tail = node
      } else {
        node.next = current
        current.prev = node //新增的
        head = node
      }
    } else if (position === length) { //最后一项, 新增的
      current = tail
      node.next = current
      current.prev = node
      tail = node
    } else {
      while (index++ < postion) {
        previous = current
        current = current.next
      }
      previous.next = node
      node.prev = previous //新增的
      
      node.next = current
      current.prev = node //新增的
    }
    length++ //更新列表的长度
    
    return true
    
  } else {
    return false
  }
}

我们来分析第一种场景：在列表的第一个位置（列表的起点）插入一个新元素。如果列表为 空（行{1}），只需要把head和tail都指向这个新节点。如果不为空，current变量将是对列表 中第一个元素的引用。就像我们在链表中所做的，把node.next设为current，而head将指向 node（它将成为列表中的第一个元素）。不同之处在于，我们还需要为指向上一个元素的指针设一个值。current.prev指针将由指向null变为指向新元素。node.prev指针已经是null，因此不需要再更新任何东西。下图演示了这个过程：

现在来分析一下，假如我们要在列表最后添加一个新元素。这是一个特殊情况，因为我们还 控制着指向最后一个元素的指针（tail）。current变量将引用最后一个元素。然后开 始建立第一个链接：node.prev将引用current。current.next指针（指向null）将指向node （由于构造函数，node.next已经指向了null）。然后只剩一件事了，就是更新tail，它将由指向current变为指向node。下图展示了这些行为：

然后还有第三种场景：在列表中间插入一个新元素。就像我们在之前的方法中所做的，迭代 列表，直到到达要找的位置。我们将在current和previous元素之间插入新元素。首先，node.next将指向current，而previous.next将指向node，这样就不会丢失节点之间的链接。然后需要处理所有的链接：current.prev将指向node，而node.prev将指向previous。下图展示了这一过程：

从任意位置删除元素

从双向链表中移除元素跟链表非常类似。唯一的区别就是还需要设置前一个位置的指针。我 们来看一下它的实现：

this.removeAt(position) {
  //检查越界值
  if (position > -1 && position < length) {
    let current = head
    let index = 0
    let previous
    
    //移除第一项
    if (position === 0) {
      head = current.next
      
      //如果只有一项，更新tail, 新增的
      if (length === 1) {
        tail = null
      } else {
        head.prve = null
      }
    }else if (position === length - 1) { //最后一项, 新增的
      current = tail
      tail = current.prev
      tail.next = null
    } else {
      
      while (index++ < length) {
        previous = current
        current = current.next
      }
      
      //将previous与current的下一项链接起来——跳过current
      previous.next = current.next
      current.next.prev = previous //新增的
    }
    
    length--
    return current.element
    
  } else {
    return null
  }
}

我们需要处理三种场景：从头部、从中间和从尾部移除一个元素。

我们来看看如何移除第一个元素。current变量是对列表中第一个元素的引用，也就是我 们 想 移 除 的 元 素 。 需 要 做 的 就 是 改 变 head 的 引 用 ， 将 其 从 current 改 为 下 一 个 元 素 （current.next）。但我们还需要更新current.next指向上一个元素的指针（因为第一个元素的prev指针是null）。因此，把head.prev的引用改为null（因为head也 指向列表中新的第一个元素，或者也可以用current.next.prev）。由于还需要控制tail的引用， 我们可以检查要移除的元素是否是第一个元素，如果是，只需要把tail也设为null。

下图勾画了从双向链表移除第一个元素的过程：

下一种场景是从最后一个位置移除元素。既然已经有了对最后一个元素的引用（tail），我 们就不需要为找到它而迭代列表。这样我们也就可以把tail的引用赋给current变量。 接下来，需要把tail的引用更新为列表中倒数第二个元素（current.prev，或者tail.prev 也可以）。既然tail指向了倒数第二个元素，我们就只需要把next指针更新为null（tail.next = null）。下图演示了这一行为：

第三种也是最后一种场景：从列表中间移除一个元素。首先需要迭代列表，直到到达要找的位）。current变量所引用的就是要移除的元素。那么要移除它，我们可以通过更新 previous.next和current.next.prev的引用，在列表中跳过它。因此，previous.next将 指向current.next，而current.next.prev将指向previous，如下图所示：