TIL[データ構造-スタック]

Stackのコンセプト

スタックは線形のデータ構造であり、計算または実行はいずれも特定の方法で行われ、その特定の方法は「最初の最初の出力」または「最初の最初の出力」と呼ばれます.

Stackは通常、データを追加するpushとデータを削除するpopを主な機能とするタワー構造である.実際、私たちがよく使う配列方法にはpopとpushがあり、配列要素を追加または削除する役割を果たします.
Stackは現実生活でもよく見られる.ハノイでタワーのようなゲームや箱に物を入れるときにもStackが使われます.まず追加されたデータや品物は一番下に押され、上に次々と積み上げられているので、私たちは上から近づくしかありません.

Stackのpush,popメソッド論理構造

1. push

Step 1-Stackがいっぱい
Step 2-Stackが満了した場合のエラーの作成と終了
Step 3-Stackが満たされていない場合はトップに1を加える
Step 4-Stack topが指す位置にデータを入れる
Step 5-成功!

2. pop

Step 1-Stackが空か
Step 2-Stackが空の場合のエラーの作成と終了
Step 3-Stackが満たされていない場合はトップに1を加える
Step 4-Stack topが指す位置にデータを入れる
Step 5-成功!

Stack実装

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

  size() {
    return this.top + 1
  }

  push(element) {
    this.top += 1 // 맨 위의 데이터의 index
    this.storage[this.top] = element
  }

  pop() {
    if(this.top === -1) return undefined;
    let result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result; // 제거된 데이터를 리턴
  }
  
  isEmpty(){
    if(this.top === -1) return true;
    else return false;
  }
  
  peek(){
    if(this.top === -1) return undefined;
    else {
      return this.storage[this.top];
    }
  
}