数据结构-栈和队列小结

看完《学习JavaScript数据结构和算法》（第2版）的第3、4章的内容，关是于栈和队列这2种数据结构的内容，以下是一些简单的笔记整理和摘录。

1、栈数据结构

1.1 栈的定义
栈是一种后进先出（LIFO，Last In First Out，后进先出）的有序集合。

1.2创建栈
用javascript的构造函数（类）可以创建表示栈，代码如下

//ES5语法
function Stack(){
  let items = [];
  // 向栈添加元素
  this.push = function(element){
    items.push(element);
  },
  //向栈移除元素
  this.pop = function(){
    return items.pop();
  },
  //查看栈顶元素
  this.peek = function(){
    return items[items.length-1];
  },
  //查看栈长度
  this.size = function (){
    return items.length;
  },
  //检查栈是否为空
  this.isEmpty = function(){
    return items.length == 0;
  },
  //清空栈元素
  this.clear = function(){
    items = [];
  },
  //打印栈元素
  this.print = function(){
    console.log(items.toString());
  }
}

1.3 使用栈
1.2节的构造函数完整创建了栈，接下来使用栈的方式

let stack = new Stack();
console.log(stack.isEmpty())  //true，此时`stack`没数据，结果为true
console.log(stack.push(5))
console.log(stack.print())  //5

2.队列数据结构

队列的创建跟栈是相似的，但原则不同。
2.1队列的定义
队列是遵循FIFO（First In First Out，先进先出）原则的一组有序的集合。
2.2创建队列
跟上面创建栈的方法类似，唯一的区别是dequeue方法和font方法由于队列原则不同所造成的。代码如下：

//ES5语法

function Queue() {
  //定义空数组，存储队列中的数据
  let items = [];
  //向队列添加元素
  this.enqueue = function(e){
    items.push(e)
  }
  //向队列移除元素
  this.dequeue = function(){
    return items.shift()
  },
  //查看队列头元素
  this.front = function(){
    return items[0]
  },
  //查看队列长度
  this.size = function (){
    return items.length;
  },
  //检查是否为空
  this.isEmpty = function(){
    return items.length == 0;
  },
  //打印队列元素
  this.print = function(){
    console.log(items.toString())
  }
}
let queue = new Queue();
console.log(queue.isEmpty())  //true

---分割线---

//ES6语法实现
let Queue2 = (function () {

  const items = new WeakMap();

  class Queue2 {
    constructor () {
      items.set(this, []);
    }
    enqueue(element) {
      let q = items.get(this);
      q.push(element);
    }
    dequeue() {
      let q = items.get(this);
      let r = q.shift();
      return r;
    }
    //其他方法
  }
  return Queue2;
})();

2.3使用队列

let queue = new Queue();
console.log(queue.isEmpty()); //输出true

用ES6语法创建的类Queue2也可以使用，输出的测试结果是一样的
2.4队列的应用
基于队列的应用是优先队列

function PriorityQueue() {
  let items = [];
  function QueueElement (element, priority){ 
    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){ 
        items.splice(i,0,queueElement); 
        added = true;
        break; 
      }
    }
    if (!added){
      items.push(queueElement); 
    }
  };

  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(); //  结果Jack1 , Camila 1, John 2