「データ構造」Stack、Queue

9299 ワード
データ構造 テキストリンク
Stack
スタックは本のように、一つ一つデータを積み上げる資料構造です.
特長
  • LIFO (Last In First Out)
    最後に入力したデータは最初に出ることができます.
  • データは順番に格納されており、最後に入力するのに最適なデータは有意義である.
  • アイドルスタックから要素を抽出しようとすると、スタックバックフローが発生し、スタックオーバーフローと呼ばれるスタックオーバーフローが発生します.
    • 活用する
    LIFOの特徴を利用して、以下の状況でスタックデータ構造を使用することができる.
  • Webブラウザアクセス履歴(後退)
    ページを移動するたびに、スタックでページが開きます.「≪戻る|Back|emdw≫」ボタンをクリックして、スタックに格納されている最後のデータを表示します.
  • 逆シーケンス文字列の作成
    スタックに文字列順にプッシュされ、すべての文字列がスタックに格納されている場合、順popになります.
    • キャンセル
  • (CTRL+Z)
    後退と同様に、実行レコードをスタック順にプッシュします.元に戻すと最後のレコードがポップアップされ、前のレコードに戻ります.
  • 再帰アルゴリズム
    • を実現する
    インプリメンテーション
    配列が使用されていない場合は、次の操作を実行できます.
    class Stack {
  constructor() {
    this.storage = {};
    this.top = 0;
  }
  size() {
    return this.top;
  }
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  pop() {
    if(this.size()<1) {
      return;
    }
    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    return result;
  }
}
    Queue
    データ待ち行列のようにFIFOの特徴を持つ資料構造.
    特長
  • FIFO (First In First Out)
    先に入力したデータは先に出ます.スタックがドアpush,popを通過すると,キューの入口と出口が分離される.
  • データを入力順に実行する必要がある場合に適しています.
    • 活用する
  • プリンタ印刷キュー
  • コールセンター待機
  • BFSアルゴリズム
    • を実施する.
    インプリメンテーション
    javascriptの配列shift、pushを用いてQを模倣して実現することができる.ただし、shiftを使用して最初の要素を削除すると、配列内で再ソートが発生するため、実際のキューよりも時間の複雑さが大きくなります.実際には、キューから最初の要素を削除するにはO(1)が必要ですが、配列を使用すると、最初の要素を削除して配列全体をループする場合は、残りの配列の要素を前に1つ引くのに余分な時間がかかります.したがって、以下のことが実現される.
    class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    return this.rear - this.front;
  }
  
  enqueue(element) {
    this.storate[this.rear] = element;
    this.rear += 1;
  }
  
  dequeue() {
    if(this.size() === 0) {
      return;
    }
    const result = this.storate[this.front];
    delete this.storate[this.front];
    this.front += 1;
    return result;
  }
}
    [1日3.SQL]Leetcode-Mediums&Hards
    Androidサスペンションボックスは、サービスでサスペンション窓を開きます.サービスでDialogを開きます.