JS栈与队列实现教程：原理、代码与十进制转二进制应用

学习背景与动机

学习起因

曾经在V2EX论坛看到一个帖子，楼主提到因为大学没有高数课程，工作后从事前端开发，深感数学基础薄弱，希望找回高中程度的数学知识。这与我情况相似，我的专业也不开设高数，同样从事前端工作，也感受到了数学知识匮乏带来的困扰。由于自认数学思维一般，我决定努力补习数学与计算机基础知识。虽然有人质疑“前端需要什么数据结构与算法”，但我认为前端开发者具备扎实的计算机基础对自身发展极为有利。我想成为一名真正的程序员，而非止步于初级前端或码农。这也是对我的勉励，毕竟基础决定上限，出于对计算机的浓厚兴趣，即使学习过程辛苦，也感到充实和幸福。为此，我购买了《学习JavaScript数据结构与算法》一书，并借阅《大话数据结构》，开始了初步学习。

JavaScipt之数组操作

栈（Stack）的实现与应用

接下来介绍数据结构的第一部分：栈。栈是一种遵循后进先出（LIFO, Last In First Out）原则的有序集合。栈顶始终指向最新的元素。例如，栈就像箱子里的一叠书，若要取出底部的书，必须先移开上面的书，不能直接抽取底层书籍。

JavaScipt中栈的实现


/**
 * 栈的构造函数
 */
function Stack() {

 // 用数组来模拟栈
 var item = [];
}

栈需要实现以下方法： - push(element(s))：向栈顶添加一个或多个元素。 - pop()：移除并返回栈顶元素。 - peek()：返回栈顶元素，但不移除。 - isAmpty：检查栈是否为空，若为空返回true。 - clear：移除栈中所有元素。 - size：返回栈中元素的个数。 - print：以字符串形式显示栈中所有内容。关于push方法的实现说明：需向栈中添加新元素，元素位于集合末尾。我们可以利用数组的push方法来模拟实现这一功能。

实现:


/**
 * 将元素送入栈，放置于数组的最后一位
 * @param {Any} element 接受的元素，不限制类型
 */
this.push = function(element) {
 items.push(element);
};

pop方法的实现

说明：需将栈顶元素弹出，同时返回被弹出的值。可以利用数组的pop方法来模拟实现。实现:


/**
 * 弹出栈顶元素
 * @return {Any} 返回被弹出的值
 */
this.pop = function() {
 return items.pop();
};

peek方法的实现


/**
 * 查看栈顶元素
 * @return {Any} 返回栈顶元素
 */
this.peek = function() {
 return items[items.length - 1];
}

其余方法的实现说明：前三个方法是栈的核心，其余方法在此一次性列出，因为下文介绍的队列将与这部分内容有大量重合。实现:


/**
 * 确定栈是否为空
 * @return {Boolean} 若栈为空则返回true,不为空则返回false
 */
this.isAmpty = function() {
 return items.length === 0
};

/**
 * 清空栈中所有内容
 */
this.clear = function() {
 items = [];
};

/**
 * 返回栈的长度
 * @return {Number} 栈的长度
 */
this.size = function() {
 return items.length;
};

/**
 * 以字符串显示栈中所有内容
 */
this.print = function() {
 console.log(items.toString());
};

实际应用

栈的实际应用场景较多，书中提供了一个将十进制转换为二进制的函数（若不了解二进制计算可参考相关资料）。以下是函数的源代码。其原理是：输入待转换的数字，不断除以2并取整。最后利用while循环，将栈中所有数字拼接成字符串输出。


/**
 * 将10进制数字转为2进制数字
 * @param {Number} decNumber 要转换的10进制数字
 * @return {Number}      转换后的2进制数字
 */
function divideBy2(decNumber) {

 var remStack = new Stack(),
  rem,
  binaryString = '';

 while (decNumber > 0) {
  rem = Math.floor(decNumber % 2);
  remStack.push(rem);
  decNumber = Math.floor(decNumber / 2);
 }

 while (!remStack.isAmpty()) {
  binaryString += remStack.pop().toString();
 }

 return binaryString;
};

至此，栈的学习告一段落。由于源代码中注释较多，此处不再贴出完整源码。

队列（Queue）的实现与应用

队列

队列与栈结构相似，主要区别在于队列遵循先进先出（FIFO, First In First Out）原则。举例来说，火车站排队买票，先到者先买（插队者除外），这样理解是否更直观？

JavaScipt中队列的实现

队列的实现方式与栈类似。首先定义构造函数：


/**
 * 队列构造函数
 */
function Queue() {
 var items = [];
}

队列需要实现以下方法： - enqueue(element(s))：向队列尾部添加一个或多个项。 - dequeue()：移除队列中的第一项（即排在最前面的项）。 - front()：返回队列的第一个元素，即最新添加的那个元素。 - 其余方法与栈相同。

enqueue方法的实现

说明：向队列尾部添加多个项。实现:


/**
 * 将元素推入队列尾部
 * @param {Any} ele 要推入队列的元素
 */
this.enqueue = function(ele) {
 items.push(ele);
};

dequeue方法的实现

说明：移除队列中的第一项。实现:


/**
 * 将队列中第一个元素弹出
 * @return {Any} 返回被弹出的元素
 */
this.dequeue = function() {
 return items.shift()
};

front方法的实现

说明：返回队列的第一个元素，即最新添加的那个元素。实现:


/**
 * 查看队列的第一个元素
 * @return {Any} 返回队列中第一个元素
 */
this.front = function() {
 return items[0];
};

以上三个方法是队列数据结构的核心方法，理解起来相对简单。

实际应用书中介绍了一个击鼓传花的小游戏。原理是在循环到指定位置时，从队列中弹出该元素，最后留下的即为赢家。源代码如下:


/**
 * 击鼓传花的小游戏
 * @param {Array} nameList 参与人员列表
 * @param {Number} num   在循环中要被弹出的位置
 * @return {String}     返回赢家(也就是最后活下来的那个)
 */
function hotPotato(nameList, num) {
 var queue = new Queue();

 for (var i = 0; i < nameList.length; i++) {
  queue.enqueue(nameList[i]);
 }

 var eliminated = '';

 while (queue.size() > 1) {
  for (var i = 0; i < num; i++) {
   queue.enqueue(queue.dequeue());
  }

  eliminated = queue.dequeue();
  console.log(eliminated + " Get out!")
 }

 return queue.dequeue()
}

队列的学习到此结束。下一期将介绍另一种数据结构：链表。

学习心得

感想

很多时候直接阅读《算法导论》或数据结构书籍会感到困惑。后来发现，从自己能看懂的内容入手，由浅入深才是适合自己的学习方式。

JavaScript数据结构与算法：栈与队列的实现及应用

学习背景与动机

栈（Stack）的实现与应用

队列（Queue）的实现与应用

学习心得

实用工具推荐