JavaScriptの配列を使用してデータ構造内のキューとスタックを実現

今日はプロジェクトでJavaScriptを使用してデータ構造のキューとスタックを実装します.ここでまとめます.
一、キューとスタックの簡単な紹介
1.1、キューの基本概念
キュー:先進的なプリアウト(FIFO)をサポートする集合であり、先に挿入されたデータが、先に取り出される!
次の図に示します.
　　
1.2、スタックの基本概念
スタック:後進先出(LIFO)をサポートする集合であり、後進先出(LIFO)が挿入されたデータであり、先に取り出される!
次の図に示します.
　　
二、JavaScriptでキューとスタックを実現する
JavaScriptでキューと配列を実装するには、主に配列を介します.js配列では、キューとスタックを容易に実装するためのいくつかの方法が用意されています.

shift:配列から最初の要素を削除し、この要素の値を返します.

unshift:配列の先頭に1つ以上の要素を追加し、新しい長さ

を返します.

push:配列の末尾に要素を追加し、新しい長さ

を返します.

pop:配列から最後の要素を削除し、この要素の値を返します.

2.1、実装キュー

 1 <script type="text/javascript">
 2         //           
 3         var a=new Array();
 4         console.log(a);
 5         //unshift:                ，       
 6         console.log("  ");
 7         a.unshift(1)
 8         console.log(a);//----->1
 9         a.unshift(2);
10         console.log(a);//----->2,1
11         a.unshift(3);
12         console.log(a);//----->3,2,1
13         a.unshift(4);
14         console.log(a);//----->4,3,2,1
15         console.log("  ，    ");
16         console.log(a);
17         //pop：             ，         
18         a.pop();//----->1
19         console.log(a);
20         a.pop();//----->2
21         console.log(a);
22         a.pop();//----->3
23         console.log(a);
24         a.pop();//----->4
25         console.log(a);
26 </script>

Googleブラウザコンソールで出力される効果は、次の図のようになります.
　　
2.2、実装スタック

 1 <script type="text/javascript">
 2         //           
 3         var a=new Array();
 4         console.log(a);
 5         //push:                ，       
 6         console.log("  ");
 7         a.push(1)
 8         console.log(a);//----->1
 9         a.push(2);
10         console.log(a);//----->1,2
11         a.push(3);
12         console.log(a);//----->1,2,3
13         a.push(4);
14         console.log(a);//----->1,2,3,4
15         console.log("  ，    ");
16         console.log(a);
17         //pop：             ，         
18         a.pop();//----->4
19         console.log(a);
20         a.pop();//----->3
21         console.log(a);
22         a.pop();//----->2
23         console.log(a);
24         a.pop();//----->1
25         console.log(a);
26 </script>

Googleブラウザコンソールで出力される効果は、次の図のようになります.
　　
2.3、push方法とunshift方法の性能テスト
Arrayのpushとunshiftメソッドはいずれも現在の配列に要素を追加することができ,異なることにpushは末尾に追加され,unshiftは先頭に追加され,原理からunshiftの効率が低いことが分かる.なぜなら、要素を追加するたびに、既存の要素を1つ下に移動するからです.しかし、果たして効率の違いはどれほど大きいのだろうか.簡単にテストしてみましょう.

 1 <script type="text/javascript">
 2     /*
 3          "var s=+newDate();"     
 4         :=+          ;
 5     +   .valueOf();
 6     +new Date()   new Date().valueOf()
 7     //4               
 8       alert(+new Date());
 9       alert(+new Date);
10       var s=new Date();
11       alert(s.valueOf());
12       alert(s.getTime());
13     */
14     var arr = [ ];
15     var startTime = +new Date(); //+new Date()   new Date().valueOf()，          
16      // push     
17      for (var i = 0; i < 100000; i++) { 
18      　　arr.push(i); 
19      }
20      var endTime = +new Date();
21      console.log("  push        100000     "+(endTime-startTime)+"  "); 
22      
23      startTime = +new Date(); 
24      arr = [ ]; 
25      // unshift     
26      for (var i = 0; i < 100000; i++) { 
27      　　arr.unshift(i); 
28      }
29      endTime = +new Date();
30      console.log("  unshift        100000     "+(endTime-startTime)+"  "); 
31 </script>

このコードはそれぞれ100000回のpushとunshift操作を実行し、Googleブラウザで1回実行した結果、下の図に示すように、unshiftはpushより100倍も遅いことがわかります.そのため、普段はunshift、特に大きな配列を慎む必要があります.それは必ずunshiftの効果を達成しなければならないならば、Arrayのreverseの方法を借りて、Arrayのreverseの方法は1つの配列を反転することができます.配列に入れる要素をpushで追加し、reverseをもう一度実行するとunshiftの効果が得られます.例:

 1 <script type="text/javascript">
 2       //           
 3         var a=new Array();
 4         //  push            
 5         a.push(1)
 6         a.push(2);
 7         a.push(3);
 8         a.push(4);
 9         console.log("              ");
10         console.log(a);//----->1,2,3,4
11         //Array     reverse   ，         。           push  ，     reverse，    unshift   
12         a.reverse();//  reverse         
13         console.log("              ");
14         console.log(a);
15 </script>

Googleブラウザコンソールで出力される効果は、次の図のようになります.
　　
実行結果から,配列要素の順序が反転した.
2.4、reverse方法の性能テスト
reverseの性能はどうですか.次にテストします.

1 <script type="text/javascript">
2         var arr = [ ], s = +new Date; 
3         for (var i = 0; i < 100000; i++) { 
4         　　    arr.push(i); 
5         }
6         //  reverse        100000       
7         arr.reverse(); 
8         console.log("  reverse        100000         ："+(+new Date - s)+"  ");
9 </script>

Googleブラウザコンソールで出力される効果は、次の図のようになります.
実行効果から,reverseメソッドの性能は極めて高く,安心して使用できることがわかる.
以上javascriptで配列を介してキューとスタックを実現するまとめについて述べ,push,unshift,reverseのいくつかの方法の大きな配列を操作する上での性能の優劣を簡単にテストした.