数据结构与算法JavaScript (一) 栈


数据结构与算法JavaScript这本书算是讲解得比较浅显的,优点就是用javascript语言把常用的数据结构给描述了下,书中很多例子来源于常见的一些面试题目,算是与时俱进,业余看了下就顺便记录下来吧

git代码下载:https://github.com/JsAaron/data_structure.git

 

栈结构

特殊的列表,栈内的元素只能通过列表的一端访问,栈顶

后入先出(LIFO,last-in-first-out)的数据结构

 

javascript提供可操作的方法, 入栈 push, 出栈 pop,但是pop会移掉栈中的数据

数据结构与算法JavaScript (一) 栈

实现一个栈的实现类

底层存数数据结构采用 数组

因为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叠加


发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>