`

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

阅读更多

栈的特点:

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

现实生活中的栈:

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

在这一摞盘子的最上面。

 

栈的主要方法和属性:

  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

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

    
 

 

 

分享到:
评论

相关推荐

    数据结构栈-括号匹配

    该源码在VS2010上,正确编译、运行,无任何错误和警告。

    JavaScript版 数据结构与算法

    第1章 课程导学对课程整体进行介绍,让您切实感受到前端工程师学习数据结构与算法的必要性。 1-1 课程导学 试看 1-2 学习姿势 1-3 说明与承诺第2章 基础算法之“字符串类”字符串作为JS最基本的数据类型,掌握好字符...

    JavaScript网页计算器-栈实现.html

    使用 JavaScript 写的网页版计算器。可以很好的完成加减乘除,但是并没有括号提供使用。内部实现的话,主要基于入栈出栈,与大学算法书中的简易计算器原理一致。

    JavaScript数据结构与算法之栈详解

    主要介绍了JavaScript数据结构与算法之栈详解,本文讲解了对栈的操作、对栈的实现实例等内容,需要的朋友可以参考下

    《数据结构与算法JavaScript描述》.zip

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

    《学习JavaScript数据结构与算法》.zip

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

    利用 JavaScript 来学数据结构和算法算法

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

    《数据结构与算法JavaScript描述》看书敲代码.zip

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

    从 0 到 1 学习 JavaScript 数据结构与算法.zip

    算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...

    01_Java版数据结构与算法 02_算法_直通BAT算法精讲

    数据结构1.pptx 2X1{SH5V_HSM`5JS[H]Z`JP.png 33XTI0U)]QTVK1MINJY0)F3.png 34MMEH64LMCA}H5G_RXKPGO.png 65]YTLJ{NP7ICB9{]%XK5J2.png 73I2ZJ(3Z5XWL3W1LFVZRCR.png MQJ[~8HPO2L{35`{CY8{WXO.png P)(%S5}WL7HD(09E1...

    《学习javascript数据结构与算法》一书中的代码.zip

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

    JavaScript讲解了数据结构和算法.zip

    算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...

    《Hello 算法》数据结构与算法教程,支持 Java, C++, Python, Go, JS, TS, C#

    算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...

    structureAndAlgorithm-JS:通过JavaScript来封装实现常见的数据结构与算法

    通过JavaScript来封装实现常见的数据结构与算法 介绍 收录了各种常见的数据结构与算法通过 JavaScript 来封装的代码,可以直接拿取使用 注意 现在暂未更新完,进度会随着本人CSDN博客上的文章进度而更新,欢迎大家...

    《Hello 算法》:动画图解、一键运行的数据结构与算法教程,支持 Java, C++, Python, Go, JS, TS等

    常见的数据结构有数组、链表、栈、队列、树、图等。 算法则是解决特定问题的步骤,是对数据运算和操作的详细描述。算法的设计和选择会直接影响到程序的效率,因此,在设计和选择算法时,需要考虑到时间复杂度、空间...

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

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

    JS数据结构与算法1

    顺序数据结构数组栈Stack后进先出(LIFO)队列Queue先进先出(FIFO)链表LinkedList存储有序的元素集合元素本身指针(链接):指向下一个元素

    数据结构与算法源码.zip

    多种语言包括java、python、c语言、go语言、php等来实现的数据结构的源码,包含数组、 链表、栈、队列、递归、排序、二分查找、散列表、二叉树、堆、图、回溯、分治、动态规划的实现方法。非常适合学习数据结构的小...

    用JavaScript实现的算法和数据结构,附详细解释和刷题指南.zip

    算法代码:我们提供了多种数据结构的实现代码,包括数组、链表、栈、队列、树、图等。这些代码不仅能帮助你理解数据结构的基本概念,而且能让你明白如何在实际情况中应用这些数据结构。 笔记:详细且系统的笔记,...

Global site tag (gtag.js) - Google Analytics