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

页面导航:首页 > 网络编程 > JavaScript > 数据结构与算法JavaScript (一) 栈

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

来源: 作者: 时间:2016-02-04 09:15 【

栈结构特殊的列表,栈内的元素只能通过列表的一端访问,栈顶后入先出(LIFO,last-in-first-out)的数据结构javascript提供可操作的方法, 入栈 push, 出栈 pop,但是pop会移掉栈中的数据image_thumb
栈结构
 
特殊的列表,栈内的元素只能通过列表的一端访问,栈顶
 
后入先出(LIFO,last-in-first-out)的数据结构
 
 
 
javascript提供可操作的方法, 入栈 push, 出栈 pop,但是pop会移掉栈中的数据
 
image_thumb2
 
实现一个栈的实现类
 
底层存数数据结构采用 数组
 
因为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叠加
 
Tags:

文章评论

最 近 更 新
热 点 排 行
Js与CSS工具
代码转换工具

<