javascript编程实现栈的方法详解【经典数据结构】

本文实例讲述了javascript编程实现栈的方法。分享给大家供大家参考,具体如下:

栈是限定仅在表尾进行插入或删除操作的线性表,栈是先进后出的。栈的表尾称为栈顶(top),而表头端称为栈底(bottom)。

和线性表类似,栈也有两种存储表示方法,顺序栈和链栈。

这里讲一下顺序栈,设置指针top指示栈顶元素在顺序栈中的位置。通常的做法就是以top=0表示空栈。base为栈底指针,top为栈顶指针。

如果base为null,则表示栈结构不存在,如果top=base则表示空栈。每当插入一个新的元素,top+1,删除元素,top-1。因此,非空栈中top始终在栈顶元素的下一位置上。

如下图所示

JavaScript中自带了数组的push和pop方法,其原理无非就是数组最后继续添加和删除数组最后一个元素。这里我们自己实现一遍栈的操作,代码如下:

<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8">
    <title>JS栈</title>
  </head>
  <body>
    <script type="text/javascript">
    function Stack(count){
      var top=-1;//top头指针
      this.myArray=new Array();
      if(count!=undefined){
        this.count=count;
        this.myArray=new Array(this.count);
      }else{
        this.count=0;
      }
      //入栈
      this.In=function(value){
        if(top==this.count){
          return false;
        }else{
          ++top;
          this.myArray[top]=value;
          return true;
        }
        return false;
      }
      //出栈
      this.Out=function(){
        if(top==-1){
          return false;
        }else{
          var removeValue=this.myArray[top];
          this.myArray[top]=null;
          top--;
          return removeValue;
        }
      }
      this.Clear=function(){
        this.top=-1;
      }
      //遍历栈
      this.tostring=function(){
        for(var i=0;i<this.myArray.length;i++){
          document.write(this.myArray[i]+'<br>');
        }
      }
    }
    Stack(3);
    In(1);
    In(2);
    In(3);
    tostring();//1 2 3
    Out();
    Out();
    tostring();//1 null null
    In(4);
    tostring();//1 4 null
    </script>
  </body>
</html>

首先需要定义头指针

function Stack(count){
 var top=-1;//top头指针
 this.myArray=new Array();
 if(count!=undefined){
  this.count=count;
  this.myArray=new Array(this.count);
 }else{
  this.count=0;
 }

然后是入栈操作

//入栈
this.In=function(value){
  if(top==this.count){
   return false;
  }else{
   ++top;
   this.myArray[top]=value;
   return true;
  }
  return false;
}

出栈操作

//出栈
this.Out=function(){
  if(top==-1){
   return false;
  }else{
   var removeValue=this.myArray[top];
   this.myArray[top]=null;
   top--;
   return removeValue;
  }
}

链栈的操作和链表类似,这里就不做详细介绍了。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题:《JavaScript数据结构与算法技巧总结》、《JavaScript数学运算用法总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》

希望本文所述对大家JavaScript程序设计有所帮助。

(0)

相关推荐

  • JavaScript数据结构之链表的实现

    前面楼主分别讨论了数据结构栈与队列的实现,当时所用的数据结构都是用的数组来进行实现,但是数组有的时候并不是最佳的数据结构,比如在数组中新增删除元素的时候需要将其他元素进行移动,而在javascript中使用spit()方法不需要访问其他元素.如果你在使用数组的时候发现很慢,就可以考虑使用链表. 链表的概念 链表是一种常见的数据结构.它是动态地进行存储分配的一种结构.链表有一个"头指针"变量,以head表示,它存放一个地址,指向一个元素.每个结点都使用一个对象的引用指标它的后继,指向另一

  • JavaScript数据结构之二叉查找树的定义与表示方法

    本文实例讲述了JavaScript数据结构之二叉查找树的定义与表示方法.分享给大家供大家参考,具体如下: 树是一种非线性的数据结构,以分层的方式存储数据.树被用来存储具有层级关系的数据,比如文件系统中的文件:树还被用来存储有序列表.这里将研究一种特殊的树:二叉树.选择树而不是那些基本的数据结构,是因为在二叉树上进行查找非常快(而在链表上查找则不是这样),为二叉树添加或删除元素也非常快(而对数组执行添加或删除操作则不是这样). 树是n个结点的有限集.最上面的为根,下面为根的子树.树的节点包含一个数

  • javascript数据结构之二叉搜索树实现方法

    本文实例讲述了javascript二叉搜索树实现方法.分享给大家供大家参考,具体如下: 二叉搜索树:顾名思义,树上每个节点最多只有二根分叉:而且左分叉节点的值 < 右分叉节点的值 . 特点:插入节点.找最大/最小节点.节点值排序 非常方便 二叉搜索树-javascript实现 <script type="text/javascript"> // <![CDATA[ //打印输出 function println(msg) { document.write(msg

  • JavaScript数据结构和算法之二叉树详解

    二叉树的概念 二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的.分别称为根结点的左子树和右子树的二叉树组成. 二叉树的特点 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点.二叉树中每一个节点都是一个对象,每一个数据节点都有三个指针,分别是指向父母.左孩子和右孩子的指针.每一个节点都是通过指针相互连接的.相连指针的关系都是父子关系. 二叉树节点的定义 二叉树节点定义如下: 复制代码 代码如下: struct

  • JS实现的二叉树算法完整实例

    本文实例讲述了JS实现的二叉树算法.分享给大家供大家参考,具体如下: <!DOCTYPE HTML> <head> <title>20130328BinaryTree</title> <metahttp-equiv="Content-Type" content="text/html; charset=utf-8" /> </head> <html> <body> <

  • JavaScript数据结构之数组的表示方法示例

    本文实例讲述了JavaScript数据结构之数组的表示方法.分享给大家供大家参考,具体如下: 数组类似于线性表.基本上每种语言都会讲数组作为固有类型.这里主要讲一下二维数组.我们可以把二维数组看成这样一个定长线性表:它的每个数据元素也是一个定长的线性表.数组一旦被定义,它的维数和维界就不再改变.因此,除了结构的初始化和销毁之外,数组只有存取元素和修改元素值的操作(这里注意和JavaScript中的array类型做出区分,这里说的是数据结构,而不是某一种单独语言的语法). 由于数组一般不作插入或者

  • javascript数据结构之串的概念与用法分析

    本文实例讲述了javascript数据结构之串的概念与用法.分享给大家供大家参考,具体如下: 串是由零个或多个字符组成的有限序列.串中字符的个数称为串的长度. 串中任意个连续的字符组成的子序列称为该串的子串.包含子串的串相应地称为主串.通常称字符在序列中的序号为该字符在串中的位置.子串的首字符在主串中首次出现的位置定义为子串在主串中的位置. 串的逻辑结构和线性表十分相似,区别仅仅在于串的数据对象约束为字符集.然而两者的基本操作有很大差别.线性表中,基本以单个元素来进行操作:而串中多半以串的整体也

  • JavaScript数据结构之广义表的定义与表示方法详解

    本文实例讲述了JavaScript数据结构之广义表的定义与表示方法.分享给大家供大家参考,具体如下: 广义表是线性表的推广,也有人称其为列表. 那么它和线性表有什么区别呢?线性表中每个成员只能是单个元素,而广义表中的成员可以是单个元素,也可以是广义表,分别称为广义表的原子和子表.下面举几个广义表的例子. A=(); B=(e); C=(a,(b,c,d)); D=((),(e),(a,(b,c,d))); E=(a,E); 由于广义表中的数据元素可以具有不同的结构(原子或列表),因此难以用顺序存

  • JS实现线性表的链式表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的链式表示方法.分享给大家供大家参考,具体如下: 从上一节可以,顺序存储结构的弱点就是在插入或删除操作时,需要移动大量元素.所以这里需要介绍一下链式存储结构,由于它不要求逻辑上相邻的元素在物理位置上也相邻,所以它没有顺序存储结构的弱点,但是也没有顺序表可随机存取的优点. 下面介绍一下什么是链表. 线性表的链式存储结构用一组任意的存储单元存储线性表的数据元素.所以,每一个数据元素除了存储自身的信息之外,还需要存储一个指向其后继的存储位置的信息.这两部分信息组成了元素的存

  • JS二叉树的简单实现方法示例

    本文实例讲述了JS二叉树的简单实现方法.分享给大家供大家参考,具体如下: 今天学习了一下 二叉树的实现,在此记录一下 简单的二叉树实现,并且实现升序和降序排序输出 function Node(data , left,right){ this.data = data; this.left = left; this.right = right; this.show = show; function show(){ return this.data; } }; function Bst(){ this

  • JS实现线性表的顺序表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的顺序表示方法.分享给大家供大家参考,具体如下: 线性表的顺序表示指的是用一组地址连接的存储单元依次存储线性表的数据元素.通常称这种存储结构的线性表为顺序表. 顺序表的特点是以元素在计算机内物理位置相邻来表示数据元素之间的逻辑关系.每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数.也就是说只要确定了存储线性表的起始位置,线性表中的任一元素都可以随机存储,所以说,顺序表是一种随机存取的存储结构. 高级语言中的数组与其相似,所以我

  • JS中的二叉树遍历详解

    二叉树是由根节点,左子树,右子树组成,左子树和友子树分别是一个二叉树. 这篇文章主要在JS中实现二叉树的遍历. 一个二叉树的例子 var tree = { value: 1, left: { value: 2, left: { value: 4 } }, right: { value: 3, left: { value: 5, left: { value: 7 }, right: { value: 8 } }, right: { value: 6 } } } 广度优先遍历 广度优先遍历是从二叉树

随机推荐