StackとQueueの実装

30867 ワード
データ構造 テキストリンク

Stack実装


1)シナリオ
2)接続リスト

整列


push popの使用

接続リスト

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

class Stack {
  constructor() {
    this.top = null;
    this.len = 0;
  }

  push(value) {
    const node = new Node(value);
    node.next = this.top;
    this.top = node;
    this.len += 1;
  }

  pop() {
    const value = this.top.value;
    this.top = this.top.next;
    this.len -= 1;
    return value;
  }

  size() {
    return this.len;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.size());
console.log(stack.pop());
console.log(stack.size());
  • ノードクラス:valueとnextのプロパティ値があります.
  • Stackクラス:既存this.トップに接続するときは次のためにトップを自分のノードに設定します.
    • もし1がpushされたら、これは.トップはnullなので接続されていません.1というノードはthisです.トップになります.( Node { value: 1, next: null } )
    2押されたらこれtopは1のノードがnextに接続されている.topはnext接続を含むコンテンツです.( Node { value: 2, next: Node { value: 1, next: null } } )
    popの場合、現在最も高いthisです.上部の次はこれです.トップになります.(つまり、上のを削除します.)

    画像の例


    ex) stack.push(5) , stack.push(6)運転時

    Queue実装

  • アレイ
  • 接続リスト

    • 整列

    class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
console.log(queue.dequeue());
queue.enqueue(8);
console.log(queue.size());
console.log(queue.peek());
    frontとhutを基準に、hutを1回増加するたびに、減少するたびにfrontを1回増加させる.

    接続リスト

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

class Queue {
  constructor() {
    this.head = null; //0에서 null로수정
    this.tail = null;
    this.len = 0;
  }

  enqueue(newValue) {
    const newNode = new Node(newValue);

   if (this.head === null) {
      this.tail = newNode;
      this.head = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.len += 1;
  }

  dequeue() {
    const value = this.head.value;
    this.head = this.head.next;
    this.len -= 1;
    return value;
  }

  size() {
    return this.tail.value - this.head.value + 1;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
console.log(queue.dequeue());		//1
console.log(queue.size());		//4
console.log(queue.dequeue());		//2
console.log(queue.size());		//3
    stackと同様にノードクラスを作成する
    デフォルトでは、Queueは開始と終了を表すheadとtailに設定されています.

    状況の説明


    1) this.tail.next = newNode;2) this.tail = newNode;1)console.log(this)を下に追加
    2)下記にconsole.log(this)を追加
    Queue {
  head: Node { value: 1, next: Node { value: 2, next: null } },
  tail: Node { value: 1, next: Node { value: 2, next: null } },
  len: 1
}		//1)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: null } },
  tail: Node { value: 2, next: null },
  len: 1
}		//2)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 2, next: Node { value: 3, next: null } },
  len: 2
}		//3)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 3, next: null },
  len: 2
}		//4)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 3, next: Node { value: 4, next: null } },
  len: 3
}		//5)
Queue {
  head: Node { value: 1, next: Node { value: 2, next: [Node] } },
  tail: Node { value: 4, next: null },
  len: 3
}		//6)
    1)において同じであり,2)においてheadである.nextはtailと同じと考えられる.
    3)からヘッドまで.nextはtailと同じと考えられています.this.tail = newNode;からtail晩4)になった.
  • 、すなわち、同じメモリ、headはnextによって生成され続け、最後にtailは同じメモリのnextをheadとtailに適用し、現在のノードを追加する.
  • 写真の上下はtailです.
    • [esercizio] React Hooks 3
    フロントエンド-テキストループスクロール再生