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