世界

両端キューで柔軟性を 2 倍に | Duvvuru Kishore 著 | 2024 年 1 月

戻るエンキュー: 要素を後ろに追加するだけなので、0(1) 回で後ろにエンキューできます。 以前のバック要素は 56 で、エンキュー後は 89 です。デキューでは、どうすれば後方からデキューできるでしょうか?最初の方法: 最後の要素を削除するには、直前の要素までトラバースする必要があります!-0(n) 時間計算量2番目の方法: 最後の要素の前の要素をキャプチャし、前の要素の次の値を null に設定することで、O(1) の時間計算量を達成できます。最初の方法:ただし、キューの最後尾からデキューしたい場合は、最後から 2 番目のノードまで移動し、次のポインタを null を指すように変更する必要があります。 最後のノードを解放するには、リストの前から開始して、最後から 2 番目のノードに到達する必要があります。第二の方法最後のノードを末尾ポインターとして持っている場合でも、前のノードのアドレスはわかりません。次のノードが null であることだけがわかります。リンクリスト全体を走査せずに、何らかの方法で 2 番目のノードから最後のノードまで到達できたらどうなるでしょうか。すべてのノードが次のノードにアクセスできるのと同じように、すべてのノードが前のノードにアクセスできる場合はどうなるでしょうか?最後のノードを指すテール ポインタを使用すると、その前のノードにアクセスし、すぐに最後のノードをデタッチできるため、キューを後方からデシーケンスできるのでしょうか。ここで重要なのは、キューを拡張したのと同じようにノードを拡張することです変数を追加し直すなどして要素を取得できるようにキューが拡張されていますfunction createQueue(){let head = null;let back = null;............}同様に、以前のノードアドレスを取得するためにノード構造を変更できます。function Node(data){this.data=data;this.prev=null;this.next=null;}リンクされたリストは次のようになりますリンク リスト全体を走査することなく 2 番目のノードから最後のノードまで到達でき、0(1) の時間計算量でデキュー操作を実行できます。次に同じことをCodeで実装していきます。学び続ける…成長し続ける…