欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法-栈篇(js实现)

程序员文章站 2024-01-23 21:28:58
...

栈的特点:

  • 栈内的元素只能通过列表的一端访问,这一端称为栈顶
  • 先入后出。任何不在栈顶的元素都无法访问,为了得到栈底的元素,必须先拿掉上面的元素

现实生活中的栈:

  咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子,盘子洗净后,也只能摞

在这一摞盘子的最上面。

 

栈的主要方法和属性:

  1. 入栈。push方法;
  2. 出栈。pop方法;
  3. 访问栈顶元素。peek方法;
  4. 清除所有栈内元素。clear方法;
  5. 记录栈顶位置。top属性;
  6. 判断栈内是否有元素存在。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

 当然,如果只是想实现以上的进制转换以及判断回文的功能函数,我们可以有更简便的方法去实现它,此处只是为了说明此数据结构的特点使用了这些例子。