JavaScriptを介したスタックとキューの探索

非常に多くの場合、完全にデッキアウトされた二重リンクリストは、達成しようとしていることに対してやり過ぎかもしれません。 この記事では、リンクリストの2つの非常に一般的なミニマリストのバリエーションであるスタックとキューについて説明します。

スタックとキューは、特に特定の順序で削除する必要がある場合に、受信データを処理する反対の方法です。 これらは一般に、データ構造としてではなく、抽象データ型と見なされます。つまり、正確な構造ではなく、特定の使用法を表します。 したがって、これらは、配列、リンクリスト、さらにはツリーなどの他のデータ構造を使用して、さまざまな方法で実装できるパターンに近いものです。

前提条件

リンクリストの基本を理解することは、リストの実装を理解するために不可欠です。リストの実装については、ここで概要を確認できます。

スタックとキューを理解するために必要ではありませんが、ここで短いイントロを書いたBigONotationの基本をすでに理解しているはずです。

スタック

スタックはLIFO構造と見なされます。つまり、後入れ先出しを意味します。 スタックにアイテムを追加し、タイマーが切れた、タスクが完了したなど、他の条件が満たされた場合、最後に追加されたアイテムが最初に削除され、対話できる唯一のアイテムになります。 私はこれをプレートのスタックの洗浄と乾燥として視覚化するのが好きです。スタックの一番上に追加すると、残りのプレートにアクセスする前に一番上のプレートでのみ作業するように制限されます。

非同期リクエストを行うときの再帰呼び出しスタックや標準のJavaScript呼び出しスタックのように、すでにスタックをたくさん使用しています。 このように操作の順序を厳密に制御する必要があることは非常に一般的であり、ツリーのトラバースや検索結果のランク付けなど、直感的ではない方法でも役立ちます。

これの最も基本的なバージョンは、単純な配列を使用するだけです。 配列を実装したスタックは O(1)、リンクリストの場合と同じです。これは、テールを操作するだけであり、インデックスを再作成する必要がないためです。 通常の使用が可能です push と pop これを行うためのメソッド。 これらの2つの関数を使用してデータを操作するだけである限り、技術的には機能スタックがあります。

const stack = [];

const add = val => stack.push(val);
const remove = () => stack.pop();

add('one');
add('two');
add('three');
remove();
console.log(stack); // ["one", "two"]

リンクリストはもう少し複雑です。通常のノードには1つのポインターといくつかのポインターしかありません。 add と remove メソッド。 リストに何もない場合は、ヘッドとテールまたはnullとして設定します。それ以外の場合は、その前のアイテムのポインターを変更します。 頭と尾のどちらを追加/削除するかは、それが私たちが対話している唯一のものである限り、問題ではありません。

この方法は、多数のノードを含むデータベースに接続している場合に適しています。 配列は固定サイズでロードされるため、リンクリストは必要なデータのチャンクのみをロードする方が適切です。

class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
};

class Stack {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  add(val) {
    const newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      const temp = this.head;
      this.head = newNode;
      this.head.next = temp;
    };

    this.length++;
    return this;
  }
  remove() {
    if (!this.head) return null;

    let temp = this.head;
    this.head = this.head.next;

    this.length--;
    return temp.val;
  }
};

let stack = new Stack()
stack.add('one')
stack.add('two')
stack.add('three')
stack.remove()
console.log(stack) // two -> one

キュー

キューは、 FIFO 構造のスタックの逆であり、先入れ先出しを意味します。 これは、列に並んでいるのとまったく同じです。最初に現れたので、最初に行くことができます。

同様に、配列の実装も可能ですが、今回は異なります。 何かを削除するときは最初から作業しているので、削除するたびに、コンピューターが配列の残りの部分をループしてすべてのインデックスを再作成する必要があります。 O(n).

const queue = [];

const add = val => queue.push(val);
const remove = () => queue.shift();

add('one');
add('two');
add('three');
remove();
console.log(queue); // ["two", "three"]

この場合、リンクリストは、インデックスの再作成の問題を回避するため、ほとんどの場合、大量のデータを処理するのに優れています。

もう一方の端から削除する限り、どちらの端に追加してもかまいません。この場合、尾に追加して頭を削除します。

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  enqueue(val) {
    const newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    };

    this.length++;
    return this;
  }
  dequeue() {
    if (!this.head) return null;
    if (this.head === this.tail) this.last = null;
    let temp = this.head;
    this.head = this.head.next;

    this.length--;
    return temp.val;
  }
}

let queue = new Queue();
queue.enqueue('one');
queue.enqueue('two');
queue.enqueue('three');
queue.dequeue();
console.log(queue); // two -> three

まとめ

これは、通常のリンクリストと配列から分割ヘアを作成するように見えるかもしれませんが、ますます洗練された構造に進むにつれて、スタックとキューは、データの構造化とトラバースの方法に不可欠なコンポーネントになります。