利用JavaScript学习基础的数据结构: 数组, 栈, 队列.

数组

一般来说, 数组存储一系列同一种数据类型的值.但因为JavaScript是动态类型(Dynamic Typing), 数组中的类型不需要一致, 可以包含不同类型的值.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var arr = [
  1,
  false,
  {
    name: 'Tony',
    address: '111 Main St.'
  },
  function(name){
    var greeting = "Hello ";
    console.log(greeting + name);
  },
  // 为什么这个function是函数表达式? (inside of an object, created on the fly)
  "hello"
];
// 可以这样调用函数
arr[3](arr[2].name); // "Hello Tony"

在JavaScript中,数组是一个可以修改的对象.如果添加元素,它就会动态增长.在C和Java等其他语言里,我们要决定数组的大小,想添加元素就要创建一个全新的数组,不能简单地往其中添加所需的元素.

添加和删除数组首尾元素

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
var numbers = [0,1,2,3,4,5,6,7,8,9];

// 添加元素到数组最后
// 1
numbers[numbers.length]=10;

// 2
numbers.push(12);
numbers.push(12,23);

// 添加元素到数组最前
// 1
for(var i = numbers.length; i>=0; i--){
  numbers[i] = numbers[i-1];
}
numbers[0] = -1;

// 2
numbers.unshift(-2);
numbers.unshift(-3, -4);

// 删除数组中最靠后的元素
// 1
numbers.pop();

// 移除数组中第一个元素
// 1
for(var i = 0; i < numbers.length; i++){
  numbers[i] = numbers[i+1];
};
numbers.pop();//上述循环只是将数组后一位元素覆盖前一位, 因此需要利用pop⬇️将最后一位移除

// 2
numbers.shift();
  • 通过push和pop方法,就能用数组来模拟栈
  • 通过shift和unshift方法,就能用数组模拟基本的队列数据结构

添加和删除数组任意元素

1
2
3
4
5
6
7
var numbers = [0,1,2,3,4,5,6,7,8,9];

// 删除从数组索引5开始的3个元素
numbers.splice(5,3);

// 从索引5开始, 不删除元素, 分别添加2,3,4三个元素
numbers.splice(5,0,2,3,4);

二维和多维数组

JavaScript只支持一维数组,并不支持矩阵(二维数组).但可以用数组套数组,实现矩阵或任一多维数组.

创建3x3矩阵:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var matrix3x3x3 = [];

for(var i=0; i<3; i++){
  matrix3x3x3[i] = [];
  for(var j=0; j<3; j++){
    matrix3x3x3[i][j] = [];
    for(var z=0; z<3; z++){
      matrix3x3x3[i][j][z] = i+j+z;
    }
  }
}
// 查看矩阵输出:

function printMatrix(matrix){
  for(var i=0; i<matrix.length; i++){
    for(var j=0; j<matrix[i].length; j++){
      for(var z=0; z<matrix[i][j].length;z++){
        console.log(matrix[i][j][z]);
      };
    }
  }
};

printMatrix(matrix3x3x3);

栈

两种数据结构类似于数组,但在添加和删除元素时更为可控.它们就是栈和队列.

栈是一种遵从后进先出(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
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
function Stack(){
  // 利用数组保存栈内的元素
  var items = [];

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

  // 移除栈顶元素, 同时返回被移除的元素
  this.pop = function(element){
    return items.pop();
  };
  //只能用push和pop方法添加删除栈中元素, 遵从LIFO原则

  // 返回栈顶元素, 不对栈做任何修改
  this.peek = function(){
    return items[items.length-1];
  };

  // 如果栈中没有元素就返回true, 否则返回false
  this.isEmpty = function(){
    return items.length === 0;
  };

  // 返回栈中元素个数,与数组的length属性功能相似
  this.size = function(){
    return items.length;
  };

  // 移除栈中所有元素
  this.clear = function(){
    items = [];
  };


  // 将栈中所有元素输出到控制台
  this.print = function(){
    console.log(items.toString());
  };
};

// 实例化Stack类
var stack = new Stack();

// 验证栈是否为空
console.log(stack.isEmpty());

// 往栈中添加元素
stack.push(5);
stack.push(8);
stack.push(12);
stack.push(2);

// 查看栈顶元素
console.log(stack.peek());

// 查看栈中元素格式
console.log(stack.size());

// 再次检查栈是否为空
console.log(stack.isEmpty());

// 移除栈顶元素后再查看
stack.pop();
console.log(stack.peek());

// 查看栈内所有元素
stack.print();

利用栈解决十进制和二进制的转换问题:

要把十进制转化成二进制,我们可以将该十进制数字和2整除(二进制是满二进一),直到结果是0为止.举个例子,把十进制的数字10转化成二进制的数字,过程大概是这样:

2-10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function divideBy2(decNum){
  var remStack = new Stack(), rem, binaryString = '';

  while(decNum > 0){ // {1}
    rem = Math.floor(decNum % 2); // {2}
    remStack.push(rem); // {3}
    decNum = Math.floor(decNum / 2); // {4}
  }

  while(!remStack.isEmpty()){ // {5}
    binaryString += remStack.pop().toString();
  }

  return binaryString;
};

在这段代码中,当函数参数满足和2做整除的条件时(行{1}),我们会获得当前参数与2相除的余数,放到栈中(行{2}、{3}).然后让参数和2相除(行{4}).另外注意:JavaScript有数字类型,但是它不会区分究竟是整数还是浮点数.因此,要使用Math.floor函数让除法的操作仅返回整数部分.最后,用pop方法把栈中的元素都移除,把出栈的元素变成连接成字符串(行{5}).

修改以上算法, 把 十进制转换成任何进制:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function baseConverter(decNum, base){
  var remStack = new Stack(), rem, baseString = '';
  var digits = '0123456789ABCDEF'; //{6}

  while(decNum > 0){
    rem = Math.floor(decNum % base);
    remStack.push(rem);
    decNum = Math.floor(decNum / base);
  }

  while(!remStack.isEmpty()){
    baseString += digits[remStack.pop()]; //{7}
  }

  return baseString;

};

在将十进制转成二进制时,余数是0或1；在将十进制转成八进制时,余数是0到8之间的数；但是将十进制转成16进制时,余数是0到8之间的数字加上A、B、C、D、E和F(对应10、11、12、13、14和15).因此,需要对栈中的数字做转化.(行{6}和行{7}).

队列

队列和栈有很多相似之处,但有个重要区别,队列是遵循FIFO(First In First Out,先进先出,也称为先来先服务)原则的一组有序的项.队列在尾部添加新元素,并从顶部移除元素.最新添加的元素必须排在队列的末尾.

在现实中,最常见的队列的例子就是排队.

在计算机科学中,一个常见的例子就是打印队列.比如说我们需要打印五份文档.我们会打开每个文档,然后点击打印按钮.每个文档都会被发送至打印队列.第一个发送到打印队列的文档会首先被打印,以此类推,直到打印完所有文档.

队列的创建和使用

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

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

  // 移除队列的首位元素, 并返回被移除的元素
  this.dequeue = function(){
    return items.shift();
  };

  // 返回队列中首位元素(即最先被添加的元素), 不对队列做任何修改, 与栈的peek方法类似
  this.front = function(){
    return items[0];
  };

  // 如果队列中不包含任何元素, 返回true, 否则返回false
  this.isEmpty = function(){
    return items.length === 0;
  };

  this.clear = function(){
    items = [];
  };

  // 返回队列中包含元素个数
  this.size = function(){
    return items.length;
  };

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

// 实例化Queue类
var queue = new Queue();

// 验证是否为空
console.log(queue.isEmpty());

// 向末尾添加元素
queue.enqueue('John');
queue.enqueue('Jack');
queue.enqueue('Amy');

// 输出队列中所有元素
queue.print();

// 输出队列所含元素个数
console.log(queue.size());

// 移除首位元素
queue.dequeue();

// 查看队列最前元素
console.log(queue.front());

Queue类和Stack类非常类似.唯一的区别是dequeue方法和front方法,这是由于先进先出和后进先出原则的不同所造成的.

优先队列

默认队列有一些修改版本.其中一个修改版就是优先队列.元素的添加和移除是基于优先级的.

一个现实的例子就是机场登机的顺序.头等舱和商务舱乘客的优先级要高于经济舱乘客.另一个现实中的例子是医院的(急诊科)候诊室.医生会优先处理病情比较严重的患者.

实现一个优先队列,有两种选项:设置优先级,然后在正确的位置添加元素；或者用入列操作添加元素,然后按照优先级移除它们.在这个示例中,将会在正确的位置添加元素,因此可以对它们使用默认的出列操作:

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

  function QueueElement(element, priority){  // {1}
    this.element = element;
    this.priority = priority;
  };

  this.enqueue = function(element, priority){
    var queueElement = new QueueElement(element, priority);

    // 如果队列为空, 直接插入元素
    if(this.isEmpty()){
      items.push(queueElement);
    } else {
      // 设置added变量用以标识元素是否被插入队列
      var added = false;
      // 遍历队列, 比较待插入元素与队列内各个元素优先级
      for(var i=0; i<items.length; i++){
        if(queueElement.priority < items[i].priority){
          // 将待插入元素插入适当位置
          // 在本例情况下priority值大在后(以下用p值代替,p值小,优先级高)
          // 因此将待插入元素插入p值比其大的元素之前一位
          // 这样插入, 即使优先级相同, 也遵循先进先出原则
          items.splice(i, 0, queueElement);  
          // 当元素被顺利插入, 将added值改成true
          added = true;
          break; // 终止循环
        }
      }
      // 如果队列不为空, 而又没有元素被添加, 说明待插入元素p值最大, 直接插入末尾位置.
      if(!added){  
        items.push(queueElement);
      }
    }
  };

  // 其他方法和默认的Queue实现相同
}

默认的Queue类和PriorityQueue类实现上的区别是,要向PriorityQueue添加元素,需要创建一个特殊的元素(行{1}).这个元素包含了要添加到队列的元素(可以是任意类型)及其在队列中的优先级.

1
2
3
4
5
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("John", 2);
priorityQueue.enqueue("Jack", 1);
priorityQueue.enqueue("Camila", 1);
priorityQueue.print();

以上代码是一个使用PriorityQueue类的示例.在下图中可以看到每条命令的结果(以上代码的结果):

prior-queue

第一个被添加的元素是优先级为2的John.因为此前队列为空,所以它是队列中唯一的元素.接下来,添加了优先级为1的Jack.由于Jack的优先级高于John,它就成了队列中的第一个元素.然后,添加了优先级也为1的Camila.Camila的优先级和Jack相同,所以它会被插入到Jack之后(因为Jack先被插入队列)；Camila的优先级高于John,所以它会被插入到John之前.

我们在这里实现的优先队列称为最小优先队列,因为优先级的值较小的元素被放置在队列最前面(1代表更高的优先级).最大优先队列则与之相反,把优先级的值较大的元素放置在队列最前面.

循环队列

还有另一个修改版的队列实现,就是循环队列.循环队列的一个例子就是击鼓传花游戏(Hot Potato).在这个游戏中,孩子们围成一个圆圈,把花尽快地传递给旁边的人.某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈结束游戏.重复这个过程,直到只剩一个孩子(胜者).

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 hotPotato(nameList, num){
  var queue = new Queue(); // {1}

  for(var i=0; i<nameList.length; i++){
    queue.enqueue(nameList[i]); // {2}
  }

  var eliminated = '';
  while(queue.size() > 1){
    for(var i=0; i<num; i++){
      queue.enqueue(queue.dequeue()); // {3}
    }
    eliminated = queue.dequeue(); // {4}
    console.log(eliminated + '在击鼓传花游戏中被淘汰. ');
  }
  return queue.dequeue(); // {5}
}

var names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
var winner = hotPotato(names, 7);
console.log('胜利者: ' + winner);

// Camila在击鼓传花游戏中被淘汰.
// Jack在击鼓传花游戏中被淘汰.
// Carl在击鼓传花游戏中被淘汰.
// Ingrid在击鼓传花游戏中被淘汰.
// 胜利者: John

实现一个模拟的击鼓传花游戏,要用到这一章开头实现的Queue类(行{1}).我们会得到一份名单,把里面的名字全都加入队列(行{2}).给定一个数字,然后迭代队列.从队列开头移除一项,再将其添加到队列末尾(行{3}),模拟击鼓传花(如果你把花传给了旁边的人,你被淘汰的威胁立刻就解除了).一旦传递次数达到给定的数字,拿着花的那个人就被淘汰了(从队列中移除——行{4}).最后只剩下一个人的时候,这个人就是胜者(行{5}).

参考