1數(shù)組 1.1方法列表 數(shù)組的常用方法如下: concat: 鏈接兩個(gè)或者更多數(shù)據(jù)，并返回結(jié)果。 every: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定的函數(shù)，如果該函數(shù)對(duì)每一項(xiàng)都返回true，則返回true。 filter: 對(duì)數(shù)
1數(shù)組
1.1方法列表
數(shù)組的常用方法如下:

concat: 鏈接兩個(gè)或者更多數(shù)據(jù)，并返回結(jié)果。
every: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定的函數(shù)，如果該函數(shù)對(duì)每一項(xiàng)都返回true，則返回true。
filter: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定函數(shù)，返回改函數(shù)會(huì)返回true的項(xiàng)組成的數(shù)組。
forEach: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定函數(shù)，這個(gè)方法沒有返回值。
join: 將所有的數(shù)組元素鏈接成一個(gè)字符串。
indexOf: 返回第一個(gè)與給定參數(shù)相等的數(shù)組元素的索引，沒有找到則返回-1。
lastIndexOf: 返回在數(shù)組中搜索到的與給定參數(shù)相等的元素的索引里最大的值。
map: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定函數(shù)，返回每次函數(shù)調(diào)用的結(jié)果組成的數(shù)組。
reverse: 顛倒數(shù)組中元素的順序，原先第一個(gè)元素現(xiàn)在變成最后一個(gè)，同樣原先的最后一個(gè)元素變成現(xiàn)在的第一個(gè)。
slice: 傳入索引值，將數(shù)組中對(duì)應(yīng)索引范圍內(nèi)的元素作為新元素返回。
some: 對(duì)數(shù)組中的每一項(xiàng)運(yùn)行給定函數(shù)，如果任一項(xiàng)返回true，則返回true。
sort: 按照字母順序?qū)?shù)組排序，支持傳入指定排序方法的函數(shù)作為參數(shù)。
toString: 將數(shù)組作為字符串返回。
valueOf: 和toString相似，將數(shù)組作為字符串返回。
1.2數(shù)組合并
concat方法可以向一個(gè)數(shù)組傳遞數(shù)組、對(duì)象或是元素。數(shù)組會(huì)按照該方法傳入的參數(shù)順序 連接指定數(shù)組。

var zero = 0;
var positiveNumbers = [1,2,3];
var negativeNumbers = [-1,-2,-3];
var numbers = negativeNumbers.concat(zero,positiveNumbers);
console.log(numbers);//輸出結(jié)果： [-1, -2, -3, 0, 1, 2, 3]

1.3迭代器函數(shù)
reduce方法接收一個(gè)函數(shù)作為參數(shù),這個(gè)函數(shù)有四個(gè)參數(shù):previousValue、currentValue、index和array。這個(gè)函數(shù)會(huì)返回一個(gè)將被疊加到累加器的 值,reduce方法停止執(zhí)行后會(huì)返回這個(gè)累加器。如果要對(duì)一個(gè)數(shù)組中的所有元素求和,這就很有用了。

var isEven = function(x){
  return (x%2 == 0)?true:false;
}
var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
//every方法會(huì)迭代數(shù)組中的每個(gè)元素,直到返回false。
var result = numbers.every(isEven);
console.log(result);//false
//some方法會(huì)迭代數(shù)組的每個(gè)元 素,直到函數(shù)返回true.
result = numbers.some(isEven);
console.log(result);//true
//forEach對(duì)每一項(xiàng)運(yùn)行給定的函數(shù)，沒有返回值
numbers.forEach(function(item,index){
  console.log(item%2 == 0);
});
//map會(huì)迭代數(shù)組中的每個(gè)值，并且返回迭代結(jié)果
var myMap = numbers.map(isEven);
console.log(myMap);// [false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]
//filter方法返回的新數(shù)組由使函數(shù)返回true的元素組成
var myFilter = numbers.filter(isEven);
console.log(myFilter);// [2, 4, 6, 8, 10, 12, 14]
//reduct函數(shù)
var myReduce = numbers.reduce(function(previous,current,index){
  return previous + "" + current;
});
console.log(myReduce);//123456789101112131415

1.4排序
var numbers = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
numbers.reverse();//[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
function compare(a,b){
if(a > b){
return 1;
}
if(a < b){
return -1;
}
return 0;
}
//sort函數(shù)使用
[1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9].sort(compare);

var friends = [{
  name:'huang',
  age:30
},{
  name:'chengdu',
  age:27
},{
  name:'du',
  age:31
}];
function comparePerson(a,b){
  if(a.age > b.age){
    return 1;
  }
  if(a.age < b.age){
    return -1;
  }
  return 0;
}
console.log(friends.sort(comparePerson));// [Object { name="chengdu",  age=27}, Object { name="huang",  age=30}, Object { name="du",  age=31}]
//搜索
numbers.push(10);
console.log(numbers.indexOf(10));//5
console.log(numbers.lastIndexOf(10));//15
var numbersString = numbers.join('-');
console.log(numbersString);//15-14-13-12-11-10-9-8-7-6-5-4-3-2-1-10

2棧
2.1棧的創(chuàng)建
對(duì)于一個(gè)棧，我們需要實(shí)現(xiàn)添加、刪除元素、獲取棧頂元素、已經(jīng)是否為空，棧的長(zhǎng)度、清除元素等幾個(gè)基本操作。下面是基本定義。

function Stack(){
  this.items = [];
}
Stack.prototype = {
  constructor:Stack,
  push:function(element){
    this.items.push(element);
  },
  pop:function(){
    return this.items.pop();
  },
  peek:function(){
    return this.items[this.items.length - 1];
  },
  isEmpty:function(){
    return this.items.length == 0;
  },
  clear:function(){
    this.items = [];
  },
  size:function(){
    return this.items.length;
  },
  print:function(){
    console.log(this.items.toString());
  }
}

2.2棧的基本使用
棧的基本操作。

var stack = new Stack();
console.log(stack.isEmpty());//true
stack.push(5);
stack.push(8);
console.log(stack.peek());//8
stack.push(11);
console.log(stack.size());//3
console.log(stack.isEmpty());
stack.push(15);
stack.pop();
stack.pop();
console.log(stack.size());//2
console.log(stack.print());//5,8

通過棧實(shí)現(xiàn)對(duì)正整數(shù)的二進(jìn)制轉(zhuǎn)換。

function divideBy2(decNumber){
  var decStack = new Stack();
  var rem;
  var decString = '';
  while(decNumber > 0){
    rem = decNumber%2;
    decStack.push(rem);
    decNumber = Math.floor(decNumber/2);
  }
  while(!decStack.isEmpty()){
    decString += decStack.pop().toString();
  }
  return decString;
}
console.log(divideBy2(10));//1010

3隊(duì)列
3.1隊(duì)列的創(chuàng)建
隊(duì)列是遵循FIFO(First In First Out,先進(jìn)先出,也稱為先來先服務(wù))原則的一組有序的項(xiàng)。隊(duì)列在尾部添加新元素,并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾。隊(duì)列要實(shí)現(xiàn)的操作基本和棧一樣，只不過棧是FILO(先進(jìn)后出)。

function Queue(){
  this.items = [];
}
Queue.prototype = {
  constructor:Queue,
  enqueue:function(elements){
    this.items.push(elements);
  },
  dequeue:function(){
    return this.items.shift();
  },
  front:function(){
    return this.items[0];
  },
  isEmpty:function(){
    return this.items.length == 0;
  },
  size:function(){
    return this.items.length;
  },
  clear:function(){
    this.items = [];
  },
  print:function(){
    console.log(this.items.toString());
  }
}

隊(duì)列的基本使用

var queue = new Queue();
console.log(queue.isEmpty());//true
queue.enqueue('huang');
queue.enqueue('cheng');
console.log(queue.print());//huang,cheng
console.log(queue.size());//2
console.log(queue.isEmpty());//false
queue.enqueue('du');
console.log(queue.dequeue());//huang
console.log(queue.print());//cheng,du

3.2 優(yōu)先隊(duì)列
元素的添加和移除是基于優(yōu)先級(jí)的。實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列,有兩種選項(xiàng):設(shè)置優(yōu)先級(jí),然后在正確的位置添加元素;或者用入列操 作添加元素,然后按照優(yōu)先級(jí)移除它們。 我們?cè)谶@里實(shí)現(xiàn)的優(yōu)先隊(duì)列稱為最小優(yōu)先隊(duì)列,因?yàn)閮?yōu)先級(jí)的值較小的元素被放置在隊(duì)列最 前面(1代表更高的優(yōu)先級(jí))。最大優(yōu)先隊(duì)列則與之相反,把優(yōu)先級(jí)的值較大的元素放置在隊(duì)列最 前面。

3.2.1 優(yōu)先隊(duì)列的定義
我們?cè)谶@里使用組合繼承的方式繼承自Queue隊(duì)列。

function PriorityQueue(){
  Queue.call(this);
};
PriorityQueue.prototype = new Queue();
PriorityQueue.prototype.constructer = PriorityQueue;
PriorityQueue.prototype.enqueue = function(element,priority){
  function QueueElement(tempelement,temppriority){
    this.element = tempelement;
    this.priority = temppriority;
  }
  var queueElement = new QueueElement(element,priority);
  if(this.isEmpty()){
    this.items.push(queueElement);
  }else{
    var added = false;
    for(var i = 0; i < this.items.length;i++){
      if(this.items[i].priority > queueElement.priority){
        this.items.splice(i,0,queueElement);
        added = true;
        break;
      }
    }
    if(!added){
        this.items.push(queueElement);
    }
  }
  
}
//這個(gè)方法可以用Queue的默認(rèn)實(shí)現(xiàn)
PriorityQueue.prototype.print = function(){
  var result ='';
  for(var i = 0; i < this.items.length;i++){
    result += JSON.stringify(this.items[i]);
  }
  return result;
}

3.2.1 優(yōu)先隊(duì)列的基本使用
var priorityQueue = new PriorityQueue();
priorityQueue.enqueue("cheng", 2);
priorityQueue.enqueue("du", 3);
priorityQueue.enqueue("huang", 1);
console.log(priorityQueue.print());//{"element":"huang","priority":1}{"element":"cheng","priority":2}{"element":"du","priority":3}
console.log(priorityQueue.size());//3
console.log(priorityQueue.dequeue());//{ element="huang", priority=1}
console.log(priorityQueue.size());//2
3鏈表
數(shù)組的大小是固定的,從數(shù)組的起點(diǎn)或中間插入 或移除項(xiàng)的成本很高,因?yàn)樾枰苿?dòng)元素(盡管我們已經(jīng)學(xué)過的JavaScript的Array類方法可以幫 我們做這些事,但背后的情況同樣是這樣)。鏈表存儲(chǔ)有序的元素集合,但不同于數(shù)組,鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè) 元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用(也稱指針或鏈接)組成。

相對(duì)于傳統(tǒng)的數(shù)組,鏈表的一個(gè)好處在于,添加或移除元素的時(shí)候不需要移動(dòng)其他元素。然 而,鏈表需要使用指針,因此實(shí)現(xiàn)鏈表時(shí)需要額外注意。數(shù)組的另一個(gè)細(xì)節(jié)是可以直接訪問任何 位置的任何元素,而要想訪問鏈表中間的一個(gè)元素,需要從起點(diǎn)(表頭)開始迭代列表直到找到 所需的元素

3.1.1鏈表的創(chuàng)建
我們使用動(dòng)態(tài)原型模式來創(chuàng)建一個(gè)鏈表。列表最后一個(gè)節(jié)點(diǎn)的下一個(gè)元素始終是null。

function LinkedList(){
  function Node(element){
    this.element = element;
    this.next = null;
  }
  this.head = null;
  this.length = 0;
  //通過對(duì)一個(gè)方法append判斷就可以知道是否設(shè)置了prototype
  if((typeof this.append !== 'function')&&(typeof this.append !== 'string')){
    //添加元素
    LinkedList.prototype.append = function(element){
      var node = new Node(element);
      var current;
      if(this.head === null){
        this.head = node;
      }else{
        current = this.head;
        while(current.next !== null){
          current = current.next;
        }
        current.next = node;
      }
      this.length++;
    };
    //插入元素，成功true，失敗false
    LinkedList.prototype.insert = function(position,element){
      if(position > -1 && position < this.length){
        var current = this.head;
        var previous;
        var index = 0;
        var node = new Node(element);
        if(position == 0){
          node.next = current;
          this.head = node;
        }else{
          while(index++ < position){
            previous = current;
            current = current.next;
          }
          node.next = current;
          previous.next = node;
        }
        this.length++;
        return true;
      }else{
        return false;
      }
    };
    //根據(jù)位置刪除指定元素，成功 返回元素， 失敗 返回null
    LinkedList.prototype.removeAt = function(position){
      if(position > -1 && position < this.length){
        var current = this.head;
        var previous = null;
        var index = 0;
        if(position == 0){
          this.head = current.next;
        }else{
          while(index++ < position){
            previous = current;
            current = current.next;
          }
          previous.next = current.next;
        }
        this.length--;
        return current.element;
      }else{
        return null;
      }
    };
    //根據(jù)元素刪除指定元素，成功 返回元素， 失敗 返回null
    LinkedList.prototype.remove = function(element){
      var index = this.indexOf(element);
      return this.removeAt(index);
    };
    //返回給定元素的索引，如果沒有則返回-1
    LinkedList.prototype.indexOf = function(element){
      var current = this.head;
      var index = 0;
      while(current){
        if(current.element === element){
          return index;
        }
        index++;
        current = current.next;
      }
      return -1;
    };
    LinkedList.prototype.isEmpty = function(){
      return this.length === 0;
    };
    LinkedList.prototype.size = function(){
      return this.length;
    };
    LinkedList.prototype.toString = function(){
        var string = '';
        var current = this.head;
        while(current){
          string += current.element;
          current = current.next;
        }
        return string;
    };
    LinkedList.prototype.getHead = function(){
      return this.head;
    };
  }
}

3.1.2鏈表的基本使用
var linkedList = new LinkedList();
console.log(linkedList.isEmpty());//true;
linkedList.append('huang');
linkedList.append('du')
linkedList.insert(1,'cheng');
console.log(linkedList.toString());//huangchengdu
console.log(linkedList.indexOf('du'));//2
console.log(linkedList.size());//3
console.log(linkedList.removeAt(2));//du
console.log(linkedList.toString());//huangcheng
3.2.1雙向鏈表的創(chuàng)建
鏈表有多種不同的類型,這一節(jié)介紹雙向鏈表。雙向鏈表和普通鏈表的區(qū)別在于,在鏈表中, 一個(gè)節(jié)點(diǎn)只有鏈向下一個(gè)節(jié)點(diǎn)的鏈接,而在雙向鏈表中,鏈接是雙向的:一個(gè)鏈向下一個(gè)元素, 另一個(gè)鏈向前一個(gè)元素。

雙向鏈表和鏈表的區(qū)別就是有一個(gè)tail屬性，所以必須重寫insert、append、removeAt方法。每個(gè)節(jié)點(diǎn)對(duì)應(yīng)的Node也多了一個(gè)prev屬性。

//寄生組合式繼承實(shí)現(xiàn)，詳見javascript高級(jí)程序設(shè)計(jì)第七章
function inheritPrototype(subType, superType) {
function object(o) {
function F() {}
F.prototype = o;
return new F();
}
var prototype = object(superType.prototype);
prototype.constructor = subType;
subType.prototype = prototype;
}
function DoublyLinkedList() {
function Node(element) {
this.element = element;
this.next = null;
this.prev = null;
}
this.tail = null;
LinkedList.call(this);
//與LinkedList不同的方法自己實(shí)現(xiàn)。
this.insert = function(position, element) {
if (position > -1 && position <= this.length) {
var node = new Node(element);
var current = this.head;
var previous;
var index = 0;
if (position === 0) {
if (!this.head) {
this.head = node;
this.tail = node;
} else {
node.next = current;
current.prev = node;
this.head = node;
}
} else if (position == this.length) {
current = this.tail;
current.next = node;
node.prev = current;
this.tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
current.prev = node;
node.prev = previous;
}
this.length++;
return true;
} else {
return false;
}
};
this.append = function(element) {
var node = new Node(element);
var current;
if (this.head === null) {
this.head = node;
this.tail = node;
} else {
current = this.head;
while (current.next !== null) {
current = current.next;
}
current.next = node;
node.prev = current;
this.tail = node;
}
this.length++;
};
this.removeAt = function(position) {
if (position > -1 && position < this.length) {
var current = this.head;
var previous;
var index = 0;
if (position === 0) {
this.head = current.next;
if (this.length === 1) {
this.tail = null;
} else {
this.head.prev = null;
}
} else if (position === (this.length - 1)) {
current = this.tail;
this.tail = current.prev;
this.tail.next = null;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
this.length--;
return current.element;
} else {
return false;
}
};
}
inheritPrototype(DoublyLinkedList, LinkedList);
3.2.2雙向鏈表的基本使用
var doublyList = new DoublyLinkedList();
console.log(doublyList.isEmpty()); //true;
doublyList.append('huang');
doublyList.append('du')
doublyList.insert(1, 'cheng');
console.log(doublyList.toString()); //huangchengdu
console.log(doublyList.indexOf('du')); //2
console.log(doublyList.size()); //3
console.log(doublyList.removeAt(2)); //du
console.log(doublyList.toString()); //huangcheng
3.2.3 循環(huán)鏈表
循環(huán)鏈表可以像鏈表一樣只有單向引用,也可以像雙向鏈表一樣有雙向引用。循環(huán)鏈表和鏈 表之間唯一的區(qū)別在于,最后一個(gè)元素指向下一個(gè)元素的指針(tail.next)不是引用null, 而是指向第一個(gè)元素(head)。雙向循環(huán)鏈表有指向head元素的tail.next,和指向tail元素的head.prev。
JavaScript中的“閉包”是什么？請(qǐng)舉一個(gè)例子。
閉包是一個(gè)可以訪問外部（封閉）函數(shù)作用域鏈中的變量的內(nèi)部函數(shù)。閉包可以訪問三種范圍中的變量：這三個(gè)范圍具體為：（1）自己范圍內(nèi)的變量，（2）封閉函數(shù)范圍內(nèi)的變量，以及（3）全局變量。
下面是一個(gè)簡(jiǎn)單的例子：

  var globalVar = "xyz";

  (function outerFunc(outerArg) {
  var outerVar = 'a';

  (function innerFunc(innerArg) {
   var innerVar = 'b';

  console.log(
  "outerArg = " + outerArg + "\n" +
  "innerArg = " + innerArg + "\n" +
  "outerVar = " + outerVar + "\n" +
  "innerVar = " + innerVar + "\n" +
  "globalVar = " + globalVar);

  })(456);
  })(123);

在上面的例子中，來自于 innerFunc， outerFunc和全局命名空間的變量都在 innerFunc的范圍內(nèi)。因此，上面的代碼將輸出如下：

outerArg = 123
innerArg = 456
outerVar = a
innerVar = b
globalVar = xyz