学习数据结构与算法之栈与队列

pingan8787 发布于2019-08-20 18:37 / 2906人阅读

摘要：于是翻出了机房里的这本学习数据结构与算法开始学习程序员的基础知识。这本书用了我最熟悉的来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。队列在头部删除元素，尾部添加元素。

本系列所有文章：
第一篇文章：学习数据结构与算法之栈与队列
第二篇文章：学习数据结构与算法之链表
第三篇文章：学习数据结构与算法之集合
第四篇文章：学习数据结构与算法之字典和散列表
第五篇文章：学习数据结构与算法之二叉搜索树

起因

最近要准备校招，打开某网站准备开始刷题，发现算法题根本无法动手，于是觉得这块需要恶补。(⊙v⊙)嗯，至少得先知道概念吧。于是翻出了机房里的这本《学习JavaScript数据结构与算法》开始学习程序员的基础知识。这本书用了我最熟悉的JS来实现各种数据结构和算法，而且书很薄，可以说是一本不错的入门教程。虽然我是个前端，但是计算机基础不能丢下。

栈

栈可以理解为一种特殊的数组。遵循后进先出(LIFO)的原则，元素在栈顶添加和删除。生活中常用来比作栈的例子主要是一叠盘子或一堆书，但是我觉得不够形象，因为盘子或书可以从中间被抽走。所以我一般把栈看成弹匣，想象一下子弹被一个个推进弹匣中，比如下图：

(图片来自谷歌搜索，侵删)

用JavaScript实现栈

声明一个构造函数：

function Stack () {
  // 使用数组来保存栈元素
  var items = []
}

为栈声明一些方法：

push(elements(s))：添加一个或多个元素到栈顶

pop()：删除位于栈顶的元素，并返回该元素

peek()：返回栈顶元素

isEmpty()：当前栈为空则返回true，否则为false

size()：返回栈的元素个数

clear()：清空栈

实现push

用数组的push方法向数组末尾添加新元素，实现元素入栈

// 栈顶添加
this.push = function (element) {
  items.push(element)
}

实现pop

用数组的pop方法在数组末尾删除一个元素，并返回删除元素，实现元素出栈

// 栈顶删除并返回删除元素
this.pop = function () {
  return items.pop()
}

实现peek

栈顶就是数组最后一个元素，使用Array[Array.length - 1]获得

// 返回栈顶元素
this.peek = function () {
  return items[items.length - 1]
}

实现其他方法

队列里面也用了这些方法，为避免重复，就先多带带拿出来了。

// 栈是否为空
this.isEmpty = function () {
  return items.length === 0
}

// 返回栈里的元素个数
this.size = function () {
  return items.length
}

// 清空栈
this.clear = function () {
  items = []
}

// 打印栈
this.print = function () {
  console.log(items.toString())
}

栈的应用

书上的例子有将十进制转二进制，这里我把后面那个十进制转任意进制的代码贴出来。

十进制转二进制原理很简单：把十进制数不断除以2直到为0，然后把每次的余数拼接到一起就是二进制数。

转其他进制也是类似的方法，只不过是把除以2换成其他数而已。代码如下：

// 把十进制转成任何进制
function BaseConverter (decNumber, base) {
  var remStack = new Stack(),
      rem,
      binaryString = "",
      digits = "0123456789ABCDEF"

  // 判断十进制数是否为0，把余数推入栈中
  while (decNumber > 0) {
    rem = Math.floor(decNumber % base)
    remStack.push(rem)
    decNumber = Math.floor(decNumber / base)
  }

  // 把栈中的元素拼接打印出来
  while (!remStack.isEmpty()) {
    binaryString += digits[remStack.pop()]
  }

  // 返回转换的二进制数
  return binaryString
}

这里的decNumber是要转换的十进制数，base是要转换的进制，remStack是上面Stack的实例，在remStack中操作栈的方法。这里的digits是对打印出来的数做一个处理，比如十六进制的数余数会大于9，那么就要用A、B、C、D、E、sF来表示10～15。

栈的学习暂时就这样了，这里贴上代码地址，有兴趣的可以看看：

栈的实现-源代码

队列

和栈很类似，只是原则不同，队列是先进先出（FIFO），又称先来先服务。队列在头部删除元素，尾部添加元素。生活中队列的例子就是排队了，这也很容易理解。

用JavaScript实现队列

同样声明构造函数：

function Queue () {
  var items = []
}

队列的方法：

enqueue(elements(s))：向队列尾部添加一个或多个元素

dequeue()：移除队列头部的元素并返回

front()：返回队列头部的元素

其他的和栈一样。

实现enqueue

用push方法推入元素

// 向队列尾部添加元素
this.enqueue = function (element) {
  items.push(element)
}

实现dequeue

用shift方法删除第一个数组元素，并返回删除的元素

// 删除队列头部的元素并返回删除元素
this.dequeue = function () {
  return items.shift()
}

实现front

直接返回第一个数组元素

// 返回队列头部的元素
this.front = function () {
  return items[0]
}

队列的应用

书上有讲优先队列和循环队列的应用，这里就简单讲一下优先队列的原理：

要实现优先队列有两种思路：一是将元素按正确的位置添加到队列中，然后元素正常在队列头部被删除；二是元素在队列尾部不按优先级正常入列，然后按优先级删除对应元素。

书上是按第一种思路实现的优先队列，这里限于篇幅就贴上代码地址：

队列的实现-源代码

接下来谈谈循环队列的应用——击鼓传花游戏

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 + "在击鼓传花游戏中被淘汰")
  }

  // 胜者出列并被返回
  return queue.dequeue()
}

其中nameList是参与游戏的名字列表，num是击鼓次数。

队列学习就暂时到这里，明天继续学习链表。

专线服务 idc机房托管算法与数据结构数据结构与算法数据结构与算法教程数据结构与算法答案

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/84767.html

Javascript数组系列一之栈与队列

摘要：所谓数组英语，是有序的元素序列。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。在栈中添加数据和删除数据也被称为推入和弹出，而且推入和弹出只会发生在栈的顶部。栈是一种数据结构，而队列则是一种的数据结构，即先进先出。所谓数组（英语：Array），是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称...

sunsmell 2019-08-23 11:49 评论0 收藏0
学习数据结构与算法之链表

摘要：本系列所有文章第一篇文章学习数据结构与算法之栈与队列第二篇文章学习数据结构与算法之链表第三篇文章学习数据结构与算法之集合第四篇文章学习数据结构与算法之字典和散列表第五篇文章学习数据结构与算法之二叉搜索树简单介绍链表链表一种常见的数据结构，可本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数...

jerryloveemily 2019-08-21 11:50 评论0 收藏0
学习数据结构与算法之集合

本系列所有文章：第一篇文章：学习数据结构与算法之栈与队列第二篇文章：学习数据结构与算法之链表第三篇文章：学习数据结构与算法之集合第四篇文章：学习数据结构与算法之字典和散列表第五篇文章：学习数据结构与算法之二叉搜索树集合简介记得高一数学第一节课学的就是集合，现在快大四了再看到它有种见了老朋友的感觉。哈哈，闲话不多扯，进入正题。集合是由一组无序且不重复的项组成的数据结构。这里集合的概念和高中数学...

fai1017 2019-08-21 11:51 评论0 收藏0
Javascript数组系列五之增删改和强大的 splice()

摘要：删除数组元素的开始索引需要删除元素的个数，插入数组的元素语法因为参数变化多样，我们主要从三个方面来展示的用法。今天是我们介绍数组系列文章的第五篇，也是我们数组系列的最后一篇文章，只是数据系列的结束，所以大家不用担心，我们会持续的更新干货文章。生命不息，更新不止！今天我们就不那么多废话了，直接干货开始。我们在《Javascript数组系列一之栈与队列》中描述我们是如何利用 pus...

chavesgu 2019-08-23 12:01 评论0 收藏0