「データ構造」Stack、Queue

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;
  }
}