DIV CSS 佈局教程網

JavaScript 資料結構與算法之棧與佇列
編輯:JavaScript基礎知識     

學習起因

曾經在逛論壇時看到一個帖子:數學完全還給老師了,想學回一些基礎數學,有什麼書籍推薦?發帖的樓主大學沒有高數課程,一直從事前端工作,感覺到知識的匱乏。看著這個帖子,我感覺和自己很像——我的專業不開高數,學的也是前端,也同樣感受到數學知識匱乏所帶來的困頓。當時也有人說「前端需要什麼資料結構與算法」,但我並不這麼認為。在我看來,前端具備扎實的計算機基礎,對自身發展極為有利。於是開始了資料結構與算法的初步學習。

JavaScript 之陣列操作

接下來是資料結構的第一部分:棧。棧是一種遵從「後進先出」(LIFO,Last In First Out)原則的有序集合,棧頂永遠是最新的元素。舉個例子:棧就像放在箱子裡的一疊書,你要拿下面的書,得先把上面的書拿開。

JavaScript 中棧的實現

首先建立構造函式,用陣列來模擬棧:

function Stack() {
  var item = [];
}

棧需要具備 push、pop、peek、isEmpty、clear、size、print 等方法。

push 方法:往棧中添加新元素,位置在陣列末尾,可用陣列的 push 模擬:

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

pop 方法:把棧頂元素彈出並返回:

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

peek 方法:查看棧頂元素,可用陣列長度實現:

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

其餘方法:

this.isAmpty = function() {
  return items.length === 0;
};
this.clear = function() {
  items = [];
};
this.size = function() {
  return items.length;
};
this.print = function() {
  console.log(items.toString());
};

實際應用:書中有個十進位轉二進位的函式,原理是輸入要轉換的數字,不斷除以二並取整,最後用 while 循環把棧中所有數字拼接成字串輸出。

function divideBy2(decNumber) {
  var remStack = new Stack(), rem, binaryString = '';
  while (decNumber > 0) {
    rem = Math.floor(decNumber % 2);
    remStack.push(rem);
    decNumber = Math.floor(decNumber / 2);
  }
  while (!remStack.isAmpty()) {
    binaryString += remStack.pop().toString();
  }
  return binaryString;
};

佇列

佇列與棧很相像,不同之處在於佇列是「先進先出」(FIFO,First In First Out)的。舉個例子:火車站排隊買票,先到的先買(插隊的不算)。

首先建立構造函式:

function Queue() {
  var items = [];
}

enqueue 方法:向佇列尾部添加元素:

this.enqueue = function(ele) {
  items.push(ele);
};

dequeue 方法:移除佇列的第一項:

this.dequeue = function() {
  return items.shift();
};

front 方法:返回佇列的第一個元素:

this.front = function() {
  return items[0];
};

實際應用:書上是個「擊鼓傳花」的小遊戲,原理是循環到相應位置時把該元素彈出,最後留下的就是贏家:

function hotPotato(nameList, num) {
  var queue = new Queue();
  for (var i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i]);
  }
  var eliminated = '';
  while (queue.size() > 1) {
    for (var i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue());
    }
    eliminated = queue.dequeue();
    console.log(eliminated + " Get out!")
  }
  return queue.dequeue()
}

感想

很多時候直接看算法導論或資料結構的書都會很迷糊,後來才發現,從自己能看懂的開始、由淺入深,才是適合自己的學習方式。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved