一、隊(duì)列和堆棧的簡單介紹
1.1、隊(duì)列的基本概念
隊(duì)列:是一種支持先進(jìn)先出(FIFO)的集合,即先被插入的數(shù)據(jù),先被取出!
如下圖所示：
1.2、堆棧的基本概念
堆棧:是一種支持后進(jìn)先出(LIFO)的集合,即后被插入的數(shù)據(jù),先被取出!
如下圖所示：
二、 在JavaScript中實(shí)現(xiàn)隊(duì)列和堆棧
在JavaScript中實(shí)現(xiàn)隊(duì)列和數(shù)組主要是通過數(shù)組，js數(shù)組中提供了以下幾個方法可以讓我們很方便實(shí)現(xiàn)隊(duì)列和堆棧：
•shift:從數(shù)組中把第一個元素刪除，并返回這個元素的值。
•unshift: 在數(shù)組的開頭添加一個或更多元素，并返回新的長度
•push:在數(shù)組的中末尾添加元素，并返回新的長度
•pop:從數(shù)組中把最后一個元素刪除，并返回這個元素的值。
2.1、實(shí)現(xiàn)隊(duì)列
<script type="text/javascript">//創(chuàng)建一個數(shù)組來模擬隊(duì)列var a=new Array();console.log(a);//unshift: 在數(shù)組的開頭添加一個或更多元素，并返回新的長度console.log("入隊(duì)");a.unshift()console.log(a);//----->a.unshift();console.log(a);//----->,a.unshift();console.log(a);//----->,,a.unshift();console.log(a);//----->,,,console.log("出隊(duì)，先進(jìn)先出");console.log(a);//pop：從數(shù)組中把最后一個元素刪除，并返回這個元素的值a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);</script> 在google瀏覽器控制臺輸出的效果如下圖所示：
2.2、實(shí)現(xiàn)堆棧
<script type="text/javascript">//創(chuàng)建一個數(shù)組來模擬堆棧var a=new Array();console.log(a);//push: 在數(shù)組的末尾添加一個或更多元素，并返回新的長度console.log("入棧");a.push()console.log(a);//----->a.push();console.log(a);//----->,a.push();console.log(a);//----->,,a.push();console.log(a);//----->,,,console.log("出棧，后進(jìn)先出");console.log(a);//pop：從數(shù)組中把最后一個元素刪除，并返回這個元素的值a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);a.pop();//----->console.log(a);</script> 在google瀏覽器控制臺輸出的效果如下圖所示：
2.3、push方法和unshift方法的性能測試
Array的push與unshift方法都能給當(dāng)前數(shù)組添加元素，不同的是，push是在末尾添加，而unshift則是在開頭添加，從原理就可以知道，unshift的效率是較低的。原因是，它每添加一個元素，都要把現(xiàn)有元素往下移一個位置。但到底效率差異有多大呢？下面來簡單測試一下。
<script type="text/javascript">/*關(guān)于代碼中"var s=+newDate();"的技巧說明解釋如下:=+這個運(yùn)算符是不存在的;+相當(dāng)于.valueOf();+new Date()相當(dāng)于new Date().valueOf()//個結(jié)果一樣返回當(dāng)前時(shí)間的毫秒數(shù)alert(+new Date());alert(+new Date);var s=new Date();alert(s.valueOf());alert(s.getTime());*/var arr = [ ];var startTime = +new Date(); //+new Date()相當(dāng)于new Date().valueOf()，返回當(dāng)前時(shí)間的毫秒數(shù)// push性能測試 for (var i = ; i < ; i++) { arr.push(i); }var endTime = +new Date();console.log("調(diào)用push方法往數(shù)組中添加個元素耗時(shí)"+(endTime-startTime)+"毫秒"); startTime = +new Date(); arr = [ ]; // unshift性能測試 for (var i = ; i < ; i++) { arr.unshift(i); }endTime = +new Date();console.log("調(diào)用unshift方法往數(shù)組中添加個元素耗時(shí)"+(endTime-startTime)+"毫秒"); </script> 這段代碼分別執(zhí)行了100000次push和unshift操作，在Google瀏覽器運(yùn)行一次，得到的結(jié)果如下圖所示：
可見，unshift比push要慢差不多100倍！因此，平時(shí)還是要慎用unshift，特別是對大數(shù)組。那如果一定要達(dá)到unshift的效果，可以借助于Array的reverse方法，Array的reverse的方法能夠把一個數(shù)組反轉(zhuǎn)。先把要放進(jìn)數(shù)組的元素用push添加，再執(zhí)行一次reverse，就達(dá)到了unshift的效果。比如：
<script type="text/javascript">//創(chuàng)建一個數(shù)組來模擬堆棧var a=new Array();//使用push方法在數(shù)組的末尾添加元素a.push()a.push();a.push();a.push();console.log("數(shù)組反轉(zhuǎn)之前數(shù)組中的元素順序");console.log(a);//----->,,,//Array有一個叫做reverse的方法，能夠把一個數(shù)組反轉(zhuǎn)。先把要放進(jìn)數(shù)組的元素用push添加，再執(zhí)行一次reverse，就達(dá)到了unshift的效果a.reverse();//使用reverse方法將數(shù)組進(jìn)行反轉(zhuǎn)console.log("數(shù)組反轉(zhuǎn)之后數(shù)組中的元素順序");console.log(a);</script> 在google瀏覽器控制臺輸出的效果如下圖所示：
從運(yùn)行結(jié)果來看，數(shù)組元素的順序已經(jīng)反轉(zhuǎn)過來了。
2.4、reverse方法的性能測試
reverse的性能又如何呢，下面再來測試：
<script type="text/javascript">var arr = [ ], s = +new Date; for (var i = ; i < ; i++) { arr.push(i); }//調(diào)用reverse方法將數(shù)組里面的元素的順序反轉(zhuǎn)arr.reverse(); console.log("調(diào)用reverse方法將數(shù)組里面的元素的順序反轉(zhuǎn)耗時(shí)："+(+new Date - s)+"毫秒");</script> 在google瀏覽器控制臺輸出的效果如下圖所示：
從運(yùn)行效果中可以看到，reverse方法的性能極高，可以放心使用。
以上就是關(guān)于在javascript中通過數(shù)組來實(shí)現(xiàn)隊(duì)列和堆棧的總結(jié)，并且簡單測試了一下push、unshift、reverse這幾個方法在操作大數(shù)組方面的性能優(yōu)劣。
以上所述是小編給大家介紹的JavaScript數(shù)組實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列與堆棧，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會及時(shí)回復(fù)大家的。在此也非常感謝大家對武林網(wǎng)網(wǎng)站的支持！
新聞熱點(diǎn)
疑難解答
