Javascript技术栈中的四种依赖注入详解

作为面向对象编程中实现控制反转(Inversion of Control,下文称IoC)最常见的技术手段之一,依赖注入(Dependency Injection,下文称DI)可谓在OOP编程中大行其道经久不衰。比如在J2EE中,就有大名鼎鼎的执牛耳者Spring。Javascript社区中自然也不乏一些积极的尝试,广为人知的AngularJS很大程度上就是基于DI实现的。遗憾的是,作为一款缺少反射机制、不支持Annotation语法的动态语言,Javascript长期以来都没有属于自己的Spring框架。当然,伴随着ECMAScript草案进入快速迭代期的春风,Javascript社区中的各种方言、框架可谓群雄并起,方兴未艾。可以预见到,优秀的JavascriptDI框架的出现只是早晚的事。

本文总结了Javascript中常见的依赖注入方式,并以inversify.js为例,文章分为四节:

一. 基于Injector、Cache和函数参数名的依赖注入
二. AngularJS中基于双Injector的依赖注入
三. TypeScript中基于装饰器和反射的依赖注入
四. inversify.js——Javascript技术栈中的IoC容器

一. 基于Injector、Cache和函数参数名的依赖注入

尽管Javascript中不原生支持反射(Reflection)语法,但是Function.prototype上的toString方法却为我们另辟蹊径,使得在运行时窥探某个函数的内部构造成为可能:toString方法会以字符串的形式返回包含function关键字在内的整个函数定义。从这个完整的函数定义出发,我们可以利用正则表达式提取出该函数所需要的参数,从而在某种程度上得知该函数的运行依赖。
比如Student类上write方法的函数签名write(notebook, pencil)就说明它的执行依赖于notebook和pencil对象。因此,我们可以首先把notebook和pencil对象存放到某个cache中,再通过injector(注入器、注射器)向write方法提供它所需要的依赖:

var cache = {};
// 通过解析Function.prototype.toString()取得参数名
function getParamNames(func) {
 var paramNames = func.toString().match(/^function\s*[^\(]*\(\s*([^\)]*)\)/m)[1];
 paramNames = paramNames.replace(/ /g, '');
 paramNames = paramNames.split(',');
 return paramNames;
}
var injector = {
 // 将func作用域中的this关键字绑定到bind对象上,bind对象可以为空
 resolve: function (func, bind) {
  // 取得参数名
  var paramNames = getParamNames(func);
  var params = [];
  for (var i = 0; i < paramNames.length; i++) {
   // 通过参数名在cache中取出相应的依赖
   params.push(cache[paramNames[i]]);
  }
  // 注入依赖并执行函数
  func.apply(bind, params);
 }
};

function Notebook() {}
Notebook.prototype.printName = function () {
 console.log('this is a notebook');
};

function Pencil() {}
Pencil.prototype.printName = function () {
 console.log('this is a pencil');
};

function Student() {}
Student.prototype.write = function (notebook, pencil) {
 if (!notebook || !pencil) {
  throw new Error('Dependencies not provided!');
 }
 console.log('writing...');
};
// 提供notebook依赖
cache['notebook'] = new Notebook();
// 提供pencil依赖
cache['pencil'] = new Pencil();
var student = new Student();
injector.resolve(student.write, student); // writing...

有时候为了保证良好的封装性,也不一定要把cache对象暴露给外界作用域,更多的时候是以闭包变量或者私有属性的形式存在的:

function Injector() {
 this._cache = {};
}

Injector.prototype.put = function (name, obj) {
 this._cache[name] = obj;
};

Injector.prototype.getParamNames = function (func) {
 var paramNames = func.toString().match(/^function\s*[^\(]*\(\s*([^\)]*)\)/m)[1];
 paramNames = paramNames.replace(/ /g, '');
 paramNames = paramNames.split(',');
 return paramNames;
};

Injector.prototype.resolve = function (func, bind) {
 var self = this;
 var paramNames = self.getParamNames(func);
 var params = paramNames.map(function (name) {
  return self._cache[name];
 });
 func.apply(bind, params);
};

var injector = new Injector();

var student = new Student();
injector.put('notebook', new Notebook());
injector.put('pencil', new Pencil())
injector.resolve(student.write, student); // writing...
比如现在要执行Student类上的另一个方法function draw(notebook, pencil, eraser),因为injector的cache中已经有了notebook和pencil对象,我们只需要将额外的eraser也存放到cache中:
function Eraser() {}
Eraser.prototype.printName = function () {
 console.log('this is an eraser');
};

// 为Student增加draw方法
Student.prototype.draw = function (notebook, pencil, eraser) {
 if (!notebook || !pencil || !eraser) {
  throw new Error('Dependencies not provided!');
 }
 console.log('drawing...');
};

injector.put('eraser', new Eraser());
injector.resolve(student.draw, student);

通过依赖注入,函数的执行和其所依赖对象的创建逻辑就被解耦开来了。
当然,随着grunt/gulp/fis等前端工程化工具的普及,越来越多的项目在上线之前都经过了代码混淆(uglify),因而通过参数名去判断依赖并不总是可靠,有时候也会通过为function添加额外属性的方式来明确地说明其依赖:

Student.prototype.write.depends = ['notebook', 'pencil'];
Student.prototype.draw.depends = ['notebook', 'pencil', 'eraser'];
Injector.prototype.resolve = function (func, bind) {
 var self = this;
 // 首先检查func上是否有depends属性,如果没有,再用正则表达式解析
 func.depends = func.depends || self.getParamNames(func);
 var params = func.depends.map(function (name) {
  return self._cache[name];
 });
 func.apply(bind, params);
};
var student = new Student();
injector.resolve(student.write, student); // writing...
injector.resolve(student.draw, student); // draw...

二. AngularJS中基于双Injector的依赖注入

熟悉AngularJS的同学很快就能联想到,在injector注入之前,我们在定义module时还可以调用config方法来配置随后会被注入的对象。典型的例子就是在使用路由时对$routeProvider的配置。也就是说,不同于上一小节中直接将现成对象(比如new Notebook())存入cache的做法,AngularJS中的依赖注入应该还有一个"实例化"或者"调用工厂方法"的过程。
这就是providerInjector、instanceInjector以及他们各自所拥有的providerCache和instanceCache的由来。
在AngularJS中,我们能够通过依赖注入获取到的injector通常是instanceInjector,而providerInjector则是以闭包中变量的形式存在的。每当我们需要AngularJS提供依赖注入服务时,比如想要获取notebook,instanceInjector会首先查询instanceCache上是存在notebook属性,如果存在,则直接注入;如果不存在,则将这个任务转交给providerInjector;providerInjector会将"Provider"字符串拼接到"notebook"字符串的后面,组成一个新的键名"notebookProvider",再到providerCache中查询是否有notebookProvider这个属性,如有没有,则抛出异常Unknown Provider异常:

如果有,则将这个provider返回给instanceInjector;instanceInjector拿到notebookProvider后,会调用notebookProvider上的工厂方法$get,获取返回值notebook对象,将该对象放到instanceCache中以备将来使用,同时也注入到一开始声明这个依赖的函数中。过程描述起来比较复杂,可以通过下面的图示来说明:

需要注意的是,AngularJS中的依赖注入方式也是有缺陷的:利用一个instanceInjector单例服务全局的副作用就是无法单独跟踪和控制某一条依赖链条,即使在没有交叉依赖的情况下,不同module中的同名provider也会产生覆盖,这里就不详细展开了。

另外,对于习惯于Java和C#等语言中高级IoC容器的同学来说,看到这里可能觉得有些别扭,毕竟在OOP中,我们通常不会将依赖以参数的形式传递给方法,而是作为属性通过constructor或者setters传递给实例,以实现封装。的确如此,一、二节中的依赖注入方式没有体现出足够的面向对象特性,毕竟这种方式在Javascript已经存在多年了,甚至都不需要ES5的语法支持。希望了解Javascript社区中最近一两年关于依赖注入的研究和成果的同学,可以继续往下阅读。

三. TypeScript中基于装饰器和反射的依赖注入

笔者本身对于Javascript的各种方言的学习并不是特别热情,尤其是现在EMCAScript提案、草案更新很快,很多时候借助于polyfill和babel的各种preset就能满足需求了。但是TypeScript是一个例外(当然现在Decorator也已经是提案了,虽然阶段还比较早,但是确实已经有polyfill可以使用)。上文提到,Javascript社区中迟迟没有出现一款优秀的IoC容器和自身的语言特性有关,那就依赖注入这个话题而言,TypeScript给我们带来了什么不同呢?至少有下面这几点:
* TypeScript增加了编译时类型检查,使Javascript具备了一定的静态语言特性
* TypeScript支持装饰器(Decorator)语法,和传统的注解(Annotation)颇为相似
* TypeScript支持元信息(Metadata)反射,不再需要调用Function.prototype.toString方法
下面我们就尝试利用TypeScript带来的新语法来规范和简化依赖注入。这次我们不再向函数或方法中注入依赖了,而是向类的构造函数中注入。
TypeScript支持对类、方法、属性和函数参数进行装饰,这里需要用到的是对类的装饰。继续上面小节中用到的例子,利用TypeScript对代码进行一些重构:

class Pencil {
 public printName() {
  console.log('this is a pencil');
 }
}

class Eraser {
 public printName() {
  console.log('this is an eraser');
 }
}

class Notebook {
 public printName() {
  console.log('this is a notebook');
 }
}

class Student {
 pencil: Pencil;
 eraser: Eraser;
 notebook: Notebook;
 public constructor(notebook: Notebook, pencil: Pencil, eraser: Eraser) {
  this.notebook = notebook;
  this.pencil = pencil;
  this.eraser = eraser;
 }
 public write() {
  if (!this.notebook || !this.pencil) {
   throw new Error('Dependencies not provided!');
  }
  console.log('writing...');
 }
 public draw() {
  if (!this.notebook || !this.pencil || !this.eraser) {
   throw new Error('Dependencies not provided!');
  }
  console.log('drawing...');
 }
}

下面是injector和装饰器Inject的实现。injector的resolve方法在接收到传入的构造函数时,会通过name属性取出该构造函数的名字,比如class Student,它的name属性就是字符串"Student"。再将Student作为key,到dependenciesMap中去取出Student的依赖,至于dependenciesMap中是何时存入的依赖关系,这是装饰器Inject的逻辑,后面会谈到。Student的依赖取出后,由于这些依赖已经是构造函数的引用而非简单的字符串了(比如Notebook、Pencil的构造函数),因此直接使用new语句即可获取这些对象。获取到Student类所依赖的对象之后,如何把这些依赖作为构造函数的参数传入到Student中呢?最简单的莫过于ES6的spread操作符。在不能使用ES6的环境下,我们也可以通过伪造一个构造函数来完成上述逻辑。注意为了使instanceof操作符不失效,这个伪造的构造函数的prototype属性应该指向原构造函数的prototype属性。

var dependenciesMap = {};
var injector = {
 resolve: function (constructor) {
  var dependencies = dependenciesMap[constructor.name];
  dependencies = dependencies.map(function (dependency) {
   return new dependency();
  });
  // 如果可以使用ES6的语法,下面的代码可以合并为一行:
  // return new constructor(...dependencies);
  var mockConstructor: any = function () {
   constructor.apply(this, dependencies);
  };
  mockConstructor.prototype = constructor.prototype;
  return new mockConstructor();
 }
};
function Inject(...dependencies) {
 return function (constructor) {
  dependenciesMap[constructor.name] = dependencies;
  return constructor;
 };
}

injector和装饰器Inject的逻辑完成后,就可以用来装饰class Student并享受依赖注入带来的乐趣了:

// 装饰器的使用非常简单,只需要在类定义的上方添加一行代码
// Inject是装饰器的名字,后面是function Inject的参数
@Inject(Notebook, Pencil, Eraser)
class Student {
 pencil: Pencil;
 eraser: Eraser;
 notebook: Notebook;
 public constructor(notebook: Notebook, pencil: Pencil, eraser: Eraser) {
  this.notebook = notebook;
  this.pencil = pencil;
  this.eraser = eraser;
 }
 public write() {
  if (!this.notebook || !this.pencil) {
   throw new Error('Dependencies not provided!');
  }
  console.log('writing...');
 }
 public draw() {
  if (!this.notebook || !this.pencil || !this.eraser) {
   throw new Error('Dependencies not provided!');
  }
  console.log('drawing...');
 }
}
var student = injector.resolve(Student);
console.log(student instanceof Student); // true
student.notebook.printName(); // this is a notebook
student.pencil.printName(); // this is a pencil
student.eraser.printName(); // this is an eraser
student.draw(); // drawing
student.write(); // writing

利用装饰器,我们还可以实现一种比较激进的依赖注入,下文称之为RadicalInject。RadicalInject对原代码的侵入性比较强,不一定适合具体的业务,这里也一并介绍一下。要理解RadicalInject,需要对TypeScript装饰器的原理和Array.prototype上的reduce方法理解比较到位。

function RadicalInject(...dependencies){
 var wrappedFunc:any = function (target: any) {
  dependencies = dependencies.map(function (dependency) {
   return new dependency();
  });
  // 使用mockConstructor的原因和上例相同
  function mockConstructor() {
   target.apply(this, dependencies);
  }
  mockConstructor.prototype = target.prototype;

  // 为什么需要使用reservedConstructor呢?因为使用RadicalInject对Student方法装饰之后,
  // Student指向的构造函数已经不是一开始我们声明的class Student了,而是这里的返回值,
  // 即reservedConstructor。Student的指向变了并不是一件不能接受的事,但是如果要
  // 保证student instanceof Student如我们所期望的那样工作,这里就应该将
  // reservedConstructor的prototype属性指向原Student的prototype
  function reservedConstructor() {
   return new mockConstructor();
  }
  reservedConstructor.prototype = target.prototype;
  return reservedConstructor;
 }
 return wrappedFunc;
}

使用RadicalInject,原构造函数实质上已经被一个新的函数代理了,使用上也更为简单,甚至都不需要再有injector的实现:

@RadicalInject(Notebook, Pencil, Eraser)
class Student {
 pencil: Pencil;
 eraser: Eraser;
 notebook: Notebook;
 public constructor() {}
 public constructor(notebook: Notebook, pencil: Pencil, eraser: Eraser) {
  this.notebook = notebook;
  this.pencil = pencil;
  this.eraser = eraser;
 }
 public write() {
  if (!this.notebook || !this.pencil) {
   throw new Error('Dependencies not provided!');
  }
  console.log('writing...');
 }
 public draw() {
  if (!this.notebook || !this.pencil || !this.eraser) {
   throw new Error('Dependencies not provided!');
  }
  console.log('drawing...');
 }
}
// 不再出现injector,直接调用构造函数
var student = new Student();
console.log(student instanceof Student); // true
student.notebook.printName(); // this is a notebook
student.pencil.printName(); // this is a pencil
student.eraser.printName(); // this is an eraser
student.draw(); // drawing
student.write(); // writing

由于class Student的constructor方法需要接收三个参数,直接无参调用new Student()会造成TypeScript编译器报错。当然这里只是分享一种思路,大家可以暂时忽略这个错误。有兴趣的同学也可以使用类似的思路尝试代理一个工厂方法,而非直接代理构造函数,以避免这类错误,这里不再展开。

AngularJS2团队为了获得更好的装饰器和反射语法的支持,一度准备另起炉灶,基于AtScript(AtScript中的"A"指的就是Annotation)来进行新框架的开发。但最终却选择拥抱TypeScript,于是便有了微软和谷歌的奇妙组合。

当然,需要说明的是,在缺少相关标准和浏览器厂商支持的情况下,TypeScript在运行时只是纯粹的Javascript,下节中出现的例子会印证这一点。

四. inversify.js——Javascript技术栈中的IoC容器

其实从Javascript出现各种支持高级语言特性的方言就可以预见到,IoC容器的出现只是早晚的事情。比如博主今天要介绍的基于TypeScript的inversify.js,就是其中的先行者之一。
inversity.js比上节中博主实现的例子还要进步很多,它最初设计的目的就是为了前端工程师同学们能在Javascript中写出符合SOLID原则的代码,立意可谓非常之高。表现在代码中,就是处处有接口,将"Depend upon Abstractions. Do not depend upon concretions."(依赖于抽象,而非依赖于具体)表现地淋漓尽致。继续使用上面的例子,但是由于inversity.js是面向接口的,上面的代码需要进一步重构:

interface NotebookInterface {
 printName(): void;
}
interface PencilInterface {
 printName(): void;
}
interface EraserInterface {
 printName(): void;
}
interface StudentInterface {
 notebook: NotebookInterface;
 pencil: PencilInterface;
 eraser: EraserInterface;
 write(): void;
 draw(): void;
}
class Notebook implements NotebookInterface {
 public printName() {
  console.log('this is a notebook');
 }
}
class Pencil implements PencilInterface {
 public printName() {
  console.log('this is a pencil');
 }
}
class Eraser implements EraserInterface {
 public printName() {
  console.log('this is an eraser');
 }
}

class Student implements StudentInterface {
 notebook: NotebookInterface;
 pencil: PencilInterface;
 eraser: EraserInterface;
 constructor(notebook: NotebookInterface, pencil: PencilInterface, eraser: EraserInterface) {
  this.notebook = notebook;
  this.pencil = pencil;
  this.eraser = eraser;
 }
 write() {
  console.log('writing...');
 }
 draw() {
  console.log('drawing...');
 }
}

由于使用了inversity框架,这次我们就不用自己实现injector和Inject装饰器啦,只需要从inversify模块中引用相关对象:

import { Inject } from "inversify";

@Inject("NotebookInterface", "PencilInterface", "EraserInterface")
class Student implements StudentInterface {
 notebook: NotebookInterface;
 pencil: PencilInterface;
 eraser: EraserInterface;
 constructor(notebook: NotebookInterface, pencil: PencilInterface, eraser: EraserInterface) {
  this.notebook = notebook;
  this.pencil = pencil;
  this.eraser = eraser;
 }
 write() {
  console.log('writing...');
 }
 draw() {
  console.log('drawing...');
 }
}

这样就行了吗?还记得上节中提到TypeScript中各种概念只是语法糖吗?不同于上一节中直接将constructor引用传递给Inject的例子,由于inversify.js是面向接口的,而诸如NotebookInterface、PencilInterface之类的接口只是由TypeScript提供的语法糖,在运行时并不存在,因此我们在装饰器中声明依赖时只能使用字符串形式而非引用形式。不过不用担心,inversify.js为我们提供了bind机制,在接口的字符串形式和具体的构造函数之间搭建了桥梁:

import { TypeBinding, Kernel } from "inversify";

var kernel = new Kernel();
kernel.bind(new TypeBinding<NotebookInterface>("NotebookInterface", Notebook));
kernel.bind(new TypeBinding<PencilInterface>("PencilInterface", Pencil));
kernel.bind(new TypeBinding<EraserInterface>("EraserInterface", Eraser));
kernel.bind(new TypeBinding<StudentInterface>("StudentInterface", Student));

注意这步需要从inversify模块中引入TypeBinding和Kernel,并且为了保证返回值类型以及整个编译时静态类型检查能够顺利通过,泛型语法也被使用了起来。
说到这里,要理解new TypeBinding<NotebookInterface>("NotebookInterface", Notebook)也就很自然了:为依赖于"NotebookInterface"字符串的类提供Notebook类的实例,返回值向上溯型到NotebookInterface。
完成了这些步骤,使用起来也还算顺手:

var student: StudentInterface = kernel.resolve<StudentInterface>("StudentInterface");
console.log(student instanceof Student); // true
student.notebook.printName(); // this is a notebook
student.pencil.printName(); // this is a pencil
student.eraser.printName(); // this is an eraser
student.draw(); // drawing
student.write(); // writing

以上就是关于Javascript技术栈中的四种依赖注入的全部内容,希望对大家的学习有所帮助。

(0)

相关推荐

  • JS实现线性表的链式表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的链式表示方法.分享给大家供大家参考,具体如下: 从上一节可以,顺序存储结构的弱点就是在插入或删除操作时,需要移动大量元素.所以这里需要介绍一下链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构的弱点,但是也没有顺序表可随机存取的优点. 下面介绍一下什么是链表. 线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素.所以,每一个数据元素除了存储自身的信息之外,还需要存储一个指向其后继的存储位置的信息.这两部分信息组成了元素的存

  • JS实现线性表的顺序表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的顺序表示方法.分享给大家供大家参考,具体如下: 线性表的顺序表示指的是用一组地址连接的存储单元依次存储线性表的数据元素.通常称这种存储结构的线性表为顺序表. 顺序表的特点是以元素在计算机内物理位置相邻来表示数据元素之间的逻辑关系.每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数.也就是说只要确定了存储线性表的起始位置,线性表中的任一元素都可以随机存储,所以说,顺序表是一种随机存取的存储结构. 高级语言中的数组与其相似,所以我

  • JavaScript调用堆栈及setTimeout使用方法深入剖析

    Javascript中会经常用到setTimeout来推迟一个函数的执行,如: 复制代码 代码如下: setTimeout(function(){alert("Hello World");},1000); 会在执行到这句话后延迟1秒钟来弹出alert窗口.那么再看这一段: 复制代码 代码如下: function a(){ setTimeout(function() {alert(1)}, 0); alert(2); } a(); 注意这段代码中的setTimeout延迟设为了0,就是延

  • JavaScript把数组作为堆栈使用的方法

    本文实例讲述了JavaScript把数组作为堆栈使用的方法.分享给大家供大家参考.具体如下: JavaScript把数组作为堆栈使用的代码范例,支持堆栈常用的push和pop方法 <script type="text/javascript"> var numbers = ["one", "two", "three", "four"]; numbers.push("five")

  • JavaScript数组实现数据结构中的队列与堆栈

    一.队列和堆栈的简单介绍 1.1.队列的基本概念 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 如下图所示: 1.2.堆栈的基本概念 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 如下图所示: 二. 在JavaScript中实现队列和堆栈 在JavaScript中实现队列和数组主要是通过数组,js数组中提供了以下几个方法可以让我们很方便实现队列和堆栈: •shift:从数组中把第一个元素删除,并返回这个元素的值. •unshift: 在数组

  • js使用栈来实现10进制转8进制与取除数及余数

    复制代码 代码如下: function ten2eight(x){ var s=[]; var r=''; while(x>0){ s.push(x%8); x=parseInt(x/8); } while(s.length>0){ r=r+s.pop(); } return r; } N=(N div 8)*8+(N mod 8) (div 是整除操作,mod 是求余) 对于输入的一个非负十进制整数转换成八进制,计算过程是从低位到高位顺序产生八进制的各个数位,而输出时,一般来说应从高位到低位

  • JavaScript数据结构与算法之栈与队列

    学习起因 曾经有一次在逛V2EX时,碰到这么一个帖子. 数学完全还给老师了,想学回一些基础数学,大概是高中程度的,有什么书籍推荐? 发帖的楼主大学没有高数课程,出去工作时一直在从事前端的工作.感觉到数学知识的匮乏,所以想补一补数学. 看了看帖子,感觉和我很像,因为我的专业是不开高数的,我学的也是前端.也同样感觉到了数学知识匮乏所带来的困顿.同时因为自己的数学思维实在是不怎么好,所以决定努力补习数学与计算机基础知识. 当时也有人说:"前端需要什么数据结构与算法",但是对于这个事情我有自己

  • JavaScript数组的栈方法与队列方法详解

    数组(Array)和对象(Object)应该是JavaScript中使用最多也是最频繁的两种类型了,Array提供了很多常用的方法:栈方法.队列方法.重排序方法.操作方法.位置方法.迭代方法等等. 1.Array的栈方法 栈是一种LIFO(Last-In-First-Out,后进先出)的数据结构,也就是最新添加的项最早被移除.栈中项的插入(push)和移除,只发生在一个位置--栈的顶部.ECMAScript为数组提供了push()和pop()方法,可以实现类似栈的行为.下面两图分别演示了入栈与出

  • JavaScript中数据结构与算法(一):栈

    序 数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧 git代码下载:https://github.com/JsAaron/data_structure.git 栈结构 特殊的列表,栈内的元素只能通过列表的一端访问,栈顶 后入先出(LIFO,last-in-first-out)的数据结构 javascript提供可操作的方法, 入栈 push,

  • javascript编程实现栈的方法详解【经典数据结构】

    本文实例讲述了javascript编程实现栈的方法.分享给大家供大家参考,具体如下: 栈是限定仅在表尾进行插入或删除操作的线性表,栈是先进后出的.栈的表尾称为栈顶(top),而表头端称为栈底(bottom). 和线性表类似,栈也有两种存储表示方法,顺序栈和链栈. 这里讲一下顺序栈,设置指针top指示栈顶元素在顺序栈中的位置.通常的做法就是以top=0表示空栈.base为栈底指针,top为栈顶指针. 如果base为null,则表示栈结构不存在,如果top=base则表示空栈.每当插入一个新的元素,

  • JavaScript数据结构与算法之栈详解

    在上一篇博客介绍了下列表,列表是最简单的一种结构,但是如果要处理一些比较复杂的结构,列表显得太简陋了,所以我们需要某种和列表类似但是更复杂的数据结构---栈.栈是一种高效的数据结构,因为数据只能在栈顶添加或删除,所以这样操作很快,而且容易实现. 一:对栈的操作. 栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端陈为栈顶.比如餐馆里面洗盘子,只能先洗最上面的盘子,盘子洗完后,也只能螺到这一摞盘子的最上面.栈被称为 "后入先出"(LIFO)的数据结构. 由于栈具有后入先出的特点

  • JS实现队列与堆栈的方法

    本文实例讲述了JS实现队列与堆栈的方法.分享给大家供大家参考,具体如下: 在面向对象的程序设计里,一般都提供了实现队列(queue)和堆栈(stack)的方法,而对于JS来说,我们可以实现数组的相关操作,来实现队列和堆栈的功能,看下面的相关介绍. 一.看一下它们的性质,这种性质决定了它们的使用场合 队列:是一种支持先进先出(FIFO)的集合,即先被插入的数据,先被取出! 堆栈:是一种支持后进先出(LIFO)的集合,即后被插入的数据,先被取出! 二.看一下实现的代码(JS代码) var a=new

随机推荐