数据结构与算法-栈篇(js实现)
程序员文章站
2024-01-23 21:12:58
...
栈的特点:
- 栈内的元素只能通过列表的一端访问,这一端称为栈顶
- 先入后出。任何不在栈顶的元素都无法访问,为了得到栈底的元素,必须先拿掉上面的元素
现实生活中的栈:
咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞
在这一摞盘子的最上面。
栈的主要方法和属性:
- 入栈。push方法;
- 出栈。pop方法;
- 访问栈顶元素。peek方法;
- 清除所有栈内元素。clear方法;
- 记录栈顶位置。top属性;
- 判断栈内是否有元素存在。length方法;
栈的实现:
从定义一个stack构造函数开始
function Stack() { this.dataStore = [];//保存栈内元素 this.top = 0; }
对栈的各种操作
Stack.prototype={ push:function push(element) { this.dataStore[this.top++] = element;//添加一个元素并将top+1 }, peek:function peek() { return this.dataStore[this.top-1];//返回栈顶元素 }, pop:function pop() { return this.dataStore[--this.top];//返回栈顶元素并将top-1 }, clear:function clear() { this.top = 0;//将top归0 }, length:function length() { return this.top;//返回栈内的元素个数 } }
测试:
var lk=new Stack(); lk.push("likeke"); lk.push("zhangsan"); lk.push("wangwu"); lk.peek();//"wangwu" lk.length();3 lk.pop();//"wangwu" lk.peek();//"zhangsan" lk.clear(); lk.peek();//undefind lk.length();0
栈的使用:
1.十进制转换为2~9进制
function mulBase(num, base) { var s = new Stack(); do { s.push(num % base); num = Math.floor(num /= base); } while (num > 0); var converted = ""; while (s.length() > 0) { converted += s.pop(); } return converted; } mulBase(12,2);//"1100" mulBase(19,5);//"34" mulBase(19,3);//"201"
2.判断给定字符串是否是回文
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("likeke");//false isPalindrome("lkijikl");//true
3.计算任意数字的阶乘
//如果使用递归我们一般会这样写 function factorial(n) { if (n === 0) { return 1; } else { return n * factorial(n-1); } } //那么使用Stack类呢,如何来模拟这个递归过程 function fact(n) { var s = new Stack(); while (n > 1) { s.push(n--); } var product = 1; while (s.length() > 0) { product *= s.pop(); } return product; } factorial(5); // 120 fact(5); // 120
当然,如果只是想实现以上的进制转换以及判断回文的功能函数,我们可以有更简便的方法去实现它,此处只是为了说明此数据结构的特点使用了这些例子。
上一篇: 我的博客的搬迁工作第一步 Linux
下一篇: Java虚拟机是怎么new的对象?