JavaScript數(shù)組實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列與堆棧

更新時間：2016年05月26日 11:08:06 作者：孤傲蒼狼

這篇文章主要介紹了JavaScript數(shù)組實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列與堆棧的相關(guān)資料,需要的朋友可以參考下

一、隊(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ù)
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ù)
// push性能測試 
for (var i = ; i < ; i++) { 
　　arr.push(i); 
}
var endTime = +new Date();
console.log("調(diào)用push方法往數(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ù)組中添加個元素耗時"+(endTime-startTime)+"毫秒"); 
</script>

　　這段代碼分別執(zhí)行了100000次push和unshift操作，在Google瀏覽器運(yùn)行一次，得到的結(jié)果如下圖所示：

　　可見，unshift比push要慢差不多100倍！因此，平時還是要慎用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)耗時："+(+new Date - s)+"毫秒");
</script>

　　在google瀏覽器控制臺輸出的效果如下圖所示：