Googleインタビュー問題解決

日符号化問題の解説
Quackは、スタックとキューの両方のプロパティを組み合わせたデータ構造です.3つの操作が可能であるように、左から右に書かれた要素のリストとして見ることができます.

push(x):リストの左端に新しい項目xを追加する

pop () :リストの左端にある項目を削除して返す

pull () :リストの右端にある項目を削除します.

3つのスタックとO(1)の追加メモリを使用してQuackを実装し、任意のプッシュ、ポップ、プル操作のための償却時間をO(1)とする.

JavaScriptのソリューション
プッシュとPOPは既にリスト操作としてサポートされています.リスト操作は実際に右からアイテムを削除します.
プルは、最初の項目を削除するようにトリッキーになりますO(n)操作されるリスト内のすべての他の項目を移動する必要があります.
我々は、DEC(ダブルエンドキュー)を利用することができます.キューの種類を削除することができますし、フロントからの項目だけでなく、バック.ですから、DECKをスタックとキューとして使用することができます.ここでDequeについてもっと読むことができます.DECは、一般的に、2つのデータ構造、すなわち、円形配列、2重連結リストを用いて作成される.
しかし、我々の解決のために、我々はスタックでdequeをつくる必要があります.
つの方法は3つのスタックを持つことです.

左(プッシュとポップに使用されます)

右(プル用)

バッファ(スタックを反転するために使用されます)!無題

プッシュ
我々は直接左からアイテムを追加することができますし、我々は動的なJavaScriptの配列を使用しているように我々はQuackの上限を心配する必要はありませんか、または我々は左のスタックを言うことができます.


ポップ
私たちが左の配列にアイテムを持っているならば、我々は単にこのように開くことができます

しかし、我々のケースでは、我々が我々の右のリストでアイテムを持っているかどうかチェックする必要があります.
例:

このためには、スタックの左にスタックの右側の項目の半分を移動する必要があります

バッファの項目の半分を移動します.

残りの項目を左に移動します.

バッファー内のすべての項目を右側に移動します.

プル操作に関しては、右の配列にアイテムを持っていない場合には、Quickのバランスをとる必要があります.
フルコードです

class Quack {
  constructor(left = [], right = []) {
    this.left = left;
    this.right = right;
    this.buffer = [];
  }

  print() {
    console.log(this.left, this.right);
  }

  push(newItem) {
    this.left.push(newItem);
  }

  pop() {
    if (this.left.length <= 0 && this.right.length <= 0) {
      console.log("Quack is already Empty");
      return;
    }
    if (this.left.length === 0) this.balance(this.right, this.left);
    this.left.pop();
  }

  pull() {
    if (this.left.length <= 0 && this.right.length <= 0) {
      console.log("Quack is already Empty");
      return;
    }
    if (this.right.length === 0) this.balance(this.left, this.right);
    this.right.pop();
  }

  balance(from, to) {
    const length = from.length;
    const halfPoint = Math.floor(length / 2);
    for (let i = 0; i < halfPoint; i++) {
      this.buffer.push(from.pop());
    }

    while (from.length > 0) {
      to.push(from.pop());
    }

    while (this.buffer.length > 0) {
      from.push(this.buffer.pop());
    }
  }
}

const quack = new Quack();

quack.push(1);
quack.push(2);
quack.push(3);

quack.print();
quack.balance(quack.right, quack.left);

quack.print();
quack.pull();
quack.pop();
quack.pop();
quack.pull();

quack.print();