文档章节

<学习JavaScript数据结构与算法>读书笔记之用JS实现栈和队列

Anymore
 Anymore
发布于 2016/11/08 15:12
字数 1130
阅读 16
收藏 1

我的理解是,js 语言中其实没有栈和队列这一引用类型(有用数组的基础方法push()和pop()模拟栈,shift()和push()模拟队列,栈和队列更复杂的功能需要自己写),这些概念以及方法都是通过对数组中一些方法的组合和封装来达到的。 数组中一些常用的方法有:

  • every 对数组中的每一项运行给定函数,如果该函数对每一项都返回true,则返回true
  • filter 对数组中的每一项运行给定函数,返回该函数会返回true的项组成的数组
  • forEach 对数组中的每一项运行给定函数。这个方法没有返回值
  • join 将所有的数组元素连接成一个字符串
  • indexOf 返回第一个与给定参数相等的数组元素的索引,没有找到则返回-1
  • lastIndexOf 返回在数组中搜索到的与给定参数相等的元素的索引里最大的值
  • map 对数组中的每一项运行给定函数,返回每次函数调用的结果组成的数组
  • reverse 颠倒数组中元素的顺序,原先第一个元素现在变成最后一个,同样原先的最后一个元素变成了现在 的第一个
  • slice 传入索引值,将数组里对应索引范围内的元素作为新数组返回
  • some 对数组中的每一项运行给定函数,如果任一项返回true,则返回true
  • sort 按照字母顺序对数组排序,支持传入指定排序方法的函数作为参数
  • toString 将数组作为字符串返回
  • valueOf 和toString 类似,将数组作为字符串返回

栈: 栈中一些常用的方法有(可以自己再加方法):

  • push(element(s)) :添加一个(或几个)新元素到栈顶。
  • pop():移除栈顶的元素,同时返回被移除的元素。
  • peek() :返回栈顶的元素,不对栈做任何修改(这个方法不会移除栈顶的元素,仅仅返 回它)。
  • isEmpty():如果栈里没有任何元素就返回true,否则返回false。
  • clear():移除栈里的所有元素。
  • size() :返回栈里的元素个数。这个方法和数组的length属性很类似。
//栈
//首先通过创建一个类来表示栈
function Stack(){
    var items=[];
    this.push=function(elements){
        items.push(elements);
    };
    this.pop=function(){
        return items.pop();
    };
    this.peek=function(){
        return items[items.length-1];
    };
    this.isEmpty=function(){
        return items.length==0;
    };
    this.clear=function(){
        items=[];
    };
    this.size=function(){
        return items.length;
    };
    this.print=function(){
        return items.toString();
    }
}
//使用Stack类
var stack=new Stack();
console.log(stack.isEmpty());//true
stack.push(4);
stack.push(5);
console.log(stack.print());//4,5
console.log(stack.peek());//5

栈的实例:

//实例:利用栈将十进制转换为二进制
var decimalism=233;
var binary=new Stack();
var result='';
while(decimalism>0){
    binary.push(parseInt(decimalism%2));
    decimalism=parseInt(decimalism/2);
}
while(!binary.isEmpty()){
    result=result+binary.pop().toString();
}
console.log(result);//11101001

队列: 队列中一些常用的方法有(可以自己再加方法):

  • enqueue(element(s)):向队列尾部添加一个(或多个)新的项。
  • dequeue():移除队列的第一(即排在队列最前面的)项,并返回被移除的元素。
  • front():返回队列中第一个元素——最先被添加,也将是最先被移除的元素。队列不 做任何变动(不移除元素,只返回元素信息——与Stack 类的peek方法非常类似)。
  • isEmpty():如果队列中不包含任何元素,返回true,否则返回false 。
  • size() :返回队列包含的元素个数,与数组的length属性类似。
 //创建队列
 function Queue(){
     var items=[];
     this.enqueue=function(elements){
         items.push(elements);
     };
     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());
     };

 }

var queue=new Queue();
queue.enqueue("Anna");
queue.print();//Anna
//...

优先队列:

//优先队列
function PriorityQueue(){
    var items=[];
    function QueueElement(element,priority){
        this.elements=element;
        this.priority=priority;
    }
    this.isEmpty=function(){
         return items.length==0;
     };
    this.enqueue=function(element,priority){
        var queueElement=new QueueElement(element,priority);
        if(this.isEmpty()){
           items.push(queueElement);
        }else{
            var added=false;
            for(var 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(){
         console.log(items);
     };
    //其他方法与默认队列一致
}
//调用
var priorityQueue=new PriorityQueue();
priorityQueue.enqueue("Anna",3);
priorityQueue.enqueue("Bob",1);
priorityQueue.enqueue("Cindy",2);
priorityQueue.print();

循环队列(在队列的基础上进行特殊的调用)

//模拟击鼓传花
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();
}
var names=["John","Jack","Camila","Ingrid","Carl"];
var winner=hotPotato(names,4);
console.log("胜利者"+winner);

© 著作权归作者所有

Anymore
粉丝 5
博文 64
码字总数 29473
作品 0
塘沽
前端工程师
私信 提问
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
2018/05/10
0
0
【前端性能优化】高性能JavaScript读书笔记

序 曾经看过一篇文章,有一句话这样说: 只有在大学的图书馆里,你才能真正赚回你交的学费。 临近毕业,还想再去图书馆多转转。偶然在架子上发现了这本书,一看作者是写大名鼎鼎的红宝书的人...

番茄沙司
03/22
0
0
前端进阶(第一期)-调用堆栈笔记

1-1 理解 Javascript 执行上下文和执行栈 原文地址 知识点有: JavaScript程序的内部执行机制; 理解执行上下文和执行栈; 理解以上知识点有助于理解JavaScript的提升机制、作用域和闭包 执行...

xszi
2018/12/04
0
0
js的array实现栈数据结构

申明:本文是js系列笔记之一,有不正确的地方请尽管指出,大家相互学习,共同进步; 首先在阅读本文之前,默认你已经知道了javascript的数组类型,并且了解array的pop()和push方法;这里对这...

XBGG
2018/07/03
0
0
[翻译]理解异步JavaScript

写在文章前 这篇文章是翻译自Sukhjinder Arora的 Understanding Asynchronous JavaScript。这篇文章描述了异步和同步JavaScript是如何在运行环境中,使用调用栈,消息队列,作业队列,以及事...

YukiSong
2018/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Boot + Mybatis-Plus 集成与使用(二)

前言: 本章节介绍MyBatis-Puls的CRUD使用。在开始之前,先简单讲解下上章节关于Spring Boot是如何自动配置MyBatis-Plus。 一、自动配置 当Spring Boot应用从主方法main()启动后,首先加载S...

伴学编程
昨天
7
0
用最通俗的方法讲spring [一] ──── AOP

@[TOC](用最通俗的方法讲spring [一] ──── AOP) 写这个系列的目的(可以跳过不看) 自己写这个系列的目的,是因为自己是个比较笨的人,我曾一度怀疑自己的智商不适合干编程这个行业.因为在我...

小贼贼子
昨天
7
0
Flutter系列之在 macOS 上安装和配置 Flutter 开发环境

本文为Flutter开发环境在macOS下安装全过程: 一、系统配置要求 想要安装并运行 Flutter,你的开发环境需要最低满足以下要求: 操作系统:macOS(64位) 磁盘空间:700 MB(不包含 IDE 或其余...

過愙
昨天
6
0
OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
昨天
2.7K
16
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
昨天
42
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部