[2020. 10. 20 TIL] Data Structure - Stack, Queue

Stackの定義

A LIFO data structure!
The last element added to the stack will be the first element removed from the stack

Property

top:スタック上部データの位置値(インデックス).

maxSize:maxSizeはリポジトリの最大サイズ

を表す.

スタックアレイ:リポジトリ自体

Method

push():配列の末尾値を追加する方法

pop():配列の末尾値を削除する方法.取り出した値を出力または他の場所に指定できます.

空():リポジトリが空かどうかに基づいて、ブール値

を返します.

size():現在のリポジトリに戻るデータ数

JavascriptによるStackの実装

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

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top++;
  }

  pop() {
    let topVal = this.storage[this.top-1];
    delete this.storage[this.top-1];

    if(this.top > 0){
      this.top--;
    }

    return topVal;
  }
}

Queueの定義

A FIFO data structure
First In First Out
先入先出

How do we use them in programming?

Background tasks

Uploading resources

Printing/Task processing

キューは、プリンタの出力処理、Windowsシステムのメッセージプロセッサ、プロセス管理など、入力された時間順にデータを処理する必要がある場合に使用します.(ウィキペディア)
JavascriptによるQueueの実装

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }

  dequeue() {
    let frontVal = this.storage[this.front];
    delete this.storage[this.front];

    for(let i=1 ; i<this.rear ; i++){
      let curr = this.storage[i];
      this.storage[i-1] = curr;
    }

    if(this.rear > 0){
      this.rear--;
    }
    delete this.storage[this.rear];
    return frontVal;
  }
}