2:00am, Writing code

Roughly coding. Posted from Berlin.

Javascriptでスタックを実装する

Javascriptには組み込みのデータ構造としてスタックが実装されていないので実装してみる。とはいえスタックに必要な基本操作はArrayに実装されているので、実質的にはスタック風のラッパーを被せるだけで事足りる。

実際のコードは以下のようになる。

class Stack {
  constructor() {
    this._array = [];
  }

  push(val) {
    this._array.push(val);
  }

  pop() {
    return this._array.pop();
  }

  peek() {
    return this._array[this._array.length - 1];
  }

  isEmpty() {
    return this._array.length === 0;
  }

  get top() {
    return this._array.length;
  }
}

topは現在のスタックの最大要素の位置を返すものでスタックポインタというやつである。get topとすることでゲッターとして定義している。これによってtopへの再代入を防止して擬似的にプライベート変数のような扱いにできる。

定義したStackは以下のように使用できる。

const s = new Stack();
s.push(1);
s.push(2);
s.push(3);
console.log(s.top); // 3
console.log(s.pop()); // 3
console.log(s.top); // 2
console.log(s.peek()); // 2
console.log(s.top); // 2
console.log(s.pop()); // 2
console.log(s.pop()); // 1
console.log(s.pop()); // undefined
console.log(s.top); // 0
console.log(s.isEmpty()); // true

参考

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

スタック - Wikipedia