JavaScript でキューを実装して性能を比較してみた - Qiita

JavaScript でキューを実装して性能を比較してみた。 今回は、以下の条件で実装を行った。 クラスとして実装する 1個のデータのエンキューとデキューを行うメソッドをそれぞれ実装する それ以外のメソッド (要素数、先頭を削除せずに取得など) は実装しない エラー処理 (空のときにデキューを試みるなど) は行わない なお、実装で出てくる # つきのメンバ変数はプライベートプロパティである。 方針・実装 配列のpush・shift 配列の末尾に要素を追加するメソッド push をエンキューとして用い、配列の先頭から要素を取り除いて返すメソッド shift をデキューとして用いる。 エンキューとデキューがともに1回メソッドを呼び出すだけで実現でき、シンプルな実装になる。 スタックを用いてプッシュ時退避 スタックによるキューの実装と、キューによるスタックの実装 #Python - Qiita

[yorkfield]

キューと言えばリングバッファだと思ってた。

[xlc]

キューに滞留するデータが少なければ単純な実装(push/shift)で問題なかろう。滞留するデータが多い場合は上限を決めて循環リストにするのでは。

[strawberryhunter]

QueueStack#dequeue()は頭悪そうな実装に見えるのにこの中では平均的に速いのが興味深い。先頭のインデックスを保持してArray#splice(index)にしたらQueueShiftはもっと速くできたりしないかね。

[gfx]

ベンチマークが現実のプログラムのワークロードとかけ離れている気はするが、push//shift法がChromeとFirefoxで全然速度の性質が違うのはけっこう驚きだな。

[softstone]

firefoxだとshiftまともに動くんか。/ECMAScriptが未だにまともなリストを言語仕様として持ってないのが諸悪の根源なので、いちいちこんなベンチマーク取らせんなってキレて良いよ。