栈和队列数据结构

本内容整理自《学习JavaScript数据结构与算法》

一、栈：栈是一种遵从后进先出(LIFO)原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。

一个栈数据结构，需要有一些方法：
push(element(s)):添加一个(或几个)新元素到栈顶。
pop():移除栈顶的元素，同时返回被移除的元素。
peek():返回栈顶的元素，不对栈做任何修改(该方法不会移除栈顶的元素，仅仅返回它)。
isEmpty():如果栈里没有任何元素就返回 true，否则返回 false。
clear():移除栈里的所有元素。
size():返回栈里的元素个数。该方法和数组的 length 属性很类似。

创建一个 Stack 类最简单的方式是使用一个数组来存储其元素。在处理大量数据的时候(这在现实生活中的项目里很常见)，我们同样需要评估如何操作数据是最高效的。在使用数组时,大部分方法的时间复杂度是 O(n)。O(n)的意思是，我们需要迭代整个数组直到找到要找的那个元素，在最坏的情况下需要迭代数组的所有位置，其中的 n 代表数组的长度。如果数组有更多元素的话，所需的时间会更长。另外，数组是元素的一个有序集合，为了保证元素排列有序，它会占用更多的内存空间。
如果我们能直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排 列，那不是更好吗?对于使用 JavaScript 语言实现栈数据结构的场景，我们也可以使用一个 JavaScript 对象来存储所有的栈元素，保证它们的顺序并且遵循 LIFO 原则。

下面通过使用js数组和对象分别来实现一个栈。
1.运用js数组

class Stack {
    constructor() {
      this.items = []; 
    }
    push(element) {
      this.items.push(element)
    }
    pop() {
      return this.items.pop()
    }
    peek() {
      return this.items[this.items.length-1]
    }
    isEmpty() {
      return this.items.length === 0
    }
    clear() {
      this.items = []
    }
    //或
    clear() {
      while(!this.isEmpty()){
        this.pop()
      }
    }
    size() {
      return this.items.length
    }
  }

2.运用js对象

class Stack {
    constructor() {
      this.count = 0;
      this.items = {};
    }
    push(element) {
      this.items[this.count] = element;
      this.count++;
    }
    pop() {
      if (this.isEmpty()) {
        return undefined
      }
      let item = this.items[this.count-1];
      delete this.items[this.count-1];
      this.count--;
      return item
    }
    peek() {
      if (this.isEmpty()) {
        return undefined
      }
      return this.items[this.count-1]
    }
    isEmpty() {
      return this.count === 0
    }
    clear() {
      this.items = {};
      this.count = 0;
    }
    //或
    clear() {
      while(!this.isEmpty()){
        this.pop()
      }
    }
    size() {
      return this.count
    }
/*在数组版本中，我们不需要关心 toString 方法的实现，因为数据结构可以直接使用数组已 经提供的 
toString 方法。对于使用对象的版本，我们将创建一个 toString 方法来像数组一样打印出栈的内容。*/
    toString() {
      if (this.isEmpty()) {
        return ''
      }
      let val = this.items[0]
      for (var i=1; i<this.count; i++) {
        val += `,${this.items[i]}`
      }
      return val
    }
  }

栈的应用：十进制转换为其他进制

function baseConverter(decNumber, base) {
    //decNumber是需要转换的数，base是转换的进制
    const remStack = new Stack();
    const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'; // {6}
    let number = decNumber;
    let rem;
    let baseString = '';
    if (!(base >= 2 && base <= 36)) {
      return '';
    }
    while (number > 0) {
      rem = Math.floor(number % base);
      remStack.push(rem);
      number = Math.floor(number / base);
    }
    while (!remStack.isEmpty()) {
        baseString += digits[remStack.pop()]; // {7}
    }
    return baseString;
  }

二、队列：队列是遵循先进先出(FIFO，也称为先来先服务)原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。

队列需要的一些方法：
 enqueue(element(s)):向队列尾部添加一个(或多个)新的项。
 dequeue():移除队列的第一项(即排在队列最前面的项)并返回被移除的元素。
 peek():返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动(不移除元素，只返回元素信息——与 Stack 类的 peek 方法非常类似)。该方法在其他语言中也可以叫作 front 方法。
isEmpty():如果队列中不包含任何元素，返回 true，否则返回 false。
size():返回队列包含的元素个数，与数组的 length 属性类似。
clear():移除队列里的所有元素。

下面通过使用js数组和对象分别来实现一个队列。

1.js数组方法与前面实现Stack类基本一样，在此略。

2.js对象方法

class Queue {
    constructor() {
      this.count = 0; 
      //由于我们将要从队 列前端移除元素，同样需要一个变量来帮助我们追踪第一个元素。因此，声明一个 lowestCount 变量
      this.lowestCount = 0; 
      this.items = {}; 
    }
    enqueue(element) {
      this.items[this.count] = element
      this.count++ 
    }
    dequeue() {
      if (this.isEmpty()) {
        return undefined
      }
      let item = this.items[this.lowestCount];
      delete this.items[this.lowestCount]
      if (this.count > 1) {
        this.lowestCount++ 
      }
      this.count--
      return item
    }
    peek() {
      if (this.isEmpty()) {
        return undefined
      }
      return this.items[this.lowestCount]
    }
    isEmpty() {
      return this.count === 0
    }
    size() {
      return this.count
    }
    toString() {
      if (this.isEmpty()) {
        return ''
      }
      let val = this.items[this.lowestCount]
      for (var i=this.lowestCount + 1; i<this.count; i++) {
        val += `,${this.items[i]}`
      }
      return val
    }
  }

队列的应用：击鼓传花游戏(hot potato)。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止， 这个时候花在谁手里，谁就退出圆圈、结束游戏。重复这个过程，直到只剩一个孩子(胜者)。

function hotPotato(elementsList, num) {
    const queue = new Queue(); // {1}
    const elimitatedList = [];
    for (let i = 0; i < elementsList.length; i++) {
      queue.enqueue(elementsList[i]); // {2}
    }
    while (queue.size() > 1) {
      for (let i = 0; i < num; i++) {
        queue.enqueue(queue.dequeue()); // {3}
      }
      elimitatedList.push(queue.dequeue()); // {4}
    }
    return {
      eliminated: elimitatedList,
      winner: queue.dequeue() // {5}
    }
  }
  /*我们会得到一 份名单，把里面的名字全都加入队列。
  *给定一个数字，然后迭代队列。从队列开头移 除一项，再将其添加到队列末尾，
  *模拟击鼓传花(如果你把花传给了旁边的人，你被 淘汰的威胁就立刻解除了。
  *一旦达到给定的传递次数，拿着花的那个人就被淘汰了(从队列中 移除。
  *最后只剩下一个人的时候，这个人就是胜者。
我们可以使用下面的代码来尝试 hotPotato 算法。*/
    const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
    const result = hotPotato(names, 7);
    result.eliminated.forEach(name => {
      console.log(`${name}在击鼓传花游戏中被淘汰`)
    });
    console.log(`胜利者: ${result.winner}`);
    /*以上算法的输出如下。
    Camila 在击鼓传花游戏中被淘汰
    Jack 在击鼓传花游戏中被淘汰
    Carl 在击鼓传花游戏中被淘汰
    Ingrid 在击鼓传花游戏中被淘汰。
    胜利者:John*/

 

三、双端队列(deque，或称 double-ended queue)是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

双端队列的一些方法：
addFront(element):该方法在双端队列前端添加新的元素。
addBack(element):该方法在双端队列后端添加新的元素(实现方法和 Queue 类中的 enqueue 方法相同)。
removeFront():该方法会从双端队列前端移除第一个元素(实现方法和 Queue 类中的 dequeue 方法相同)。
removeBack():该方法会从双端队列后端移除第一个元素(实现方法和 Stack 类中的 pop 方法一样)。
peekFront():该方法返回双端队列前端的第一个元素(实现方法和 Queue 类中的 peek 方法一样)。
peekBack():该方法返回双端队列后端的第一个元素(实现方法和 Stack 类中的 peek 方法一样)。

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {}; 
  }
  addFront(element) {
    if (this.isEmpty()) { 
      //队列为空的时候
      this.addBack(element);
    } else if (this.lowestCount > 0) { 
      //已经从队列的前端删除过元素了
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      //没有从队列删除过元素 所有元素往后移一位 空出第一个位置用来插入新元素
      for (let i = this.count; i > 0; i--) { 
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = element; 
    } 
  }
}

双端队列的应用：回文检测

    function palindromeChecker(aString) {
      if (aString === undefined || aString === null ||
        (aString !== null && aString.length === 0)) { 
        return false;
      }
      const deque = new Deque(); 
      const lowerString = aString.toLocaleLowerCase().split(' ').join(''); 
      let isEqual = true, firstChar, lastChar;
      for (let i = 0; i < lowerString.length; i++) { 
        deque.addBack(lowerString.charAt(i));
      }
      while (deque.size() > 1 && isEqual) { 
        firstChar = deque.removeFront();
        lastChar = deque.removeBack(); 
        if (firstChar !== lastChar) {
          isEqual = false; 
        }
      }
      return isEqual;
    }