首页 > 编程 > JavaScript > 正文

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

2019-11-02 15:52:24
字体:
来源:转载
供稿:网友

   这篇文章主要介绍了JavaScript中数据结构与算法(一):栈,本文讲解了栈的结构、什么是回文以及递归等内容,讲解的不错,通俗易懂,需要的朋友可以参考下

  序

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

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

  栈结构

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

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

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

  实现一个栈的实现类

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

  因为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&qu

不带脏字的狠话[www.62-6.com/1/marenbaodian/]
ot;) //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);

  }

  }

  用栈操作

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表