萬盛學電腦網

 萬盛學電腦網 >> 腳本專題 >> javascript >> JavaScript中數據結構與算法(一):棧

JavaScript中數據結構與算法(一):棧

   這篇文章主要介紹了JavaScript中數據結構與算法(一):棧,本文講解了棧的結構、什麼是回文以及遞歸等內容,講解的不錯,通俗易懂,需要的朋友可以參考下

  序

  數據結構與算法JavaScript這本書算是講解得比較淺顯的,優點就是用javascript語言把常用的數據結構給描述了下,書中很多例子來源於常見的一些面試題目,算是與時俱進,業余看了下就順便記錄下來吧

  git代碼下載:https://github.com/JsAaron/data_structure.git

  棧結構

  特殊的列表,棧內的元素只能通過列表的一端訪問,棧頂

  後入先出(LIFO,last-in-first-out)的數據結構

  javascript提供可操作的方法, 入棧 push, 出棧 pop,但是pop會移掉棧中的數據

  實現一個棧的實現類

  底層存數數據結構采用 數組

  因為pop是刪除棧中數據,所以需要實現一個查找方法 peek

  實現一個清理方法 clear

  棧內元素總量查找 length

  查找是否還存在元素 empty

  代碼如下:

  function Stack(){

  this.dataStore = []

  this.top = 0;

  this.push = push

  this.pop = pop

  this.peek = peek

  this.length = length;

  }

  function push(element){

  this.dataStore[this.top++] = element;

  }

  function peek(element){

  return this.dataStore[this.top-1];

  }

  function pop(){

  return this.dataStore[--this.top];

  }

  function clear(){

  this.top = 0

  }

  function length(){

  return this.top

  }

  回文

  回文就是指一個單詞,數組,短語,從前往後從後往前都是一樣的 12321.abcba

  回文最簡單的思路就是, 把元素反轉後如果與原始的元素相等,那麼就意味著這就是一個回文了

  這裡可以用到這個棧類來操作

   代碼如下:

  function isPalindrome(word) {

  var s = new Stack()

  for (var i = 0; i < word.length; i++) {

  s.push(word[i])

  }

  var rword = "";

  while (s.length() > 0) {

  rword += s.pop();

  }

  if (word == rword) {

  return true;

  } else {

  return false;

  }

  }

  isPalindrome("aarra") //false

  isPalindrome("aaraa") //true

  看看這個isPalindrome函數,其實就是通過調用Stack類,然後把傳遞進來的word這個元素給分解後的每一個組成單元給壓入到棧了,根據棧的原理,後入先出的原則,通過pop的方法在反組裝這個元素,最後比較下之前與組裝後的,如果相等就是回文了

  遞歸

  用遞歸實現一個階乘算法

  5! = 5 * 4 * 3 * 2 * 1 = 120

  用遞歸

   代碼如下:

  function factorial(n) {

  if (n === 0) {

  return 1;

  } else {

  return n * factorial(n - 1);

  }

  }

  用棧操作

   代碼如下:

  function fact(n) {

  var s = new Stack()

  while (n > 1) {

  //[5,4,3,2]

  s.push(n--);

  }

  var product = 1;

  while (s.length() > 0) {

  product *= s.pop();

  }

  return product;

  }

  fact(5) //120

  通過while把n = 5 遞減壓入棧,然後再通過一個循環還是根據棧的後入先出的原則,通過pop方法把最前面的取出來與product疊加

copyright © 萬盛學電腦網 all rights reserved