data-structure-1

https://github.com/EmilyYoung71415/StructuresandAlgorithms-Code

数组

数组是一种最简单和最广泛使用的数据结构，其它数据结构比如堆栈和队列都源自数组。

下图是一个大小为 4 的简单数组，包含几个元素（1,2,3 和 4）。

img

每个数据元素会被分配一个正的数值，叫作“索引”，它对应该元素在数组中的位置。大部分编程语言都将初始索引定义为 0.

种类

一维数组

二维数组

多维数组

基本操作

Insert——在给定索引位置插入一个元素

Get——返回给定索引位置的元素

Delete——删除给定索引位置的元素

Size——获取数组内所有元素的总数

常问的数组面试问题：

找到数组中第二小的元素

找到数组中第一个没有重复的整数

合并两个分类数组

重新排列数组中的正值和负值

队列

与栈类似，队列是另一种线性数据结构，以顺序方式存储元素。只允许在表的前端（front）进行删除操作，在表的后端（end）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队首。

堆栈和队列之间唯一的显着区别是，队列不是使用 LIFO 方法，而是应用 FIFO 方法，这是 First in First Out（先入先出）的缩写。

队列的完美现实例子：一列人在售票亭等候。如果有新人来，他们是从末尾加入队列，而不是在开头——站在前面的人将先买到票然后离开队列。

1553148348125

普通队列

从数据存储的角度看，实现队列有两种方式，一种是以数组做基础，一种是以链表做基础，数组是最简单的实现方式，本文以基础的数组来实现队列。

我们定义以下几个队列的方法：

然后我们利用 es6 的 class 的实现以上的方法

class Queue {
  constructor() {
    this.items = []; // 存储数据
  }
  enqueue(item) { // 向队尾添加一个元素
    this.items.push(item);
  }
  dequeue() { // 删除队首的一个元素
    return this.items.shift();
  }
  head() { // 返回队首的元素
    return this.items[0];
  }
  tail() { // 返回队尾的元素
    return this.items[this.items.length - 1];
  }
  size() { // 返回队列的元素
    return this.items.length;
  }
  isEmpty() { // 返回队列是否为空
    return this.items.length === 0;
  }
  clear() { // 清空队列
    this.items = [];
  }
}

优先队列

优先队列。元素的添加和移除是基于优先级的。

一个现实的例子就是机场登机的顺序。头等舱和商务舱乘客的优先级要高于经济舱乘客。在有些国家，老年人和孕妇（或带小孩的妇女）登机时也享有高于其他乘客的优先级。

实现一个优先队列，有两种选项：

我们在这里实现的优先队列称为最小优先队列，因为优先级的值较小的元素被放置在队列最前面（1 代表更高的优先级）。最大优先队列则与之相反，把优先级的值较大的元素放置在队列最前面。

想想生活中排队取号，，优先级 priority 数值越小，排在前面，优先级高。

function PriorityQueue() { 
  let items = []; 
  // 新建优先级对象的工厂函数
  function QueueElement (element, priority){ // {1} 
    this.element = element; 
    this.priority = priority; 
  } 
 
  this.enqueue = function(element, priority){ 
    let queueElement = new QueueElement(element, priority); 
 
    let added = false; 
    for (let i=0; i<items.length; i++){ 
      
      if (queueElement.priority < items[i].priority){ // {2} 
        // 找到一个优先级比要添加的元素小的，排在他的后面
        items.splice(i,0,queueElement); // {3} 
        added = true; 
        break; // {4} 
      } 
    } 
    if (!added){ 
      // 循环之后 added仍为 false ，说明优先级是最低的，排在队尾
      items.push(queueElement); //{5} 
    } 
  }; 
 
  this.print = function(){ 
    for (let i=0; i<items.length; i++){ 
      console.log(`${items[i].element} - ${items[i].priority}`); 
    } 
  }; 
  //其他方法和默认的Queue实现相同 
} 

let priorityQueue = new PriorityQueue(); 
priorityQueue.enqueue("John", 2); 
priorityQueue.enqueue("Jack", 1); 
priorityQueue.enqueue("Camila", 1); 
priorityQueue.print();

1554538303840

循环队列

循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。 你的实现应该支持如下操作：

isEmpty()

想要实现上面的功能，其实主要就是判断循环队列是否为空 isEmpty，是否已满 isFull，这里我们使用两个指针来表示队首（head）和队尾的指针（tail）。

front 指针始终指向队首的元素，并且始终初始化为 0，因为：

rear 指针有两种选择：

  1. rear 始终指向队尾的元素，这样 rear 应该初始化为 -1，需要考虑：
    1. enQueue 插入先设置 rear++，首次时插入到 0
    2. 如何判断为空？(rear + 1) % size === front 即为空
    3. 如何判断为满？(rear + 1) % size === front 即为满
    4. 空满的判断是一样的，不好处理
  2. rear 始终指向下一个插入元素的位置，这样 rear 应该初始化为 0，需要考虑
    1. enQueue 首次时插入到 0，插入后再设置 rear++
    2. 如何判断为空？rear === front 即为空，下一个插入的位置为队首的位置，说明是空的
    3. 如何判断为满？rear % k === front 即为满
    4. size 是 1 base 的，rear 是 0 base 的，但是因为 rear 始终指向下一个插入的位置，所以当队列为满时 rear === k
    5. rear + 1 是为了首次 enQueue 判断 0 % 任何数都为 0
    6. 所以 size 也要等于 k + 1
    7. 所以 (rear + 1) % (k + 1) === front 即为满
class circleQueue{
    constructor(k){
        this.size = k + 1
        this.front = 0
        this.rear = 0
        this.data = []
    }

    isEmpty(){
        return this.front === this.rear
    }
    isFull(){
        return (this.rear + 1 ) % this.size === this.front
    }
}

enQueue()

class MyCircularQueue {
    constructor(k){
        this.size = k + 1
        this.front = 0
        this.rear = 0
        this.data = new Array(k);
    }

    isEmpty(){
        return this.front === this.rear
    }
    isFull(){
        return (this.rear + 1 ) % this.size === this.front
    }

    enQueue(value) {
        if (this.isFull()) return false
        this.data[this.rear] = value
        this.rear = (this.rear + 1) % this.size
        return true
    }

    deQueue() {
        if (this.isEmpty()) return false;

        // 头指针往下移动一格就是删除了，不用真的 pop 元素
        this.front = (this.front + 1) % this.size
        return true
    }

    head(){
        return this.isEmpty() ? -1 : this.data[this.front]
    }

    tail(){
        return this.isEmpty() ? -1: this.data[(this.rear - 1 + this.size) % this.size]
    }
}

实例

循环队列的一个例子就是击鼓传花游戏（Hot Potato）。

在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

function hotPotato (nameList, num){ 
 
  let queue = new Queue(); // {1} 
 
  for (let i=0; i<nameList.length; i++){ 
    queue.enqueue(nameList[i]); // {2} 
  } 
 
  let eliminated = ''; 
  while (queue.size() > 1){ 
    for (let i=0; i<num; i++){ 
      // 将队首的放入队尾，执行num次
      queue.enqueue(queue.dequeue()); // {3} 
    } 
    // 一轮之后(num次),此时在队尾的人被淘汰
    eliminated = queue.dequeue();// {4} 
    console.log(eliminated + '在击鼓传花游戏中被淘汰。'); 
  } 
  // 队伍的长度等于1，游戏结束
  return queue.dequeue();// {5} 
} 
 
let names = ['Jack','John','Camila','Ingrid','Carl'];
let winner = hotPotato(names, 7);
console.log('The winner is: ' + winner);

面试题

设循环对列的容量为 50，从 0 到 49，经过入队和出队之后，有 front=11.rear=29

队列的应用

约瑟夫环问题

打印杨辉三角

常问的队列面试问题：

队列与栈

栈实现队列

思路分析

队列实现栈

思路分析

集合

概述

集合的实现

Set 类骨架

基本操作

has()

add()

remove() 和 clear()

size()

values()

集合操作

并集

交集

差集

子集

ES6——Set 类

模拟并集操作

模拟交集操作

模拟差集操作

字典

概述

字典的实现

Dictionary 类骨架

基本操作

Has 和 Set 方法

Delete 方法

Get 和 Values 方法

clear、size、keys 和 getItems 方法

ES6——Map 类

ES6——Weak Map 类和 WeakSet 类

除了 Set 和 Map 这两种新的数据结构，ES6 还增加了它们的弱化版本，WeakSet 和 WeakMap。

基本上，Map 和 Set 与其弱化版本之间仅有的区别是：

创建和使用这两个类主要是为了性能。WeakSet 和 WeakMap 是弱化的（用对象作为键），没有强引用的键。这使得 JavaScript 的垃圾回收器可以从中清除整个入口。

另一个优点是，必须用键才可以取出值。这些类没有 entries、keys 和 values 等迭代器方法，因此，除非你知道键，否则没有办法取出值。这印证了我们在第 3 章的做法，即使用 WeakMap 类封装 ES6 类的私有属性。