你的位置:首页 > Java教程

[Java教程]用JS描述的数据结构及算法表示——栈和队列(基础版)


前言:找了上课时数据结构的教程来看,但是用的语言是c++,所以具体实现在网上搜大神的博客来看,我看到的大神们的博客都写得特别好,不止讲了最基本的思想和算法实现,更多的是侧重于实例运用,一边看一边在心里隐隐歌颂大神的厉害,然后别人的厉害不是我的,所以到底看得各种受打击+头昏脑涨,写这个系列是希望自己能够总结学到东一块、西一下的知识,因为水平有限+经验不足,所以在此只说最基础的思想,附上我自己的算法实现(肯定还有更优解),如果要想看进阶版的,可以在园里搜“数据结构”,各种语言实现和进阶提升的文章有很多,希望大家都能尽快打败数据结构这个纸老虎~

参考书是:数据结构(c++版)(第2版) 编者:王红梅、胡明、王涛

正文:

热身准备:

1、根据数据元素之间的不同关系,数据结构可以分为以下四种:

  (1)集合:数据元素之间的关系就是“属于同一集合”,除此之外,没有其他关系。(此关系过于简单,就不详述了)

  (2)线性结构:数据元素之间存在“一对一”的线性关系。

  (3)树结构:数据元素之间存在“一对多”的层级关系。

  (4)图结构:数据元素之间存在“多对多”的任意关系。

2、数据结构在计算机中的存储方式,主要有两种:顺序存储和链接存储。

3、线性结构在计算机中的实现,即线性表。当然根据存储方式的不同又可以分为:顺序表和链表。

  (1)顺序表:用一段地址连续的存储单元依次存储线性表的数据元素。通常用一维数组来实现。其数据元素间的关系由下标表现。

  (2)链表:最常见的是单链表。单链表是用一组任意的存储单元存放数据元素。其数据元素间的关系由指针表现。除去单链表外,常见的还有循环链表和双链表,都是在单链表的基础上增加了更多信  息,便于实现某些操作。

 

开始运动:

栈和队列都是某些功能受限制的线性表,所以它们有线性表的基本性质,但是更特别,也正是它们的特别之处才使得它们脱颖而出。

栈:限定仅在表尾进行插入和删除操作的线性表,允许插入和删除的一端成为栈顶,另一端称为栈底,不含任何元素的栈称为空栈。

  栈具有FILO(first in last out)即先进后出的特性。

1、栈的基本操作:

push

  前置条件:栈已存在

  输入:元素值x

  功能:入栈操作,在栈顶插入一个元素x

  输出:如果插入不成功,则抛出异常

  后置条件:如果插入成功,则栈顶增加一个元素

pop

  前置条件:栈已存在

  输入:无

  功能:出栈操作,删除栈顶元素

  输出:如果删除成功,返回被删除元素,否则抛出异常

  后置条件:如果删除成功,则栈顶减少一个元素

getTop

  前置条件:栈已存在

  输入:无

  功能:取栈顶元素,读取当前的栈顶元素

  输出:如栈不空,返回当前的栈顶元素

  后置条件:栈不变

2、顺序栈

function SeqStack(){  this._stack = []; //栈  this._top = -1;  //栈顶指针}SeqStack.prototype = {  _push:function(x){
    try{ this._stack.push(x); this._top++;
    }catch(e){
     console.log("压栈失败");
    } }, _pop:function(){ if(this._top == -1) throw Error("栈空"); this._top--; return this._stack.pop(); }, _getTop:function(){ if(this._top == -1) return "空栈"; return this._stack[this._top]; }};var s = new SeqStack();s._push(1);s._push(2);s._push(3);console.log(s._getTop());//输出3s._pop();console.log(s._getTop());//输出2s._pop();s._pop();console.log(s._getTop());//输出空栈s._pop();//抛出异常

特别要说:

(1)因为js是一门非常优秀的语言,(哈哈,没有打广告,只是日常告白),js已经实现了push,pop的操作,所以此处捡了个便宜,只是对于获取栈顶(getTop)增加了实现。之所以在每个方法和属性前加了下划线,是因为看不惯sublime特别标注出来的颜色(感觉像是用了保留字一样),所以如果你看不惯_完全可以不要_。

(2)因为js中的数组是可以自己随着元素插入而增长的(如果大于你原本预计的长度),所以没有设置maxSize,如果希望栈是定长的,可以再添加maxSize属性。

(3)因为js不是强数据类型,所以如果需要栈做更实际化的操作可能会出现元素值x为特定值,没关系,加判断就好咯,交给你来,未来的灵魂程序猿(这什么中二的称呼)

3、链栈

function LinkStack(){  this._top = null;}LinkStack.prototype = {  _push:function(x){
    try{ var node = {_data:x,_next:null};//至少含有此处两属性 node._next = this._top;//当前和下一句不能互换,否则不能实现 this._top = node;
    }catch(e){
     console.log("压栈失败");
    } }, _pop:function(){ if(this._top == null) throw Error("栈空"); var node = this._top; this._top = node._next; return node; }, _getTop:function(){ if(this._top == null) return "空栈"; return this._top._data; }};var s = new LinkStack();s._push(1);s._push(2);s._push(3);console.log(s._getTop());console.log(s._pop());console.log(s._getTop());console.log(s._pop());console.log(s._pop());console.log(s._getTop());s._pop();

特别要说:

(1)链栈如果要求长度的话,会需要遍历整个栈才能计算(顺序栈基于数组有一个length属性可以获得长度),所以如果在求长度很常用的情况下,可以再增加一个自定义的length属性,每次_push时,获取当前top的length值,加1后赋值给新增node的length属性,则获取链栈的长度就很容易了。

(2)因为压入的node定义为了一个对象,所以_top初始化时用了null,非常明确的表明了之后压入的node会是对象,同时判断栈空时也很明确。建议使用这样的方法初始化_top

栈先告一段落,继续来说队列。

队列:只允许在一端进行插入,在另一端进行删除的线性表。允许插入(也称入队、进队)的一端称为队尾,允许删除(也称出队)的一端称为队头。

  队列具有FIFO(first in first out)先进先出的特性。(想想栈呢?)

1、队列的基本操作:

enQueue

  前置条件:队列已存在

  输入:元素值x

  功能:入队操作,在队尾插入一个元素

  输出:如果插入不成功,抛出异常

  后置条件:如果插入成功,队尾增加一个元素

deQueue

  前置条件:队列已存在

  输入: 无

  功能:出队操作,删除队头元素

  输出:如果删除成功,返回被删除元素值,否则,抛出异常

  后置条件:如果删除成功,队头减少一个元素

getQueue

  前置条件:队列已存在

  输入:无

  功能:读取队头元素

  输出:若队列不可,返回队头元素

  后置条件:队列不变

2、循环队列

高能警报 队列这里有个坑,如果是在数组需要预先确定长度的环境里(如使用c++声明数组,需要预先确实数组长度),当我入队5个元素,又出队5个元素,继续入队出队,总有一个时刻,我的队头指针会到达数组的边界,那么即使前面所有的空间都是空闲的(因为出队了),但是我此时依然无法再入队,因为会被判断“溢出”,这就是所谓了“假溢出”现象。那如果是在js中,当超过原定数组长度就会自动增加,那数组的长度不断增加,队头指针之前的空间也一样是浪费了的,所以,队列的顺序实现,采取了循环队列。

循环队列是将存储队列的数组看成是头尾相接的循环结构,即允许队列直接从数组中下标最大的位置延续到下标最小的位置。通过取模(%)很容易实现。

function CirQueue(){  this._queue = [];  this._front = this._rear = 0;//队头、队尾指针  this._maxSize = 10;//队列定长为10,可以随意设置}CirQueue.prototype = {  _enQueue:function(x){    try{      if(this._front == (this._rear+1)%this._maxSize) throw Error("队满");//判断是否队满      this._queue.push(x);//入队      this._rear = (this._rear+1)%this._maxSize;//rear指向空闲空间    }catch(e){      console.log("入队失败");    }  },  _deQueue:function(){    if(this._front == this._rear) throw Error("队空");//判断是否队空    var q = this._queue[this._front];    this._front = (this._front+1)%this._maxSize;    return q;  },  _getQueue:function(){    if(this._front == this._rear) throw Error("队空");    return this._queue[this._front];  }};var q = new CirQueue();q._enQueue(1);q._enQueue(2);q._enQueue(3);console.log(q._getQueue());//1console.log(q._deQueue());//1console.log(q._getQueue());//2console.log(q._deQueue());//2console.log(q._getQueue());//3console.log(q._deQueue());//3console.log(q._getQueue());//抛出异常

特别要说:

(1)队满的判断条件是front == (rear+1)%maxSize,因为牺牲了一个空闲空间,以便区别队空队满,否则队空队满的判断条件都为front == rear,不方便操作。

(2)队列删除其实并没有删除元素,只是移动了front指针,让那个元素看起来像是出队了一样。反正之后入队新的元素值会覆盖之前的值,不会对操作造成影响。

3、链队

function LinkQueue(){  this._front = this._rear = null;//队头、队尾指针}LinkQueue.prototype = {  _enQueue:function(x){    try{      var node = {_data:x,_next:null};      if(this._rear == null){//当队尾指针为null时,队空        this._rear = this._front = node;      }else{        this._rear._next = node;//将当前rear的下一个元素指向node        this._rear = node;//把rear指向当前最后的元素,即node      }    }catch(e){      console.log("入队失败");    }  },  _deQueue:function(){    if(this._front == null) throw Error("队空");    var q = this._front;    this._front = this._front._next;//队头指针移动    return q._data;  },  _getQueue:function(){    if(this._front == null) throw Error("队空");    return this._front._data;  }};var q = new LinkQueue();q._enQueue(1);q._enQueue(2);q._enQueue(3);console.log(q._getQueue());//1console.log(q._deQueue());//1console.log(q._getQueue());//2console.log(q._deQueue());//2console.log(q._getQueue());//3console.log(q._deQueue());//3console.log(q._getQueue());//抛出异常

以上栈和队列的顺序存储和链接存储的基本操作的算法就完毕啦~完结撒花~说着玩的【严肃脸】接下来就是栈和队列的应用举例,可以自己写写代码,如果有好的代码求分享哦~比哈特

 

栈的应用举例——表达式求值

  表达式求值是编译程序中一个最基本问题。表达式是由运算对象、运算符和圆括号组成的式子。运算符从运算对象的个数上分,有单目运算和双目运算符;从运算类型上分,有算术运算、关系运算、逻辑运算等。在此只讨论双目运算的算术表达式。

  题目:中缀表达式3*(4+2)/2-5#的求值。(中缀表达式:运算符在运算对象中间的表达式)

  伪代码:OPND—运算对象栈,OPTR—运算符栈,#结束符

  1.将栈OPND、OPTR初始化为空

  2.从左到右扫描每一个字符执行以下操作,直到遇到#

    2.1若当前字符为运算对象,入OPND栈

    2.2若当前字符是运算符且OPTR栈空,则入OPTR栈

    2.3若当前字符时运算符且OPTR栈不空,则比较栈顶元素和当前运算符的优先级

      2.3.1 若当前元素为),栈顶元素为(,则从OPTR栈出栈一个元素,继续2

      2.3.1 若栈顶元素优先级高于或等于当前元素,则从OPND出栈两个运算对象,从OPTR出栈一个运算符,将计算的结果压入OPND栈中,继续2

      2.3.2 若栈顶元素优先级低于当前元素,则将当前元素入栈OPTR,继续2

  3.输出栈OPND的栈顶元素,即表达式的运算结果

  运算符优先级为:()> * / > + - > #

var opnd = new SeqStack();//此处的SeqStack就是之前的顺序栈var optr = new SeqStack();var str = "3*(4+2)/2-5#";//可以换成任何你希望的算式,也可以写成函数,作为参数传入,或者由用户输入,在处理字符串前记得在最后的地方加上#结束符for(var i=0;i<str.length;i++){  if(isNaN(parseInt(str[i]))){//判断是否为数值,不为数值则进入if,为数值进入else    console.log("optr:"+optr._getTop());    if(optr._getTop() == "空栈" || optr._getTop() == "("){      optr._push(str[i]);      console.log("空栈或(:"+optr._getTop());      continue;    }    if(str[i] == ")"){      while(optr._getTop() != "("){        opnd._push(calculate(opnd._pop(),opnd._pop(),optr._pop()));      }      optr._pop();      console.log("52:"+optr._getTop());      continue;    }    var compare = priority(optr._getTop())- priority(str[i]);    switch(compare>=0){      case true:        console.log("59:"+opnd._getTop());        opnd._push(calculate(opnd._pop(),opnd._pop(),optr._pop()));        console.log("61:"+opnd._getTop());        i--;//保证当前元素不会因为i++被跳过        break;      case false:        optr._push(str[i]);break;    }      }else{    console.log("opnd:"+opnd._getTop());    opnd._push(parseInt(str[i]));//当前字符解析为数值,压入opnd栈中  }}document.write(opnd._pop());//运算符的优先级function priority(elem){  switch(elem){    case "(":    case ")":elem = 3;break;        case "*":    case "/":elem = 2;break;    case "+":    case "-":elem = 1;break;    default:elem = 0;  }  return elem;}//计算function calculate(num1,num2,sign){  switch(sign){    case "*":      return num2*num1;    case "/":      return num2/num1;    case "+":      return num2+num1;    case "-":      return num2-num1;  }}

 

队列的应用举例——火车车厢重排

  题目:给定任意编号的n节车厢,按照1~n的编号进行排序。现有一个入轨、一个出轨和k个缓冲轨进行排序,缓冲轨位于入轨和出轨直接。

  伪代码:1.对k个缓冲轨初始化。初始化下一个要输出的车厢号为 nowOut=1。

      2.依次取入轨中的车厢编号:

        2.1 如果当前车厢编号等于 nowOut,则

          2.1.1 输出该车厢

          2.1.2 nowOut++

        2.2 当前车厢编号不等于 nowOut,考察每一个缓冲轨 for( i=0;i<k;i++)

          2.2.1 取缓冲轨 i 的队头元素c

          2.2.2 如果c等于nowOut,则

            2.2.2.1 将缓冲轨 i 的队头元素出队并输出

            2.2.2.2 nowOut++

        2.3 如果入轨和缓冲轨的队头元素没用编号为nowOut的车厢,则

          2.3.1 求小于当前车厢编号的最大队尾元素所在缓冲轨 i

          2.3.2 如果 i 存在,则把当前车厢一指该缓冲轨

          2.3.3 如果 i 不存在,则判断是否有空缓冲轨

            2.3.3.1 有空缓冲轨,将当前车厢入缓冲轨

            2.3.3.2 没有空缓冲轨,则无法重排车厢,算法结束

 

function carriage(k,str){  var queue = [];//存储缓冲轨的数组,保存的元素是数组对象  for(var j=0;j<k-1;j++){//有一条缓冲轨作为入轨到出轨的通道    queue[j] = new LinkQueue();//链队列  }  var nowOut = 1;//初始化需要出列的车厢号  var result = "";//最后出列的顺序  for(j=0;j<str.length;j++){//遍历传入的数组    if(str[j] == nowOut){//如果当前车厢号等于出列号,则直接出列,并将nowOut加一      result += str[j];      nowOut++;    }else{      var frontArr = [];//缓冲列的队头元素所在缓冲区和其车厢编号      var rearArr = [];//缓冲区的队尾元素所在缓冲区和其车厢编号      var emptyQu = [];//存储空的缓冲区      var calc = false;//如果所以处理的方式都试过,但是并没有办法在继续,则退出算法      for(var i=0;i<k-1;i++){//遍历缓冲区,获取存储的数据        try{//尝试获取队头和队尾数据          frontArr.push({"_index":i,"_data":queue[i]._front._data});          rearArr.push({"_index":i,"_data":queue[i]._rear._data});          }catch(e){//如果缓冲区中没有数据,则把当前缓冲区的下标存储在emptyQu中          emptyQu.push(i);        }      }      for(i=0;i<frontArr.length;i++){//查看队头信息,是否有队头能够出队        if(frontArr[i]._data == nowOut){//当前队头正是需要出队的车厢号          result += nowOut;          nowOut++;          queue[frontArr[i]._index]._deQueue();//出队          j--;//当前的字符未用,而是在已入列的找到,故需要重新再次判断          var finded = true;//已经出队,则当前一轮操作可以退出,继续下一轮          calc = true;//已经进行操作          break;        }      }      if(window.finded){//退出当前一轮操作        continue;      }      if(!!rearArr.length){//队尾数据是否存在        var lowRears = [];//存储小于当前车厢号的队尾元素        for(i=0;i<rearArr.length;i++){          if(rearArr[i]._data < str[j]){            lowRears.push(rearArr[i]._data);          }        }        if(!!lowRears.length){//存在小于当前车厢号的队尾元素          var max = Math.max.apply(Math,lowRears);//找出其中最大者          rearArr.filter(function(elem){//筛选出最大者,并使其进入相应缓冲区中            if(parseInt(elem["_data"]) == max){              queue[parseInt(elem["_index"])]._enQueue(str[j]);            }          });          calc = true;//已经处理了当前数据          continue;        }      }      if(!!emptyQu.length){//空缓冲区是否存在        queue[emptyQu[0]]._enQueue(str[j]);//将数据入队        continue;      }      if(!calc){//如果以上操作都没能进行,则重排失败,退出算法        return "重排失败";      }    }  }  while(nowOut <= str.length){//将还在缓冲区中的数据依次遍历,尝试出列    for(var m=0;m<queue.length;m++){      try{        if(queue[m]._getQueue() == nowOut){          result += nowOut;          queue[m]._deQueue();          nowOut++;        }        }catch(e){};    }  }  return result;//将最后的结果返回}document.write(carriage(3,[3,6,9,2,4,7,1,8,5]));//123456789document.write(carriage(3,[3,10,6,9,2,4,7,1,8,5]));//重排失败

后话:

啊啊啊啊啊,真的差点崩了,写了5个小时才写完(/(ㄒoㄒ)/~~)代码意外的爱我呢,拉着我各种唠嗑不准我走,然后我就对它说啊,你要雨露均沾,但是它就宠我就宠我【笑哭】

终于终于,写完啦!完事开头难,看来之后应该会越写越顺的,加油咯~代码的地方,还有很多很多不足之处,不够精简,不够健壮,所以之后会再回过头来改改的,到时做一个大的总结也是不错的,今天先这样咯~晚安安~