准备学习《学习JavaScript数据结构与算法》，自己也开始做一写笔记来记录总结，本文也是仅针对实现方面的总结。

如果出现错误，请在评论中指出，我也好自己纠正自己的错误

author： thomaszhou

栈的实现

栈，其实就是一个数组，但是这是个非常特殊的数组，因为栈有个特性：先进后出，什么意思呢？看着下面的图来讲解。

原谅我是个灵魂画手

• 栈只有一个开口，这个开口，是进口，也是出口

  • 我们从这个口添加数据，也从这个口取出数据

• 栈的原则：先进后出

  • 我们依次添加1，2，3进入栈中，那我们取出的第一个值是3，第二个取出的值是2，第三个是1。那如果在取出2的时候，又添加一个数呢？大家可以模拟一下

• 定义栈类和声明的方法

function Stack() {  //定义栈 的类      var items = [];            this.push = function(elem) {//添加元素        return items.push(elem);      };      this.pop = function() {//弹出元素        return items.pop();      };      this.print = function() { //输出        console.log(items.toString());      };            this.size = function() {//输出栈的长度        return items.length;      };            this.clear = function() {//将栈置为空        return items = [];      };            this.peek = function() {//显示顶层元素        return items[items.length-1]      };            this.isEmpty = function() { // 判断栈是否为空        return items.length === 0;      };}复制代码

栈的测试函数

(function demo1() {  let stack1 = new Stack();  //创建栈  stack1.push(1);  stack1.push(2);  stack1.push(3);  stack1.push(4);  stack1.print();  console.log(stack1.pop());//4  console.log(stack1.peek());// 3  console.log(stack1.isEmpty());// false  stack1.clear();  console.log(stack1.isEmpty());// true})();复制代码

• 栈的例子：十进制转换为任意进制

function divideBy2(elem, base) {      var str = '',          temp = 0,          arr = new Stack(),//创建栈          baseStr = '0123456789ABCDEF';      while (elem !== 0) {        arr.push(Math.floor(elem % base));//容易漏掉Math.floor()就会造成结果为undefine；        elem = Math.floor(elem / base);        //         //console.log(elem);  测试debug      }      while (!arr.isempty()) {        console.log(arr);        str += baseStr[arr.pop()]; // 字符串也是数组，所有要用baseStr[]。而不能用baseStr()      }      return str;    }        console.log(divideBy2(7, 2));复制代码

队列的实现

(1) 普通队列

• 队列和栈的不同就在于：
  • 1、栈是先进后出，那就是push和pop方法
  • 2、队列是先进先出，那就是push和shift方法
• 我们看啊，从右边进去，依次添加1，2，3，4，取出的第一个值是啥？是1，第二个，第三个第四个就是2，3，4.也就是说，我们添加一定是从右边进去，取出一定是从左边出去，也就是上面说的先进先出，先进去的，就先出来

function Queue() {	  let items = [];	  this.enqueue = function(ele) {	    items.push(ele);		};	  this.dequeue = function() {	    return items.shift();		};	  this.front = function() {	    return items[0];		};	  //	下面方法 同 栈	  this.isEmpty = function() {	    return items.length === 0;		};	  this.clear = function() {	    items = [];		};	  this.size = function() {	    return items.length;	  };          this.print = function() {            console.log(items.toString());          }	}复制代码

普通队列的测试函数：

(function queueDemo() {	  var queue = new Queue();	  queue.enqueue(1);	  queue.enqueue(2);	  queue.enqueue(3);	  queue.print();    //1,2,3	  console.log(queue.dequeue()); //1	  console.log(queue.isEmpty()); //false	  console.log(queue.size());    //2	  console.log(queue.front());   //2	  queue.clear();	  console.log(queue.size());  // 0	})();复制代码

(2) 优先队列

优先队列的核心在于设置优先级，队列的每个数据不是单一值，而是一个值和一个优先级id

• 1、 采用构造函数，构造一个含有element和priority的实例
• 2、 每次添加实例到队列中，按照优先级的先后插入到队列中（splice方法）

//	优先队列	function PriorityQueue() {	  let items = [];	  function QueueElement(element, priority) {	    this.element = element;	    this.priority = priority;		}	  this.enqueue = function(element, priority) {	    let ele = new QueueElement(element, priority);	    if (this.isEmpty() === true) { // 队列为空，直接push	      items.push(ele);	    }else {	      // 队列不为空，element的优先级priority小的在前面              for (let i = 0; i < items.length; i++) {                if (ele.priority < items[i].priority) {                  items.splice(i, 0, ele);		}else {		//  element的优先级最低的情况-直接push到最后                  items.push(ele);		}		break;              }	    }	  };      this.print = function() {        for (let i = 0; i < items.length; i++) {          console.log(`ele: ${items[i].element},prio: ${items[i].priority}`);        }      };//		其他的方法和普通队列相同      this.dequeue = function() {        return items.shift();      };      this.front = function() {        return items[0];      };           this.isEmpty = function() {        return items.length === 0;      };      this.clear = function() {        items = [];      };      this.size = function() {        return items.length;      };	}复制代码

优先队列测试函数:

(function priQueueDemo() {  var queue = new PriorityQueue();  queue.enqueue(1, 4);  queue.enqueue(2, 7);  queue.enqueue(3, 1);  queue.print();      //	ele: 3,prio: 1	//  ele: 1,prio: 4	//  ele: 2,prio: 7  console.log(queue.dequeue());//QueueElement {element: 3, priority: 1}  console.log(queue.isEmpty());//false  console.log(queue.size());//2  console.log(queue.front());//QueueElement {element: 1, priority: 4}  queue.clear();  console.log(queue.size());// 0})();复制代码

(3)循环队列

循环队列和普通队列的区别：普通队列和循环队列都是后面进一个，前面进一个.不同点就在于，循环队列是要将弹出的元素再返回到尾部再添加进去 核心代码就是queue.enqueue(queue.dequeue())

循环队列的应用-击鼓传花 击鼓传花的游戏都玩过，就是一堆人围一个圈，然后传递花，轮一圈，谁拿到花就淘汰谁（我们的例子是通过设置num来表示一轮传递几个人，算是一个规律性的击鼓传花，如果想实现真正的击鼓传花，那么就设置num为random，然后设置一个范围，就可以了,num = Math.floor(num * Math.random())）

• 所以也只是一个虚拟的游戏

function hotPotato (nameList, num) {  let queue = new Queue(),    len = nameList.length;  for (let i = 0; i < len; i++) {    queue.enqueue(nameList[i]);  }  while (queue.size() > 1) {// 队列最后剩下一个    for (let i = 0; i < num; i++) {      queue.enqueue(queue.dequeue());// 循环队列的核心    }    console.log(`${queue.dequeue()}被淘汰`);  }  console.log(`${queue.dequeue()}胜利`);//队列的最后一个值}let arr = ['thomas1', 'thomas2', 'thomas3', 'thomas4', 'thomas5'];hotPotato(arr, 2);//thomas3被淘汰//thomas1被淘汰//thomas5被淘汰//thomas2被淘汰//thomas4胜利复制代码