数组、栈、队列

发表于 | 分类于

数组

数组的创建与初始化

  • new关键字
1
2
var color = new Array()
var colors = new Array('red','yellow','blue')
  • 数组字面量
1
2
var color = []
var colors = ['red','yellow','blue']

检测数组

检测某个对象是不是数组

ES3中的方法

1
2
3
if（value instanceof Array）{
	//如果是数组，执行某些操作
}

如果页面中包含多个框架，那实际上就存在两个以上的不同全局执行环境，从而存在两个以上的不同版本的Array构造函数。

ES5中的方法，也是现在使用的方法

兼容性： IE9+

1
2
3
if (Array.isArray(value) {
	//对数组执行某些操作
})

转换方法

1
2
3
4
5
toString(): 返回数组中每个值的字符串形式拼接而成的一个以逗号隔开的字符串。

valueOf()：返回的仍然是数组

toLocaleString(): 在大多数情况与前两者相同，不同之初是调用数组中每一项的toLocaleString（），而不是toString（）方法。

添加和删除元素

通过下标直接赋值:

1
2
var numbers = [1,2,3,4,5]
numbers[5] = 6

栈方法

1
2
3
push()  //可以接收任意数量的参数，把他们逐个添加到数组末尾，并返回修改后数组的长度

pop() //从数组 末尾移除最后一项

队列方法

1
2
3
4
5
shift() //移除数组中的第一个项并返回，同时数组长度减一

push() //向数组末端添加元素

unshift() //在数组前端任意项并返回新数组的长度

操作方法

concat() 方法

将一个或多个字符串与原字符串连接合并，形成一个新的字符串并返回。

1
2
var hello = "Hello, ";
console.log(hello.concat("Kevin", " have a nice day.")); /* Hello, Kevin have a nice day. */

slice() 方法

返回一个从开始到结束（不包括结束）选择的数组的一部分浅拷贝到一个新数组对象。原始数组不会被修改。

splice() 方法

通过删除现有元素和/或添加新元素来更改一个数组的内容

返回值: 由被删除的元素组成的一个数组。如果只删除了一个元素，则返回只包含一个元素的数组。如果没有删除元素，则返回空数组

1
2
3
4
5
6
7
8
9
var myFish = ['angel', 'clown', 'mandarin', 'sturgeon'];

myFish.splice(2, 0, 'drum'); 
// 在索引为2的位置插入'drum'
// myFish 变为 ["angel", "clown", "drum", "mandarin", "sturgeon"]

myFish.splice(2, 1); 
// 从索引为2的位置删除一项（也就是'drum'这一项）
// myFish 变为 ["angel", "clown", "mandarin", "sturgeon"]

位置方法

indexOf() 方法

indexOf()方法返回在数组中可以找到一个给定元素的第一个索引，如果不存在，则返回-1。

1
2
3
4
5
6
7
8
9
10
let a = [2, 9, 7, 8, 9]; 
a.indexOf(2); // 0 
a.indexOf(6); // -1
a.indexOf(7); // 2
a.indexOf(8); // 3
a.indexOf(9); // 1

if (a.indexOf(3) === -1) {
  // element doesn't exist in array
}

lastIndexOf() 方法

lastIndexOf() 方法可返回一个指定的字符串值最后出现的位置，在一个字符串中的指定位置从后向前搜索。

参数 描述
searchvalue 必需。规定需检索的字符串值。
fromindex 可选的整数参数。规定在字符串中开始检索的位置。它的合法取值是 0 到 stringObject.length - 1。如省略该参数，则将从字符串的最后一个字符处开始检索。

1
2
3
var numbers = [2, 5, 9, 2];
numbers.lastIndexOf(2); // 3
numbers.lastIndexOf(7); // -1

迭代方法

every()

对数组中的每一项运行给定函数，如果函数对每一项都返回true，则返回true

filter()

对数组中的每一项运行给定函数，返回给函数会返回true的数组

forEach()

对数组中的每一项运行给定函数。这个方法没有返回值

map()

对数组中的每一项运行给定函数，返回每次函数调用返回结果组成的数组。

some()

对数组中的每一项运行给定函数，如果任一个函数返回true，则返回true

归并方法

reduce

从数组第一项开始，逐个遍历到最后。

1
2
3
4
5
6
7
8
9
var total = [0, 1, 2, 3].reduce(function(sum, value) {
  return sum + value;
}, 0);
// total is 6

var flattened = [[0, 1], [2, 3], [4, 5]].reduce(function(a, b) {
  return a.concat(b);
}, []);
// flattened is [0, 1, 2, 3, 4, 5]

reduceRight（）

则从数组的最后一项开始，向前遍历到第一项。

栈

栈是一种遵从后进先出（LIFO）原则的有序集合。新添加的或待添加的元素都保存在栈的末尾，称作栈顶，另一端叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。

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
function Stack() {
    var items = []

    this.push = function (element) {
        items.push(element)
    }

    this.pop = function () {
        items.pop()
    }

    this.peek = function () {
        return items[items.length - 1]
    }

    this.isEmpty = function () {
        return items.length == 0 
    }

    this.size = function () {
        return items.length
    }

    this.print = function () {
        console.log(items.toString())
    }
}

var stack = new Stack()
console.log(stack.isEmpty())

stack.push(3)
stack.push(6)
stack.push(8)
stack.print()

console.log(stack.peek())

/*
luoyecs-iMac:js数据结构与算法 LW-luoyec$ node stack.js
true
3,6,8
8
*/

队列

队列是遵循FIFO（先进先出，也成为先来先服务）原则的一组有序的项。队列的尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

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
function Queue () {
    var items = []

    this.enqueue = function (element) {
        items.push(element)
    }

    this.dequeue = function () {
        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()
console.log(queue.isEmpty())

queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)

queue.print()

queue.dequeue()

queue.print()