发表于 | 分类于 |

引言

  • 原型和原型链是js中比较重要但也是比较难的内容；
  • 正是因为有了原型链的概念，js中的继承才成为可能；
  • 本文结合js内置的数据类型，说说我对js原型和原型链的理解；

Javascript和Java语言设计思想的区别

  • java
    • java是完全OOP的语言，对Java的认知是从类与对象开始的；
    • class是一类具有共同特点的物体的抽象，object（对象）是某个class下具体的一个实现，Object类是所有类的顶层父类；
  • js
    • javascript是基于原型（而不是基于类的，尽管ES6新增了class关键字）的面向对象的语言，没有类的概念（ES6新增的类是语法糖）；
    • javascript中的class本质上是一个函数对象，和java中的类的概念有本质区别；
    • javascript存在类似面相对象的特性，这就是原型和原型链，从而派生出了类似于父类子类和继承的概念；
  • 本图来自这里

java-js-diff

对象和数据类型

  • js中的数据类型:
    • 数据类型：string、number、boolean、object（数组、对象、null）、undefined、function；
    • 数组、对象、null是不精确的数据类型，在用typeof判断时均返回object；
    • typeof关键字只能返回非精确的数据类型；
    • 用Object.prototype.toString判断精确的数据类型；

type1

type2

  • 首字母大小写的区别：
    • 小写（string、number、boolean、object、null、undefined、function）表示数据类型；
    • 大写（String、Number、Boolean、Object、Array）表示js的内置对象（全部是function类型）；

typeof

  • js中对象的含义：
    • 广义的对象（js一切皆为对象、包括window和document对象、也包括String、Number、Boolean、Object、Array、Math、Date等内置对象）；
    • 狭义的数据类型（数组、对象、null类型均为object，即被typeof关键字判断为object类型）;
    • “对象”这种数据类型（请参考我的另一篇博客）；

原型链概述

  • JavaScript中的每个对象都有一个内部的链接指向另一个对象，这个对象就是原对象的原型，这个原型对象也有自己的原型，直到对象的原型为 null 为止（也就是没有原型）；
  • 这种一级一级的链结构就称为原型链（prototype chain）；
  • 每个对象都有一个隐形的属性proto（两边都是双下划线），这个属性的值为一个地址，指向这个属性的原型对象，原型对象是每个对象都有指向的隐形对象；
  • new出来的普通对象没有构造器，就没有prototype属性；
  • proto属性也可用someObject.[[Prototype]] 表示；
  • 如果一个对象是object类型，它的proto属性总是指向Object.prototype；
  • 如果一个对象是function类型，它的proto属性总是指向Function.prototype；
  • 继承属性：JavaScritp引擎在访问对象的属性时，如果在对象本身中没有找到，则会去原型链中查找，如果找到，直接返回值，如果整个链都遍历且没有找到属性，则返回undefined；

各种对象原型链的图示

  • String对象的原型链

string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var s = "sss";
var s1 = new String();

console.log(typeof String);  //function
console.log(typeof String.prototype);  //object
console.log(typeof String.prototype.constructor);  //function
console.log(typeof String.prototype.__proto__);  //object
console.log(typeof String.__proto__);  //function
console.log(typeof s1); //object
console.log(typeof s); //string
console.log(typeof s1.__proto__); //object
console.log(typeof s.__proto__); //object
console.log(String.prototype.constructor); // function String(){...}
console.log(String.prototype.__proto__);  //Object {}
console.log(String.__proto__);  //function(){}
console.log(String.__proto__ == Function.prototype);  //true
console.log(String.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(String.prototype.__proto__ == Object.prototype);  //true
console.log(s1);  //String {}
console.log(s1.__proto__);  //String {...}
console.log(s);  //sss
console.log(s.__proto__);  //String {...}
  • Number对象的原型链

number

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var n = 1;
var n1 = new Number();

console.log(typeof Number);  //function
console.log(typeof Number.prototype);  //object
console.log(typeof Number.prototype.constructor);  //function
console.log(typeof Number.prototype.__proto__);  //object
console.log(typeof Number.__proto__);  //function
console.log(typeof n1); //object
console.log(typeof n); //number
console.log(typeof n1.__proto__); //object
console.log(typeof n.__proto__); //object
console.log(Number.prototype.constructor); // function Number(){...}
console.log(Number.prototype.__proto__);  //Object {}
console.log(Number.__proto__);  //function(){}
console.log(Number.__proto__ == Function.prototype);  //true
console.log(Number.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Number.prototype.__proto__ == Object.prototype);  //true
console.log(n1);  //Number {}
console.log(n1.__proto__);  //Number {...}
console.log(n);  //1
console.log(n.__proto__);  //Number {...}
  • Boolean对象的原型链

boolean

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var b = true;
var b1 = new Boolean();

console.log(typeof Boolean);  //function
console.log(typeof Boolean.prototype);  //object
console.log(typeof Boolean.prototype.constructor);  //function
console.log(typeof Boolean.prototype.__proto__);  //object
console.log(typeof Boolean.__proto__);  //function
console.log(typeof b1); //object
console.log(typeof b); //boolean
console.log(typeof b1.__proto__); //object
console.log(typeof b.__proto__); //object
console.log(Boolean.prototype.constructor); // function Boolean(){...}
console.log(Boolean.prototype.__proto__);  //Object {}
console.log(Boolean.__proto__);  //function(){}
console.log(Boolean.__proto__ == Function.prototype);  //true
console.log(Boolean.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Boolean.prototype.__proto__ == Object.prototype);  //true
console.log(b1);  //Boolean {}
console.log(b1.__proto__);  //Boolean {...}
console.log(b);  //true
console.log(b.__proto__);  //Boolean {...}
  • Array对象的原型链

array

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var a =[1,2,3];
var a1 = new Array(); 

console.log(typeof Array);  //function
console.log(typeof Array.prototype);  //object
console.log(typeof Array.prototype.constructor);  //function
console.log(typeof Array.prototype.__proto__);  //object
console.log(typeof Array.__proto__);  //function
console.log(typeof a1); //object
console.log(typeof a); //object
console.log(typeof a1.__proto__); //object
console.log(typeof a.__proto__); //object
console.log(Array.prototype.constructor); // function Array(){...}
console.log(Array.prototype.__proto__);  //Object {}
console.log(Array.__proto__);  //function(){}
console.log(Array.__proto__ == Function.prototype);  //true
console.log(Array.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Array.prototype.__proto__ == Object.prototype);  //true
console.log(a1);  //[]
console.log(a1.__proto__);  //包含Array的各种方法
console.log(a);  //[1,2,3]
console.log(a.__proto__);  //包含Array的各种方法
  • Function对象的原型链

function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var f = function(){};
var f1 = new Function(); 

console.log(typeof Function);  //function
console.log(typeof Function.prototype);  //function
console.log(typeof Function.prototype.constructor);  //function
console.log(typeof Function.prototype.__proto__);  //object
console.log(typeof Function.__proto__);  //function
console.log(typeof f1); //function
console.log(typeof f); //function
console.log(typeof f1.__proto__); //function
console.log(typeof f.__proto__); //function
console.log(Function.prototype.constructor); // function Function(){...}
console.log(Function.prototype.__proto__);  //Object {}
console.log(Function.__proto__);  //function(){}
console.log(Function.__proto__ == Function.prototype);  //true
console.log(Function.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Function.prototype.__proto__ == Object.prototype);  //true
console.log(f1);  //function anonymous(){}
console.log(f1.__proto__);  //function(){}
console.log(f);  //function(){}
console.log(f.__proto__);  //function(){}
  • Object对象的原型链

object

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
   var o = {};
var o1 = new Object(); 

console.log(typeof Object);  //function
console.log(typeof Object.prototype);  //object
console.log(typeof Object.prototype.constructor);  //function
console.log(typeof Object.prototype.__proto__);  //object
console.log(typeof Object.__proto__);  //function
console.log(typeof o1); //object
console.log(typeof o); //object
console.log(typeof o1.__proto__); //object
console.log(typeof o.__proto__); //object
console.log(Object.prototype.constructor); // function Object(){...}
console.log(Object.prototype.__proto__);  //null
console.log(Object.__proto__);  //function(){}
console.log(Object.__proto__ == Function.prototype);  //true
console.log(Object.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Object.prototype.__proto__ == null);  //true
console.log(o1);  //Object{}
console.log(o1.__proto__);  //Object{...}
console.log(o);  //Object{}
console.log(o.__proto__);  //Object{...}
  • 自定义对象的原型链

myobject

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
   function Person(name,age){
	this.name = name;
	this.age = age;
}

var p1 = new Person("Jack",22);
var p = {"Jack":22};

console.log(typeof Person);  //function
console.log(typeof Person.prototype);  //object
console.log(typeof Person.prototype.constructor);  //function
console.log(typeof Person.prototype.__proto__);  //object
console.log(typeof Person.__proto__);  //function
console.log(typeof p1); //object
console.log(typeof p); //object
console.log(typeof p1.__proto__); //object
console.log(typeof p.__proto__); //object
console.log(Person.prototype.constructor); // function Person(){...}
console.log(Person.prototype.__proto__);  //Object {}
console.log(Person.__proto__);  //function(){}
console.log(Person.__proto__ == Function.prototype);  //true
console.log(Person.prototype.constructor.__proto__ == Function.prototype);  //true
console.log(Person.prototype.__proto__ == Object.prototype);  //true
console.log(p1);  //Person {name: "Jack", age: 22}
console.log(p1.__proto__);  //Person{...}
console.log(p);  //Object {Jack: 22}
console.log(p.__proto__);  //Object{...}
  • 最后附上一张知乎上面大神画的图，清楚地表示了Object和Function的继承关系

prototype

发表于 | 分类于 |

创建对象

  • 使用对象初始化器来创建对象
1
2
var obj = {key_1:value_1,
           key_2:value_2,...}
1
var myObj = {color: red, wheels:4, engine:{cylinders: 4, size: 2.2}}
  • 使用Object.create()方法创建对象
    • 语法是(属性描述符会在下面讲解)：
1
Object.create(proto, [ propertiesObject ])
1
2
3
4
5
6
7
8
9
o = Object.create(Object.prototype, {
  // foo会成为所创建对象的数据属性
  foo: { writable:true, configurable:true, value: "hello" },
  // bar会成为所创建对象的访问器属性
  bar: {
    configurable: false,
    get: function() { return 10 },
    set: function(value) { console.log("Setting `o.bar` to", value) }
}})
  • 混合构造函数和原型方式创建对象
1
2
3
4
5
6
7
8
9
10
11
function Parent(){
    this.name = "Jack";
    this.age = 22;
}

Parent.prototype.lev = function(){
    return this.name;
}

var x = new Parent();
alert(x.lev());  //Jack

对象属性的遍历

  • 遍历属性
1
2
3
4
var obj = {prop1: 4, prop2: 5, prop3: 6};
for(var i in obj){
    console.log(i);  //prop1 prop2 prop3
}
  • 遍历属性值
1
2
3
4
var obj = {prop1: 4, prop2: 5, prop3: 6};
for(var i in obj){
    console.log(obj[i]);  //4 5 6
}

对象常用操作

  • 对象的访问
    • obj.name和obj[“name”]效果一样；
  • 获取key值组成的数组
1
var arr = Object.keys(obj);
  • 删除对象或属性
1
2
3
delete objectName;
delete objectName.prop;
delete prop;  //仅仅在with语句中可以使用

getter和setter

  • getter和setter是对象属性的属性描述符的一种，可以在定义对象属性的时候指明；
  • getter和setter用于获取或者修改对象的某个属性；
  • 通过对象初始化器在创建对象的时候指明：
1
2
3
4
5
6
7
8
9
10
11
(function () {
    var o = {
        a : 7,
        get b(){return this.a +1;},  //通过 get,set的 b,c方法间接性修改a属性
        set c(x){this.a = x/2}
    };
    console.log(o.a);  //7
    console.log(o.b);  //8
    o.c = 50;
    console.log(o.a);  //25
})();
  • 使用 Object.create 方法指定：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(function () {
    var o = null;
    o = Object.create(Object.prototype,//指定原型为 Object.prototype
            {
                bar:{
                    get :function(){
                        return this.a;
                    },
                    set : function (val) {
                        console.log("Setting `o.bar` to ",val);
                        this.a = val;
                    },
                    configurable :true
                }
            }   //第二个参数
        );
    o.a = 10;
    console.log(o.bar);  //10
    o.bar = 12;
    console.log(o.bar);  //12
})();
  • 使用 Object.defineProperty 方法指定：
    • Object.defineProperty() 方法直接在一个对象上定义一个新属性，或者修改一个已经存在的属性，并返回这个对象;
    • 语法：Object.defineProperty(obj, prop, descriptor)
    • 参数：obj 需要定义属性的对象；prop 需被定义或修改的属性名；descriptor 需被定义或修改的属性的描述符；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(function () {
    var o = { a : 1}  //声明一个对象,包含一个 a 属性,值为1
    Object.defineProperty(o,"b",{
        get: function () {
            return this.a;
        },
        set : function (val) {
            this.a = val;
        },
        configurable : true
    });

    console.log(o.b);
    o.b = 2;
    console.log(o.b);
})();
  • 使用 Object.defineProperties方法指定：
    • 概述：Object.defineProperties() 方法在一个对象上添加或修改一个或者多个自有属性，并返回该对象;
    • 语法：Object.defineProperties(obj, props)
    • 参数：obj 将要被添加属性或修改属性的对象；props 该对象的一个或多个键值对定义了将要为对象添加或修改的属性的具体配置；
    • 用法与 Object.defineProperty 方法类似；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(function () {
    var obj = {a:1,b:"string"};
    Object.defineProperties(obj,{
        "A":{
            get:function(){return this.a+1;},
            set:function(val){this.a = val;}
        },
        "B":{
            get:function(){return this.b+2;},
            set:function(val){this.b = val}
        }
    });

    console.log(obj.A);
    console.log(obj.B);
    obj.A = 3;
    obj.B = "hello";
    console.log(obj.A);
    console.log(obj.B);
})();
  • 使用 Object.prototype.defineGetter以及 Object.prototype.defineSetter方法指定：
1
2
3
4
5
6
7
8
9
10
11
12
(function () {
    var o = {a:1};
    o.__defineGetter__("giveMeA", function () {
        return this.a;
    });
    o.__defineSetter__("setMeNew", function (val) {
        this.a  = val;
    })
    console.log(o.giveMeA);  //1
    o.setMeNew = 2;
    console.log(o.giveMeA);  //2
})();

属性描述符

  • 说明：
    • 对象里目前存在的属性描述符有两种主要形式：数据描述符和存取描述符。
    • 数据描述符是一个拥有可写或不可写值的属性。
    • 存取描述符是由一对 getter-setter 函数功能来描述的属性。
    • 描述符必须是两种形式之一；不能同时是两者。
  • 数据描述符和存取描述符均具有以下可选键值：
1
2
3
4
configurable
    当且仅当这个属性描述符值为 true 时，该属性可能会改变，也可能会被从相应的对象删除。默认为 false。
enumerable  
    true 当且仅当该属性出现在相应的对象枚举属性中。默认为 false。
  • 数据描述符同时具有以下可选键值：
1
2
3
4
value 
    与属性相关的值。可以是任何有效的 JavaScript 值（数值，对象，函数等）。默认为 undefined。
writable 
    true 当且仅当可能用 赋值运算符 改变与属性相关的值。默认为 false。
  • 存取描述符同时具有以下可选键值：
1
2
3
4
get 
    一个给属性提供 getter 的方法，如果没有 getter 则为 undefined。方法将返回用作属性的值。默认为 undefined。
set
    一个给属性提供 setter 的方法，如果没有 setter 则为 undefined。该方法将收到作为唯一参数的新值分配给属性。默认为 undefined。

  • 上面键值的含义：

    • 数据描述符包括两个属性 : value 属性以及 writable属性，第一个属性用来声明当前欲修饰的属性的值，第二个属性用来声明当前对象是否可写即是否可以修改；
    • 存取描述符就包括 get 与 set 属性用来声明欲修饰的象属性的 getter 及 setter；
    • 属性描述符内部，数据描述符与存取描述符只能存在其中之一，但是不论使用哪个描述符都可以同时设置 configurable 属性以及enumerable 属性；
    • configurable属性用来声明欲修饰的属性是否能够配置，仅有当其值为 true 时，被修饰的属性才有可能能够被删除，或者重新配置；
    • enumerable 属性用来声明欲修饰属性是否可以被枚举，决定属性是否能被 for…in 循环或 Object.keys 方法遍历得到；

  • create方法为显示配置对象的属性和值，如不声明将按照属性描述符的默认值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(function () {
    var obj = {};
    Object.defineProperty(obj,"key",{
    	value:"static"
                        //没有设置 enumerable 使用默认值 false
                        //没有 configurable 使用默认值 false
                        //没有 writable 使用默认值 false
                    });

    console.log(obj.key);           // static
    obj.key = "new"                 //尝试修改其值,修改将失败,因为 writable 为 false
    console.log(obj.key);           // static
    delete obj.key;                 //尝试删除属性,失败,因为 configurable 使用默认值 false
    console.log(obj.key);           // static
    obj.a = 1;                      //动态添加一个属性
    for(var item in obj){           //遍历所有 obj 的可枚举属性
    	console.log(item);
    }                               //只输出一个 “a” 因为 “key”的 enumerable为 false
})();
  • defineProperty、defineProperties方法为显示配置对象的属性和值，如不声明将按照属性描述符的默认值：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
(function () {
    var obj = {};
    Object.defineProperty(obj,"key",{
    	value : "static"
                         //没有设置 enumerable 使用默认值 false
                         //没有 configurable 使用默认值 false
                         //没有 writable 使用默认值 false
    })

    console.log(obj.key);           // static
    obj.key = "new"                 //尝试修改其值,修改将失败,因为 writable 为 false
    console.log(obj.key);           // static
    delete obj.key;                 //尝试删除属性,失败,因为 configurable 使用默认值 false
    console.log(obj.key);           // static
    obj.a = 1;                      //动态添加一个属性
    for(var item in obj){           //遍历所有 obj 的可枚举属性
    	console.log(item);
    }                               //只输出一个 “a” 因为 “key”的 enumerable为 false
})();
  • var o = {}; o.a = 1;这个语句却和上面不同，它的等价配置如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(function () {
    var o = {};
    o.a = 1;
    //等价于
    Object.defineProperty(o,"a",{value : 1,
                                writable : true,
                                configurable : true,
                                enumerable : true});
    
    Object.defineProperty(o,"a",{value :1});
    //等价于
    Object.defineProperty(o,"a",{value : 1,
                                writable : false,
                                configurable : false,
                                enumerable : false});
})();
  • Enumerable属性专项研究：
    • 属性特性 enumerable 决定属性是否能被 for…in 循环或 Object.keys 方法遍历得到；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(function () {
    var o = {};
    Object.defineProperty(o,"a",{value :1,enumerable :true});
    Object.defineProperty(o,"b",{value :2,enumerable :false});
    Object.defineProperty(o,"c",{value :2});   //enumerable default to false
    o.d = 4;    //如果直接赋值的方式创建对象的属性,则这个属性的 enumerable 为 true

    for(var item in o){ //遍历所有可枚举属性包括继承的属性
        console.log(item);  //a d
    }

    console.log(Object.keys(o)); //输出["a","d"],获取o对象的所有可遍历属性不包括继承的属性

    console.log(o.propertyIsEnumerable('a'));   //true
    console.log(o.propertyIsEnumerable('b'));   //false
    console.log(o.propertyIsEnumerable('c'));   //false
    console.log(o.propertyIsEnumerable('d'));   //true
})();
  • Configurable属性专项研究：
    • Configurable属性如果为false，表示对象的Configurable、Enumerable、value、writable、set、get属性一旦确定（包含默认确定的）就不能再更改，对象的这个属性也不能被删除；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(function () {
    var o = {};
    Object.defineProperty(o,"a",{get: function () {return 1;},
                                configurable : false} );
                                //enumerable 默认为 false,
                                //value 默认为 undefined,
                                //writable 默认为 false,
                                //set 默认为 undefined
                                  
    //抛出异常,因为最开始定义了 configurable 为 false,故后期无法对其进行再配置
    Object.defineProperty(o,"a",{configurable : true} );
    //抛出异常,因为最开始定义了 configurable 为 false,故后期无法对其进行再配置,enumerable 的原值为 false
    Object.defineProperty(o,"a",{enumerable : true} );
    //抛出异常,因为最开始定义了 configurable 为 false,set的原值为 undefined
    Object.defineProperty(o,"a",{set : function(val){}} );
    //抛出异常,因为最开始定义了 configurable 为 false,故无法进行覆盖,尽管想用一样的来覆盖
    Object.defineProperty(o,"a",{get : function(){return 1}});
    //抛出异常，因为最开始定义了 configurable 为 false,故无法将其进行重新配置把属性描述符从存取描述符改为数据描述符
    Object.defineProperty(o,"a",{value : 12});

    console.log(o.a);//输出1
    delete o.a;      //想要删除属性,将失败
    console.log(o.a);//输出1
    
})();

发表于 | 分类于 |

关于var关键字需要知道的

  • 对于var关键字，要么定义全局变量、要么定义函数内变量；
  • 不能定义只在一个语句块儿内部起作用的变量；
  • 这叫做js的函数级作用域(function-level scope)；
1
2
3
4
5
6
(function test(){
    if (true) {
      x = 5;  //x的作用域为全局
    }
    console.log(x); // 5
})();
1
2
3
4
5
6
7
8
9
10
function foo() { 
 	var x = 1; 
 	if (x) { 
 		(function () { 
 			var x = 2; 
 		}()); 
 	} 
 	console.log(x);  //1
 } 
foo();

在严格模式下不能定义一个不被var修饰的变量

1
2
3
4
5
6
7
8
(function test(){
 	if (true) {
 		x = 5;  //x的作用域为全局,严格模式报错
 	}
    console.log(x); // 5
})();

console.log(x); // 5

用let关键字定义块儿级作用域变量

  • 下面程序的lemma变量作用域为if语句块儿中；
1
2
3
4
5
6
7
8
9
"use strict"
function test(x,y){
 	if(x>y){
 		let lemma = x+3;
 		alert(lemma*y);  //5
 	}
 	alert(lemma);  // error
}
test(2,1)

javascript变量提升（hoisting）

  • 变量提升是指，你可以引用稍后声明的变量，而不会引发异常；
  • JavaScript变量感觉上是被“举起”或提升到了所有函数和语句之前；
  • 提升后的变量将返回 undefined 值；
  • 即使在使用或引用后面存在声明和初始化操作，仍将返回 undefined值；
1
2
console.log(x === undefined); // logs "true"
var x = 3;
1
2
3
4
5
6
var myvar = "my value";

(function() {
  console.log(myvar); // undefined
  var myvar = "local value";
})();

定义常量

  • 可以用关键字 const 创建一个只读的常量；
  • 常量标识符的命名规则和变量的相同：必须以字母、下划线或美元符号开头并可以包含有字母、数字或下划线；
  • 常量不可以通过赋值改变其值，也不可以在脚本运行时重新声明;
  • 常量，包括全局常量，都必须带const关键字;
  • 若const关键字被省略了，该标识符将被视为变量;
1
const prefix = '212';

发表于 | 分类于 |

引言

  • 严格模式是在ECMAscript 5中添加的；
  • 严格模式消除Javascript语法的一些不合理、不严谨之处，消除代码运行的一些不安全之处；
  • 严格模式提高编译器效率，增加运行速度；
  • 如果不主动声明，编译器默认是正常模式；

进入严格模式的方式

  • 在脚本第一行声明，则整个脚本都将以”严格模式”运行，如果这行语句不在第一行，则无效，整个脚本以”正常模式”运行；
  • 将”use strict”放在函数体的第一行，则整个函数以”严格模式”运行；
1
2
"use strict";
console.log("这是严格模式。");
1
2
3
4
function strict(){
　　"use strict";
　　return "这是严格模式";
}

严格模式”严格”了哪些语法行为

  • 全局变量必须显式声明
1
2
"use strict";
i=1;  //Uncaught ReferenceError: i is not defined
1
2
3
4
5
6
"use strict";
(function() {
    var a = b = 5;  //由于b没有用var关键自定义，严格模式下报错
})();

console.log(b);  //正常模式下b是全局变量，输出5
1
2
3
4
5
"use strict";
var arr = new Array(1,2,3);
for(i =0; i<arr.length; i++){  //Uncaught ReferenceError: i is not defined
    console.log(arr[i]);
}
  • 严格模式下不能使用with语句
1
2
3
4
5
6
7
8
"use strict"
var o = document.createElement("div");
with(o){   //Uncaught SyntaxError: Strict mode code may not include a with statement
	style.width = "100px";
	style.height = "100px";
	style.backgroundColor = "#000";
}
document.body.appendChild(o);
  • 严格模式下，eval作用域发生变化
    • 正常模式下，eval语句不形成单独的作用域，eval就相当于将其中的语句直接写到js中；
    • 严格模式下，eval语句形成了自己的作用域；
1
2
3
var x = 2;
console.info(eval("var x = 5; x")); // 5
console.info(x); // 5
1
2
3
4
"use strict";
var x = 2;
console.info(eval("var x = 5; x")); // 5
console.info(x); // 2

严格模式增强了哪些安全措施

  • this关键字禁止指向全局对象
1
2
3
4
5
6
7
8
function f(){
    return !this;  // 返回false，因为"this"指向全局对象，"!this"就是false
}

function f(){ 
    "use strict";
    return !this;  // 返回true，因为严格模式下，this的值为undefined，所以"!this"为true
}
1
2
3
4
5
"use strict";
function f(){
    this.name = 1;   //Uncaught TypeError: Cannot set property 'name' of undefined
};
f();
  • 限制使用函数内置对象
    • argument对象（比如遍历argument输出传入参数值）及其属性（比如argument.length）仍可使用， 但caller、callee不能使用；
    • argument对象不再追踪参数的变化情况;
1
2
3
4
5
6
7
8
9
10
11
12
"use strict";
function testCaller() {  
    alert(testCaller.caller);  //报错
    alert(arguments.callee);   //报错
}  

function aCaller() {  
    alert(arguments.length);  //由于传入参数个数为2，故输出2
    alert(arguments.caller);  //报错
    testCaller();
}  
aCaller("haha","heihei");
1
2
3
4
5
6
7
function f(a) {
 /*"use strict";*/
	a = 2;
	alert(arguments.caller);
	return [a, arguments[0]];
}
alert(f(1)); // 正常模式为[2,2], 严格模式为[2,1]
  • 禁止随意删除变量
    • 严格模式下无法删除变量；
    • 只有configurable设置为true的对象属性，才能被删除；
1
2
3
4
5
6
7
8
"use strict";
var x;
delete x; // 语法错误
var o = Object.create(null, {'x': {
　　　　value: 1,
　　　　configurable: true
}});
delete o.x; // 删除成功
  • 另外
    • 严格模式下，一个对象不能有重名的属性;
    • 严格模式下，一个函数不能传入重名的参数；
    • 严格模式下，禁止八进制表示法;
1
2
3
"use strict";
var o = {p:1,p:2};  //严格模式下报错
alert(o.p);  //正常模式下输出2
1
2
"use strict";
var i = 0100;  //Uncaught SyntaxError: Octal literals are not allowed in strict mode.

严格模式下的对象操作

  • 正常模式下，对一个对象的只读属性进行赋值，不会报错，只会默默地失败，严格模式下将报错;
1
2
3
4
"use strict";
var o = {};
Object.defineProperty(o, "v", { value: 1, writable: false });
o.v = 2; // 报错
  • 严格模式下，对一个使用getter方法读取的属性进行赋值，会报错；
1
2
3
4
5
"use strict";
var o = {
　　get v() { return 1; }
};
o.v = 2; // 报错
  • 严格模式下，对禁止扩展的对象添加新属性，会报错；
1
2
3
4
"use strict";
var o = {};
Object.preventExtensions(o);
o.v = 1; // 报错
  • 严格模式下，删除一个不可删除的属性，会报错；
1
2
"use strict";
delete Object.prototype; // 报错

保留字

  • 为了向将来Javascript的新版本过渡，严格模式新增了一些保留字：implements, interface, let, package, private, protected, public, static, yield；
  • 用这些新增保留字做变量名，正常模式不会报错，严格模式报错；
1
2
3
"use strict"
var implements = 1;  //Uncaught SyntaxError: Unexpected strict mode reserved word
alert(implements);

发表于 | 分类于 |

说明

  • 本文翻译自这篇文章
  • 文中并未就JSOPN提出更加安全的一个定义，但是为跨域访问策略的发展指明了一个方向；

引言

  • JSON是一种轻量级的数据交换格式。它是由Douglas Crockford正式提出的规范。JSON作为在两个实体间进行数据传输的强大工具的代表，无论发收数据的实体采用的是什么计算机语言，JSON已经被越来越多的接受和使用。

跨域访问的AJAX–简介

  • 浏览器的同源策略决定了，在数据传输时，如果目标资源所在的域等同于发出请求的页面，这样的传输行为才被允许。这一措施被所有的现代浏览器所采用，以防止不必要的或不安全的恶意JavaScript的用户行为。
  • 跨域Ajax是指突破同源策略的限制，使得跨域请求成为可能的想法。事实上，跨域的Ajax不是绝对的不安全或邪恶的，它实际上是许多世界上最流行和实用的应用中必不可少的。但是，由于种种原因，跨域Ajax始终和同源策略格格不入。

JSON-P (JSONP)

  • JSONP是这样的一个机制，它可以通过<script>标签请求不同域的内容。 2005年12月，Bob Ippolito正式提出JSONP（后来被称为JSON-P或JSON-with-padding），以此来充分利用的<script>标签的属性，实现跨域请求JSON格式的数据。JSON-P的工作原理是使一个<script>元素（HTML标签或通过JavaScript插入到DOM中），它请求服务器端的数据服务。HTTP请求的响应（装“的JavaScript”的实体内容）的内容是在请求中预先定义的，它通过参数传递给服务器端，提供被请求的JSON格式的数据的名称。当脚本执行时，相应的函数被调用，回传JSON格式的数据，从而使请求页面接收和处理这些数据。例子如下：
1
2
3
function handle_data(data) {
   // `data` is now the object representation of the JSON data
}
1
2
3
http://some.tld/web/service?callback=handle_data:

handle_data({"data_1": "hello world", "data_2": ["the","sun","is","shining"]});
  • 正如你所看到的，远端Web服务通过请求URL中的参数知道调用的函数的名称。只要该函数是在请求页面实际定义的，它会在收到数据后被调用。

问题

  • 迄今，JSON-P基本上已经被会议非正式的定义，事实上，浏览器可以接受任意的JavaScript响应。这意味着，任何依靠JSON-P的实现跨域访问的策略其实都将带来同源策略试图避免的危害。例如，一个恶意的Web服务可以通过调用函数发送JSONP请求，黑客可以通过返回的JavaScript信息窃取用户的隐私数据等。
  • 出于这个原因，很多人将JSON-P视为一种不安全和易被黑客利用的跨域Ajax策略，这似乎理由非常充分。所以，程序员们必须足够用心，在调用远程Web服务之前必须确认对方是受控或受信任的，这样才能避免他们的用户受到伤害。

替代方案

  • 有很多替代JSON-P实现跨域请求的办法，但每种方案都有自己的缺点和面临的挑战。这些技术将不会在这里详细介绍，除了这个：CORS（跨域资源共享）。 这是最近最流行的的JavaScript跨域Ajax调用方案之一。简单地说，CORS是一种扩展的XMLHttpRequest（又名“XHR”）对象，它可以让浏览器进行跨域调用（尽管存在同源策略的限制）。它会首先“预检测”目标服务器，确认服务器允许它这样做。
  • 换句话说，远程服务器能够选择加入或退出此类通信，基于它认为是否是合适的。例如，一台服务器可以应答用户端的Ajax请求，并从唯一认可的网站域名的一个预先定义的列表中获取一些内容回传客户端，而且拒绝任何其他页面中的所有其他请求。或者，如果服务器认为适合这样做，它可以开放其内容被任何其它域进行检索。
  • 乍一看，CORS可能看起来像是跨域Ajax请求的理想解决方案，使“黑客”无从下手。Nicholas Zakas最近写了一篇关于CORS的跨域Ajax请求方案，并指出它是浏览器跨域Ajax请求的解决方案中最有希望的一个。
  • CORS是否将最终成为浏览器跨域访问解决方案的标准，我们将拭目以待。当然它也有一些缺点，很可能存在一些细节问题（devil is always in the details）。
  • 首先，CORS需要实现一个Web服务，以实现拦截HTTP请求头中特殊的“预检”的授权请求，并根据服务器相关的策略，决定响应的格式。如果一个基于JSON格式的网络服务需要JSON-P跨域请求的支持，这相当简单，只需在一个函数调用中包装JSON数据块即可。
  • 在所有的互联网Web服务实现回传自定义数据更加值得期待，当然这取决于Web服务器软件的权限设置。这种技术可能需要若干年才能流行开来，并实现大部分的网络服务供应商兼容CORS。截至目前，这是非常新的技术，很少Web服务已经这样做了。
  • 此外，CORS仅在IE8浏览器开始实施（尽管有一些轻微的语法上的不同），尚未兼容Opera。因此，不支持CORS的情况时有发生，这意味着替代跨域Ajax的备选方案也许在1-3年后才可能推广开来。

可能的解决方案

  • 现在，JSON-P是跨域Ajax一个可行的解决方案。CORS可以减少黑客攻击的可能性，它可能应该在JSON-P技术串联部署，从而在不支持CORS的浏览器推广开来。然而，JSON-P的安全问题应当认真考虑并加以解决。
  • 所以，JSON-P严格的子集的定义是非常必要的。下面我们将介绍什么应视为有效、安全、可被允许的JSON-P。
1
2
3
4
5
functionName({JSON});

obj.functionName({JSON});

obj["function-name"]({JSON});
  • 其含义是，只能有一个函数表达式（函数的引用，或对象属性的引用）可用于作为该函数的JSON-P的响应，在这个单一的()中一定是严格有效的、可解析JSON对象。函数调用可以选择性地跟着一个分号。
  • 该提案的最关键的部分是浏览器厂商必须开始强制将这条规则应用于接收JSON-P回传数据的的<script>脚本上，并对任何不符合JSONP内容的错误抛出异常（或至少停止处理）。
  • 为了使浏览器能够知道什么时候应该过滤内容，或是看作是常规的JavaScript内容，MIME类型为“application / JSON-P”和/或“text/ JSON-P”的必须请求<script>标签中声明。

缺点

  • 不支持CORS的浏览器以及将来也不支持CORS的浏览器将不会拥有JSON-P的严格保护，这意味着，使用这些浏览器的用户将不会得到保护。但是，目前所有的浏览器都可以增加这个内容过滤功能，这对于使用尚未兼容CORS的浏览器的用户是一种安全支持。

注解

  • 一个可能的帮助老的浏览器用户安全的利用JSON-P技术的方案是提前检测浏览器没有这样的支持，并只对那些在不安全的浏览器中的、有条件的连接发出的请求启用本地服务器代理，它可以作为一个网关，并根据上面提到的逻辑进行内容过滤。

前瞻

  • 这是第一次讨论安全的JSON-P。在此，我主张在社区开放讨论，共同寻找可以向W3C，WHATWG和浏览器厂商宣传的一个可行的定义。
  • 最好方法是回复本文，或从本讨论建立链接。此外，本网站代码已经托管在GitHub上，你可以fork或修改以便继续讨论，然后通过pull操作更新讨论。最后，你可以在下面的评论表中作简短评论，但请保持简短，以便他人跟踪讨论进度。

发表于 | 分类于 |

引言

  • 堆是节点含有可比较对象，并以如下方式组织的完全二叉树：每个节点含有的对象不小于(最大堆)/不大于(最小堆)其后代中的对象；
  • 最大堆的根含有堆中最大的对象；
  • 最大堆中任何节点的子树也是最大堆；
  • 堆是java中重要的数据结构，堆排序算法就要用到堆；
  • 本文实现了简单的堆；

堆的实现

  • MyHeap类实现了堆的大部分方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
package heap;

import java.lang.reflect.Array;

public class MyHeap<T extends Comparable<T>> {
	public static final int INITIAL_SIZE = 16;
	Class<T> type;
	boolean flag = false;
	T[] heap;
	int size = 0; // 堆中元素数量

	// 构造器
	public MyHeap() {

	}

	// 构造器
	public MyHeap(Class<T> type) {
		heap = (T[]) Array.newInstance(type, INITIAL_SIZE);
		this.type = type;
	}

	// 清空堆
	public void clear() {
		heap = (T[]) Array.newInstance(type, INITIAL_SIZE);
		size = 0;
	}

	// 堆中元素数量
	public int size() {
		return size;
	}

	// 检查数组大小
	public void checkSize() {
		if (size > heap.length / 2) {
			T[] heap1 = (T[]) Array.newInstance(type, INITIAL_SIZE * 2);
			System.arraycopy(heap, 0, heap1, 0, heap.length);
			heap = heap1;
		}
	}

	// 求父节点数组下标
	public int getParent(int i) {
		return (i + 1) / 2 - 1;
	}

	// 求左子节点数组下标
	public int getLeftChild(int i) {
		int t = (i + 1) * 2 - 1;
		return t;
	}

	// 求右子节点数组下标
	public int getRightChild(int i) {
		int t = (i + 1) * 2;
		return t;
	}

	// 获取某元素下标
	public int getEle(T t) {
		for (int i = 0; i < size; i++) {
			if (heap[i].equals(t)) {
				flag = true;
				return i;
			}
		}
		return 0;
	}

	// 换位置
	public void swap(int i, int j) {
		T temp;
		temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}

	// 维护堆的性质(小顶堆)
	public void buildHeap(int i) {
		if (i > 0) {
			if (heap[i].compareTo(heap[getParent(i)]) < 0) {
				swap(i, getParent(i));
			}
			buildHeap(getParent(i));
		}
	}

	// 插入元素
	public void insert(T t) {
		checkSize();
		heap[size] = t;
		buildHeap(size);
		size++;
	}

	// 获取最小元素（堆顶元素）
	public T minEle() {
		return heap[0];
	}

	// 获取某个元素的父元素
	public T getParentEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (i == 0)
			return heap[0];
		else {
			return heap[getParent(i)];
		}
	}

	// 获取某元素左孩子
	public T getLeftChildEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (getLeftChild(i) >= size) {
			return null;
		} else {
			return heap[getLeftChild(i)];
		}
	}

	// 获取某元素的右孩子
	public T getRightChildEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (getRightChild(i) >= size) {
			return null;
		} else {
			return heap[getRightChild(i)];
		}
	}

	// 遍历堆（先序遍历）
	public void getPreOrder() {
		for (int i = 0; i < size; i++) {
			System.out.println(heap[i]);
		}
	}
}
  • TestMyHeap为测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package heap;

public class TestMyHeap {

	public static void main(String[] args) {
		MyHeap<Integer> h = new MyHeap<Integer>(Integer.class); 
		h.insert(10);
		h.insert(11);
		h.insert(9);
		System.out.println(h.size());  //3 
		h.getPreOrder();  //9 11 10
		System.out.println("----------");
		
		h.clear();
		h.insert(10);
		h.insert(11);
		h.insert(8);
		h.insert(9);
		h.insert(10);
		h.insert(12);
		h.insert(6);
		h.insert(13);
		h.insert(4);
		h.insert(7);
		System.out.println(h.size());  //10
		System.out.println(h.minEle());  //4
		h.getPreOrder();  //4 6 8 9 7 12 10 13 11 10
		System.out.println("----------");
		
		System.out.println(h.getParentEle(4));  //4
		System.out.println(h.getParentEle(6));  //4
		System.out.println(h.getParentEle(12)); //8
		System.out.println(h.getParentEle(13)); //9
		System.out.println(h.getParentEle(14)); //null
		System.out.println(h.getLeftChildEle(4));  //6
		System.out.println(h.getLeftChildEle(13)); //null
		System.out.println(h.getLeftChildEle(7));  //10
		System.out.println(h.getLeftChildEle(14)); //null
		System.out.println(h.getRightChildEle(4));  //8
		System.out.println(h.getRightChildEle(8));  //10
		System.out.println(h.getRightChildEle(7));  //null
		System.out.println(h.getRightChildEle(11)); //null
	}

}

发表于 | 分类于 |

引言

  • 树是重要的数据结构；
  • 本文简单介绍了树和二叉树的概念；
  • 本文详细实现了二叉查找树；

树的基本术语：

  • 树（Tree）是由显示节点间关系的边（edge）相连而成的节点的集合；
  • 这些节点排列在表明节点层次的各层（level）上；
  • 顶层是一个称为根（root）的单独节点；
  • 树的高度是树的层的数目，一般的，树的高度是从根到叶子的最长路径的长度加一；
  • 树的每个后继层中的节点是其上一层节点的孩子（children）；
  • 有孩子的节点是这些孩子的双亲（parent）；
  • 以某结点为根的子树中的任一节点成为该节点的子孙/后代（descendent）；
  • 从根到某节点所经分支上的所有节点成为该节点的祖先（ancestor）；
  • 双亲相同的孩子们被称为兄弟（sibling）；
  • 没有孩子的节点成为叶子（leaf）节点；
  • 不是叶子节点的节点被称作非叶节点（nonleaf）；

树的分类：

  • 一般树（general tree）：树中的每个节点可以有任意数量的孩子；
  • n叉树（n-ary tree）：树中的每个节点的孩子数量不超过n；
  • 二叉树（binary tree）：树种每个节点至多有两个孩子；

二叉树：

  • 二叉树每个节点至多有两个孩子，分别为左孩子（left child）和右孩子（right child）；
  • 二叉树节点的子树被称为左子树（left subtree）和右子树（right subtree）；
  • 二叉树的左子树是其根的左子树，二叉树的右子树是其根的右子树；
  • 二叉树中每个非叶节点都恰好有两个孩子，且最后一层全部填满，则称二叉树是满的（full）；
  • 二叉树中除了最后一层外其余层都含有尽可能多的节点，并且最后一层上的节点是从左到右填满的，则称这棵树是完全的（complete）；

二叉查找树

  • 每个节点的数据大于该节点左子树的数据；
  • 每个节点的数据小于该节点右子树的数据；

二叉查找树的实现

  • Node定义节点类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package binarytree;

public class Node<T> {
	Node<T> leftChid = null;
	Node<T> rightChild = null;
	T data;

	// 构造器
	public Node() {

	}
	
	//构造器
	public Node(T data){
		this.data = data;
	}

	public void display() {
		System.out.println(data + " ");
	}
	
	public Node<T> getLeftChid() {
		return leftChid;
	}

	public void setLeftChid(Node<T> leftChid) {
		this.leftChid = leftChid;
	}

	public Node<T> getRightChild() {
		return rightChild;
	}

	public void setRightChild(Node<T> rightChild) {
		this.rightChild = rightChild;
	}
}
  • BinaryTree类实现了二叉查找树的大部分方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
package binarytree;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

public class BinaryTree<T extends Comparable> {
	public int maxHeight = 8; // 默认树的最大高度为8
	public int size = 0; // 树的节点数量
	Node<T> root = null;

	// 构造器
	public BinaryTree() {

	}

	// 构造器
	public BinaryTree(int maxHeight) {
		this.maxHeight = maxHeight;
	}

	/*
	 * 基本动作
	 */

	// 清空二叉树
	public void clear() {
		root = null;
		size = 0;
	}

	// 判断是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// 判断是否是满树
	public boolean isFull() {
		// 利用满树的高度和元素个数的关系判断
		// 判断size+1是否是2的幂次即可
		if (size == 0) {
			return false;
		}
		int p = size + 1;
		while (p % 2 == 0) {
			p = p / 2;
		}
		if (p == 1) {
			return true;
		} else {
			return false;
		}
	}

	// 获取树的高度
	public int getHeight() {
		return height(root);
	}

	public int height(Node<T> subTree) {
		if (subTree == null)
			return 0; // 递归结束：空树高度为0
		else {
			int i = height(subTree.getLeftChid());
			int j = height(subTree.getRightChild());
			return (i < j) ? (j + 1) : (i + 1);
		}
	}

	// 返回结点个数
	public int getSize() {
		return size;
	}

	// 返回结点个数，第二种实现方法
	public int getSize2() {
		return size(root);
	}

	public int size(Node<T> subTree) {
		if (subTree == null) {
			return 0;
		} else {
			return 1 + size(subTree.getLeftChid())
					+ size(subTree.getRightChild());
		}
	}

	// 获取叶子节点总数
	int leafNumber = 0;

	public int getLeafNum() {
		leafNumber = 0;
		leafNum(root);
		return leafNumber;
	}

	public void leafNum(Node<T> subTree) {
		if (subTree != null) {
			if (subTree.getLeftChid() == null
					&& subTree.getRightChild() == null) {
				leafNumber++;
			}
			leafNum(subTree.getLeftChid());
			leafNum(subTree.getRightChild());
		}
	}

	/*
	 * 获取数据
	 */

	// 获取根节点数据
	public T getRoot() {
		return root.data;
	}

	// 获取双亲节点数据
	public T getParent(T data) {
		if (root == null) {
			return null;
		} else if (root.data.equals(data)) {
			return root.data;
		} else {
			return parent(root, data);
		}
	}

	public T parent(Node<T> subTree, T data) {
		// 思路：先找左子树，如果找到则返回数值，左子树找不到（左子树寻找结果为null的话）再去右子树找，
		// 如果找到则返回数值，找不到返回null
		if (subTree == null) {
			return null;
		}
		if (subTree.getLeftChid() != null
				&& subTree.getLeftChid().data.equals(data)) {
			return subTree.data;
		} else if (subTree.getRightChild() != null
				&& subTree.getRightChild().data.equals(data)) {
			return subTree.data;
		} else {
			T p;
			if ((p = parent(subTree.getLeftChid(), data)) != null) {
				return p;
			} else {
				return parent(subTree.getRightChild(), data);
			}
		}
	}

	// 获取左孩子结点数据
	public T getLeftChild(T data) {
		if (root == null) {
			return null;
		} else {
			return leftChild(root, data);
		}
	}

	public T leftChild(Node<T> subTree, T data) {
		// 思路：先找左子树，如果找到则返回数值，左子树找不到（左子树寻找结果为null的话）再去右子树找，
		// 如果找到则返回数值，找不到返回null
		if (subTree == null) {
			return null;
		}
		if (subTree.data.equals(data) && subTree.getLeftChid() != null) {
			return subTree.getLeftChid().data;
		} else {
			T p;
			if ((p = leftChild(subTree.getLeftChid(), data)) != null) {
				return p;
			} else {
				return leftChild(subTree.getRightChild(), data);
			}
		}
	}

	// 获取右孩子结点数据
	public T getRightChild(T data) {
		if (root == null) {
			return null;
		} else {
			return rightChild(root, data);
		}
	}

	public T rightChild(Node<T> subTree, T data) {
		// 思路：先找左子树，如果找到则返回数值，左子树找不到（左子树寻找结果为null的话）再去右子树找，
		// 如果找到则返回数值，找不到返回null
		if (subTree == null) {
			return null;
		}
		if (subTree.data.equals(data) && subTree.getRightChild() != null) {
			return subTree.getRightChild().data;
		} else {
			T p;
			if ((p = rightChild(subTree.getLeftChid(), data)) != null) {
				return p;
			} else {
				return rightChild(subTree.getRightChild(), data);
			}
		}
	}

	// 获取节点中的最小值
	T tMin;

	public T getMin() {
		if (root == null) {
			return null;
		} else {
			tMin = root.data;
			min(root);
			return tMin;
		}
	}

	public void min(Node<T> subTree) {
		if (subTree != null) {
			if (subTree.data.compareTo(tMin) < 0) {
				tMin = subTree.data;
			}
			min(subTree.getLeftChid());
			min(subTree.getRightChild());
		}
	}

	// 获取节点中的最大值
	T tMax;

	public T getMax() {
		if (root == null) {
			return null;
		} else {
			tMax = root.data;
			max(root);
			return tMax;
		}
	}

	public void max(Node<T> subTree) {
		if (subTree != null) {
			if (subTree.data.compareTo(tMax) > 0) {
				tMax = subTree.data;
			}
			max(subTree.getLeftChid());
			max(subTree.getRightChild());
		}
	}

	/*
	 * 插入和删除
	 */

	// 插入节点: 每个节点的数据大于该节点左子树的数据、小于该节点右子树的数据；
	public void insert(T t) throws Exception {
		if (root == null) {
			root = new Node<T>(t);
			size++;
		} else if (isFull() && getHeight() == maxHeight) {
			throw new Exception("二叉树已满且高度达到最大值！");
		} else {
			insertNode(root, t);
		}
	}

	// 插入节点具体行为
	public void insertNode(Node<T> node, T data) {
		if (data.compareTo(node.data) <= 0) {
			if (node.getLeftChid() == null) {
				node.setLeftChid(new Node<T>(data));
				size++;
			} else {
				insertNode(node.getLeftChid(), data);
			}

		} else {
			if (node.getRightChild() == null) {
				node.setRightChild(new Node<T>(data));
				size++;
			} else {
				insertNode(node.getRightChild(), data);
			}
		}
	}

	// 删除某个子树
	public void destroy(T t) {
		if (root == null) {
			return;
		} else if (root.data.equals(t)) {
			clear();
		} else {
			destroyNode(root, t);
		}
	}

	public void destroyNode(Node<T> subTree, T t) {
		//思路：先检查当前节点的左子树是否符合要求，符合则删除，不符合再检查右子树是否符合要求，符合则删除
		//若左右子树都不符合，迭代查询下层节点的左右子树
		//如果当前节点为null或叶子节点，不予检查，直接返回
		if (subTree != null
				&& (subTree.getLeftChid() != null || subTree.getRightChild() != null)) {
			if (subTree.getLeftChid() != null
					&& subTree.getLeftChid().data.equals(t)) {
				subTree.setLeftChid(null);
				size--;
			}
			if (subTree.getRightChild() != null
					&& subTree.getRightChild().data.equals(t)) {
				subTree.setRightChild(null);
				size--;
			}
			destroyNode(subTree.getLeftChid(), t);
			destroyNode(subTree.getRightChild(), t);
		}
	}

	/*
	 * 递归遍历
	 */

	// 先序遍历
	public void getPreOrder() {
		preOrder(root);
	}

	public void preOrder(Node<T> subTree) {
		if (subTree != null) {
			visit(subTree);
			preOrder(subTree.getLeftChid());
			preOrder(subTree.getRightChild());
		}
	}

	public void visit(Node<T> node) {
		node.display();
	}

	// 中序遍历
	public void getInOrder() {
		inOder(root);
	}

	public void inOder(Node<T> subTree) {
		if (subTree != null) {
			inOder(subTree.getLeftChid());
			visit(subTree);
			inOder(subTree.getRightChild());
		}
	}

	// 后序遍历
	public void getPostOrder() {
		postOrder(root);
	}

	public void postOrder(Node<T> subTree) {
		if (subTree != null) {
			postOrder(subTree.getLeftChid());
			postOrder(subTree.getRightChild());
			visit(subTree);
		}
	}

	// 按层次遍历
	public void levelTraverse() {
		levelTraverse(root);
	}

	public void levelTraverse(Node<T> node) {
		Queue<Node<T>> queue = new LinkedBlockingQueue<Node<T>>();
		queue.add(node);
		while (!queue.isEmpty()) {
			Node<T> temp = queue.poll();
			if (temp != null) {
				temp.display();
				if (temp.getLeftChid() != null)
					queue.add(temp.getLeftChid());
				if (temp.getRightChild() != null)
					queue.add(temp.getRightChild());
			}
		}
	}

	/*
	 * 非递归遍历
	 */

	// 先序遍历
	public void nrPreOrder() {
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;

		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				node.display();
				stack.push(node);
				node = node.getLeftChid();
			}
			node = stack.pop();
			node = node.getRightChild();
		}
	}

	// 中序遍历
	public void nrInOrder() {
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;
		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.getLeftChid();
			}
			node = stack.pop();
			node.display();
			;
			node = node.getRightChild();
		}
	}

	// 后序遍历
	public void nrPostOrder() {
		Stack<Node<T>> stack = new Stack<Node<T>>();
		Node<T> node = root;
		Node<T> preNode = null; // 表示最近一次访问的节点

		while (node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.getLeftChid();
			}

			node = stack.peek();
			if (node.getRightChild() == null || node.getRightChild() == preNode) {
				node.display();
				node = stack.pop();
				preNode = node;
				node = null;
			} else {
				node = node.getRightChild();
			}
		}
	}
}

BinaryTreeTest为测试类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package binarytree;

public class BinaryTreeTest {

	public static void main(String[] args) throws Exception {
		BinaryTree<Integer> b = new BinaryTree<Integer>();

		b.insert(0);
		System.out.println(b.isEmpty()); // false
		System.out.println(b.getSize()); // 1
		b.clear();
		System.out.println(b.isEmpty()); // true
		System.out.println(b.getSize()); // 0
		System.out.println("-----------");

		b.insert(11);
		b.insert(10);
		b.insert(14);
		System.out.println(b.isFull()); // true
		System.out.println(b.getHeight()); // 2
		System.out.println(b.getSize()); // 3
		System.out.println(b.getSize2()); // 3
		System.out.println(b.getLeafNum()); // 2
		System.out.println("-----------");
		b.insert(15);
		System.out.println(b.isFull()); // false
		System.out.println(b.getHeight()); // 3
		System.out.println(b.getSize()); // 4
		System.out.println(b.getSize2()); // 4
		System.out.println(b.getLeafNum()); // 2
		System.out.println("-----------");
		b.insert(12);
		System.out.println(b.isFull()); // false
		System.out.println(b.getHeight()); // 3
		System.out.println(b.getSize()); // 5
		System.out.println(b.getSize2()); // 5
		System.out.println(b.getLeafNum()); // 3
		System.out.println("-----------");
		b.destroy(15);
		System.out.println(b.isFull()); // false
		System.out.println(b.getHeight()); // 3
		System.out.println(b.getSize()); // 4
		System.out.println(b.getSize2()); // 4
		System.out.println(b.getLeafNum()); // 2
		System.out.println("-----------");
		b.insert(16);
		b.insert(17);
		b.insert(15);
		b.insert(18);
		System.out.println(b.isFull()); // false
		System.out.println(b.getHeight()); // 5
		System.out.println(b.getSize()); // 8
		System.out.println(b.getSize2()); // 8
		System.out.println(b.getLeafNum()); // 4
		System.out.println(b.getRoot()); // 11
		System.out.println("-----------");

		System.out.println(b.getParent(10)); // 11
		System.out.println(b.getParent(16)); // 14
		System.out.println(b.getParent(12)); // 14
		System.out.println(b.getParent(17)); // 16
		System.out.println(b.getParent(18)); // 17
		System.out.println(b.getParent(20)); // null
		System.out.println("-----------");

		System.out.println(b.getLeftChild(11)); // 10
		System.out.println(b.getLeftChild(10)); // null
		System.out.println(b.getLeftChild(14)); // 12
		System.out.println(b.getLeftChild(16)); // 15
		System.out.println(b.getLeftChild(15)); // null
		System.out.println(b.getLeftChild(17)); // null
		System.out.println(b.getLeftChild(18)); // null
		System.out.println("-----------");

		System.out.println(b.getRightChild(11)); // 14
		System.out.println(b.getRightChild(10)); // null
		System.out.println(b.getRightChild(14)); // 16
		System.out.println(b.getRightChild(12)); // null
		System.out.println(b.getRightChild(16)); // 17
		System.out.println(b.getRightChild(17)); // 18
		System.out.println(b.getRightChild(18)); // null
		System.out.println("-----------");

		System.out.println(b.getMin()); // 10
		System.out.println(b.getMax()); // 18
		System.out.println("-----------");

		b.getPreOrder();
		System.out.println("-----------"); // 11 10 14 12 16 15 17 18
		b.getInOrder();
		System.out.println("-----------"); // 10 11 12 14 15 16 17 18
		b.getPostOrder();
		System.out.println("-----------"); // 10 12 15 18 17 16 14 11
		b.levelTraverse();
		System.out.println("-----------"); // 11 10 14 12 16 15 17 18
		b.nrPreOrder();
		System.out.println("-----------"); // 11 10 14 12 16 15 17 18
		b.nrInOrder();
		System.out.println("-----------"); // 10 11 12 14 15 16 17 18
		b.nrPostOrder();
		System.out.println("-----------"); // 10 12 15 18 17 16 14 11
	}
}

发表于 | 分类于 |

引言

  • 队列是java中重要的数据结构；
  • 本文用数组实现了简单的单端队列；

单端队列的实现

  • MyQueue类实现了队列的大部分方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
package queuetest;

public class MyQueue<T> {
	public int size = 0; // 当前队列长度
	public int maxSize = 8; // 队列容量，默认8

	protected T[] queue = (T[]) new Object[maxSize]; // 队列用数组实现

	// 构造器
	public MyQueue() {

	}

	// 构造器
	public MyQueue(int maxSize) {
		this.maxSize = maxSize;
	}

	// 清空队列
	public void clear() {
		queue = (T[]) new Object[maxSize];
		size = 0;
	}

	// add,如果队列已满，则抛出异常
	public void add(T t) throws Exception {
		if (size == maxSize) {
			throw new Exception("队列容量已满.");
		} else {
			queue[size] = t;
			size++;
		}
	}

	// offer，添加一个元素并返回true，如果队列已满，则返回false
	public boolean offer(T t) {
		if (size < maxSize) {
			queue[size] = t;
			size++;
			return true;
		}
		return false;
	}

	// element,返回队列头部的元素,如果队列为空,则抛出异常
	public T element() throws Exception {
		if (size == 0) {
			throw new Exception("队列为空！");
		} else {
			return queue[0];
		}
	}

	// peek,返回队列头部的元素,如果队列为空，则返回null
	public T peek() {
		if (size == 0) {
			return null;
		} else {
			return queue[0];
		}
	}

	// remove,移除并返回队列头部的元素,如果队列为空则抛出异常
	public T remove() throws Exception {
		if (size != 0) {
			T t = queue[0];
			for (int i = 0; i < size - 1; i++) {
				queue[i] = queue[i + 1];
			}
			queue[size - 1] = null;
			size--;
			return t;
		} else {
			throw new Exception("队列为空！");
		}
	}

	// poll,移除并返问队列头部的元素,如果队列为空则返回null
	public T poll() {
		if (size != 0) {
			T t = queue[0];
			for (int i = 0; i < size - 1; i++) {
				queue[i] = queue[i + 1];
			}
			queue[size - 1] = null;
			size--;
			return t;
		} else {
			return null;
		}
	}

	// 当前队列长度
	public int size() {
		return size;
	}

	// 是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// 遍历队列元素
	public void display() {
		for (int i = 0; i < size; i++) {
			System.out.println(queue[i]);
		}
	}
}
  • MyQueueTest 测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
package queuetest;

public class MyQueueTest {

	public static void main(String[] args) throws Exception {
		MyQueue<String> mq = new MyQueue<String>(4);
		mq.add("111");
		mq.add("222");
		mq.add("333");
		mq.add("444");
		System.out.println(mq.size());  //4
//		mq.add("555");  //java.lang.Exception: 队列容量已满.
		System.out.println(mq.size());  //4
		System.out.println(mq.offer("666"));  //false
		System.out.println(mq.size());  //4
		System.out.println("-----------");
		
		System.out.println(mq.element());  //111
		System.out.println(mq.peek());  //111
		System.out.println("-----------");
		
		System.out.println(mq.isEmpty());  //false
		mq.display();  //111 222 333 444
		System.out.println("-----------");
		
		System.out.println(mq.remove());  //111
		System.out.println(mq.remove());  //222
		System.out.println(mq.remove());  //333
		System.out.println(mq.remove());  //444
		System.out.println(mq.size());    //0
//		System.out.println(mq.remove());  //java.lang.Exception: 队列为空！
		System.out.println(mq.poll());  //null
		System.out.println(mq.size());  //0
//		System.out.println(mq.element());  //java.lang.Exception: 队列为空！
		System.out.println(mq.peek());  //null
	}

}

发表于 | 分类于 |

引言

  • 双端队列是java中重要的数据结构，有着广泛的应用；
  • 双端队列一般用双向链表实现；
  • 本文就用双向链表实现了简单的双端队列；

Deque的实现

  • Node类定义双端队列的节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
package deque;

public class Node<T> {
	public Node<T> before;
	public Node<T> after;
	public T data;

	// 构造器
	public Node() {

	}

	// 构造器
	public Node(T t) {
		this.data = t;
	}

	public Node<T> getBefore() {
		return before;
	}

	public void setBefore(Node<T> before) {
		this.before = before;
	}

	public Node<T> getAfter() {
		return after;
	}

	public void setAfter(Node<T> after) {
		this.after = after;
	}
	
	public void display() {
		System.out.println(data + " ");
	}
}
  • Deque类实现了双端队列的大部分方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package deque;

public class Deque<T> {
	public int maxSize = 8; // 默认队列容量为8
	public int size = 0; // 双端队列的长度
	public Node<T> first; // 首节点
	public Node<T> last; // 尾节点

	// 构造器
	public Deque() {

	}

	// 构造器
	public Deque(int maxSize) {
		this.maxSize = maxSize;
	}

	// 清空队列
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}

	// 在首部添加
	public void addToFront(T t) throws Exception {
		Node<T> node = new Node<T>();
		node.data = t;
		if (size == 0) {
			first = node;
			last = node;
			size++;
		} else if (size < maxSize) {
			node.setAfter(first);
			first.setBefore(node);
			first = node;
			size++;
		} else {
			throw new Exception("队列已满！");
		}
	}

	// 在尾部添加
	public void addToBack(T t) throws Exception {
		Node<T> node = new Node<T>();
		node.data = t;
		if (size == 0) {
			first = node;
			last = node;
			size++;
		} else if (size < maxSize) {
			node.setBefore(last);
			last.setAfter(node);
			last = node;
			size++;
		} else {
			throw new Exception("队列已满！");
		}
	}

	// 从首部删除
	public void removeFront() throws Exception {
		if (size == 0) {
			throw new Exception("队列为空");
		} else if (size == 1) {
			clear();
		} else {
			first = first.getAfter();
			first.setBefore(null);
			size--;
		}
	}

	// 从尾部删除
	public void removeBack() throws Exception {
		if (size == 0) {
			throw new Exception("队列为空");
		} else if (size == 1) {
			clear();
		} else {
			last = last.getBefore();
			last.setAfter(null);
			size--;
		}
	}

	// 获取首部元素
	public T getFront() {
		if (size == 0) {
			return null;
		} else {
			return first.data;
		}
	}

	// 获取尾部元素
	public T getBack() {
		if (size == 0) {
			return null;
		} else {
			return last.data;
		}
	}

	// 判断是否为空
	public boolean isEmpty() {
		return size == 0;
	}
	
	//判断是否队列已满
	public boolean isFull(){
		return size==maxSize;
	}
	
	//获取队列长度
	public int size(){
		return size;
	}

	// 输出队列全部内容
	public void displayAll() {
		if (size != 0) {
			Node<T> node = first;
			while (node != null) {
				node.display();
				node = node.getAfter();
			}
		}
	}
}
  • DuqueTest测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package deque;

public class DequeTest {

	public static void main(String[] args) throws Exception {
		Deque<String> d = new Deque<String>(8);
		d.addToFront("111");
		d.addToFront("222");
		d.addToBack("333");
		System.out.println(d.size());  //3
		d.displayAll();  //222 111 333
		System.out.println("----------");
		
		d.clear();
		System.out.println(d.size());  //0
		System.out.println("----------");
		
		d.addToFront("aaa");
		d.addToFront("bbb");
		d.addToFront("ccc");
		d.addToFront("ddd");
		d.addToBack("eee");
		d.addToBack("fff");
		System.out.println(d.size());  //6
		d.displayAll();  //ddd ccc bbb aaa eee fff  
		System.out.println("----------");
		
		d.removeFront();
		d.removeBack();
		d.removeBack();
		System.out.println(d.size());  //3 
		d.displayAll();  //ccc bbb aaa
		System.out.println("----------");
		
		System.out.println(d.getFront());  //ccc
		System.out.println(d.getBack());  //aaa
		System.out.println("----------");
		
		System.out.println(d.isEmpty());  //false
		System.out.println(d.isFull());   //false
	}

}

发表于 | 分类于 |

引言

  • Stack是java中常用的数据结构；
  • 栈遵循先进后出，后进先出；
  • 本文实现了一个简单的栈；

栈的实现

  • MyStack实现了栈的大部分方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package test6;

public class MyStack<T> {
	public static final int DEFAULT_INITIAL_CAPACITY = 16;
	public int size = 0; // 栈大小
	protected T[] stack = (T[]) new Object[DEFAULT_INITIAL_CAPACITY];

	// 清空栈
	public void clear() {
		stack = (T[]) new Object[DEFAULT_INITIAL_CAPACITY];
		size = 0;
	}

	// 判断容量
	public void testCapacity() {
		if (size >= stack.length) {
			T[] stack1 = (T[]) new Object[stack.length * 2];
			System.arraycopy(stack, 0, stack1, 0, stack.length);
			stack = stack1;
		}
	}

	// 判断是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	// Looks at the object at the top of this stack without removing it from the
	// stack
	public T peek() {
		return stack[size - 1];
	}

	// 压入数据
	public void push(T t) {
		testCapacity();
		stack[size] = t;
		size++;
	}

	// 弹出数据
	public T pop() {
		T t = stack[size - 1];
		size--;
		return t;
	}
	
	//Returns the 1-based position where an object is on this stack
	public int search(T t){
		for(int i =size-1; i>=0; i--){
			if(stack[i].equals(t)){
				return size-i;
			}
		}
		return -1;
	}
	
	//获取容量
	public int size(){
		return size;
	}
}
  • TestMyStack测试类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
package test6;

public class TestMyStack {

	public static void main(String[] args) {
		MyStack<String> s = new MyStack<String>();
		s.push("111");
		s.push("222");
		System.out.println(s.size());  //2
		s.clear();
		System.out.println(s.size());  //0
		System.out.println("----------");
		
		s.push("aaa");
		s.push("bbb");
		s.push("ccc");
		s.push("ddd");
		System.out.println(s.size());  //4
		System.out.println(s.isEmpty());  //false
		System.out.println(s.search("ccc"));  //2
		System.out.println(s.peek());  //ddd
		System.out.println("----------");
		
		s.pop();
		System.out.println(s.peek());  //ccc
	}

}