JavaScript でのスタックとキューのアルゴリズム分析-jsチュートリアル-php.cn

この記事の内容は JavaScript のスタックとキューのアルゴリズム分析に関するものです。必要な方は参考にしていただければ幸いです。

1. データ構造の理解

データ構造とは何ですか?以下は Wikipedia の説明です。

データ構造とは、コンピュータがデータを保存し、整理する方法です。

データ構造とは、インターフェイスまたはカプセル化を意味します。データ構造は、2 つの関数間のインターフェイス、またはデータ型として見ることができます。アクセス方法のカプセル化ユニオンで構成されるストレージコンテンツの構成

配列は最も単純なメモリデータ構造であるため、私たちは日常のコーディングでデータ構造を使用します。

Array
#スタック
##リンクされたリスト
ツリー
##グラフ
##ハッシュテーブル
##スタックとキューについて学びましょう..
2. スタック

2.1 スタックのデータ構造

スタックは後入れ先出し (LIFO) 原則に従った順序付きコレクション。新しく追加された要素または削除される要素は、スタックの最上部と呼ばれるスタックの同じ端に格納され、もう一方の端はスタックの最下部と呼ばれます。スタックでは、新しい要素はスタックの上部近くにあり、古い要素は下部近くにあります。

生活の中のオブジェクトへの類似: 重ねられた本や皿の積み重ね

2.2 スタックの実装

次のメソッドは、通常のスタックによく使用されます。 JavaScript でのスタックとキューのアルゴリズム分析 push は、スタックの先頭に 1 つ (または複数) の新しい要素を追加します。

pop は、スタックの先頭要素をオーバーフローさせ、削除された要素を返します

peek は、スタックを変更せずにスタックの最上位の要素を返します。

isEmpty は、スタックに要素がない場合は true を返し、それ以外の場合は false を返します。

size は要素の数を返します。スタック内

clear スタックをクリア##

class Stack {
  constructor() {
    this._items = []; // 储存数据
  }
  // 向栈内压入一个元素
  push(item) {
    this._items.push(item);
  }
  // 把栈顶元素弹出
  pop() {
    return this._items.pop();
  }
  // 返回栈顶元素
  peek() {
    return this._items[this._items.length - 1];
  }
  // 判断栈是否为空
  isEmpty() {
    return !this._items.length;
  }
  // 栈元素个数
  size() {
    return this._items.length;
  }
  // 清空栈
  clear() {
    this._items = [];
  }
}

ログイン後にコピー

##ここで振り返って、データ構造内のスタックが何であるかを考えてください。

突然、それはそれほど魔法的なものではなく、元のデータをカプセル化しただけであることがわかりました。カプセル化の結果は次のようになります。

は内部の要素を考慮せず、スタックの最上位の要素のみを操作します

この場合、コーディングはより制御しやすくなります。

2.3 スタックの応用

(1) 10 進数を任意の数値に変換

Requirements: 関数が与えられ、Target を入力value とbase、対応する基数を出力します (最大 16 進数)

baseConverter(10, 2) ==> 1010
baseConverter(30, 16) ==> 1E

ログイン後にコピー

分析:

基数変換の本質: ターゲット値を一度に 1 つずつ基数で割ります。Base、得られた四捨五入された値value は新しいターゲット値であり、ターゲット値が 0 未満になるまで剰余を記録し、最後に剰余を逆の順序で結合します。スタックを使用して余りを記録してスタックにプッシュし、結合時にポップアウトします

// 进制转换
function baseConverter(delNumber, base) {
  const stack = new Stack();
  let rem = null;
  let ret = [];
  // 十六进制中需要依次对应A~F
  const digits = '0123456789ABCDEF';

  while (delNumber > 0) {
    rem = Math.floor(delNumber % base);
    stack.push(rem);
    delNumber = Math.floor(delNumber / base);
  }

  while (!stack.isEmpty()) {
    ret.push(digits[stack.pop()]);
  }

  return ret.join('');
}

console.log(baseConverter(100345, 2)); //输出11000011111111001
console.log(baseConverter(100345, 8)); //输出303771
console.log(baseConverter(100345, 16)); //输出187F9

ログイン後にコピー

(2) 逆ポーランド式の計算

要件:

逆ポーランド式後置式とも呼ばれる式は、複雑な式を、(a b)*(c d) を ## に変換するなど、単純な演算に依存して計算結果を取得できる式に変換します。 #a b c d *

["4", "13", "5", "/", "+"] ==> (4 + (13 / 5)) = 6
["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
==> ((10 * (6 / ((9 + 3) * -11))) + 17) + 5

ログイン後にコピー

分析: シンボルをトリガーノードとして使用すると、シンボルの最初の 2 つの要素がシンボルに従って操作されます。スタックが 1 つの要素のみ

function isOperator(str) {
  return ['+', '-', '*', '/'].includes(str);
}
// 逆波兰表达式计算
function clacExp(exp) {
  const stack = new Stack();
  for (let i = 0; i <strong></strong> (3) 通常のスタックを使用して、<code>min</code> メソッド <code> でスタックを実装するまで、新しい結果がスタックにプッシュされます。 </code><p>アイデア:<strong> 使用法 データを保存するスタックが 2 つあり、そのうちの 1 つはデータの保存に特別に使用される </strong>dataStack</p> という名前で、もう 1 つは # という名前です。 ##minStack<p>。スタックに最小のデータを保存するために特別に使用されます。スタックをプッシュするときは、2 つのスタックの要素の数を常に同じにしてください。プッシュされた要素のサイズが <strong>minStack<code> の先頭の要素より小さい場合は、その要素のサイズを比較します。スタックの先頭をスタックにプッシュする場合は、スタックの先頭をコピーします。スタックの先頭がポップされると、要素はスタックにプッシュされます。両方をポップするだけです。このように、</code>minStack</strong> の最上位要素は常に最小値になります。 </p><pre class="brush:php;toolbar:false">class MinStack {
  constructor() {
    this._dataStack = new Stack();
    this._minStack = new Stack();
  }

  push(item) {
    this._dataStack.push(item);
    // 为空或入栈元素小于栈顶元素，直接压入该元素
    if (this._minStack.isEmpty() || this._minStack.peek() > item) {
      this._minStack.push(item);
    } else {
      this._minStack.push(this._minStack.peek());
    }
  }

  pop() {
    this._dataStack.pop();
    return this._minStack.pop();
  }

  min() {
    return this._minStack.peek();
  }
}

const minstack = new MinStack();

minstack.push(3);
minstack.push(4);
minstack.push(8);
console.log(minstack.min()); // 3
minstack.push(2);
console.log(minstack.min()); // 2

ログイン後にコピー

3. キュー3.1 キューのデータ構造キューは先入れ先出し (FIFO とも呼ばれます) に従います。先着順 (順序付けられた一連のサービス項目) の原則。キューは新しい要素を末尾に追加し、先頭から要素を削除します。最後に追加された要素はキューの最後に配置する必要があります

例え: 日常生活におけるショッピングキュー

3.2 キューの実装

一般的なキューでは、通常、次のメソッドが使用されます:

#enqueue JavaScript でのスタックとキューのアルゴリズム分析 1 つ (または複数) の新しい項目をキューの最後に追加します

#dequeue

キューの最初の項目 (つまり、キューの先頭) を削除し、削除された要素を返します

head
キューに変更を加えずにキューの最初の要素を返します
tail
キューに変更を加えずにキューの最後の要素を返します
isEmpty 队列内无元素返回true，否则返回false
size 返回队列内元素个数
clear 清空队列

class Queue {
  constructor() {
    this._items = [];
  }

  enqueue(item) {
    this._items.push(item);
  }

  dequeue() {
    return this._items.shift();
  }

  head() {
    return this._items[0];
  }

  tail() {
    return this._items[this._items.length - 1];
  }

  isEmpty() {
    return !this._items.length;
  }

  size() {
    return this._items.length;
  }

  clear() {
    this._items = [];
  }
}

ログイン後にコピー

与栈类比，栈仅能操作其头部，队列则首尾均能操作，但仅能在头部出尾部进。当然，也印证了上面的话：栈和队列并不关心其内部元素细节，也无法直接操作非首尾元素。

3.3 队列的应用

（1）约瑟夫环（普通模式）

要求: 有一个数组a[100]存放0~99；要求每隔两个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数。

分析: 按数组创建队列，依次判断元素是否满足为指定位置的数，如果不是则enqueue到尾部，否则忽略，当仅有一个元素时便输出

// 创建一个长度为100的数组
const arr_100 = Array.from({ length: 100 }, (_, i) => i*i);

function delRing(list) {
  const queue = new Queue();
  list.forEach(e => { queue.enqueue(e); });
  
  let index = 0;
  while (queue.size() !== 1) {
    const item = queue.dequeue();
    index += 1;
    if (index % 3 !== 0) {
      queue.enqueue(item);
    }
  }

  return queue.tail();
}

console.log(delRing(arr_100)); // 8100 此时index=297

ログイン後にコピー

（2）菲波那切数列（普通模式）

要求: 使用队列计算斐波那契数列的第n项
分析: 斐波那契数列的前两项固定为1，后面的项为前两项之和，依次向后，这便是斐波那契数列。

function fibonacci(n) {
    const queue = new Queue();
    queue.enqueue(1);
    queue.enqueue(1);
    
    let index = 0;
    while(index <p><strong>（3）用队列实现一个栈</strong></p><p><strong>要求:</strong> 用两个队列实现一个栈<br><strong>分析:</strong> 使用队列实现栈最主要的是在队列中找到栈顶元素并对其操作。具体的思路如下：</p><ol class=" list-paddingleft-2">
<li><p>两个队列，一个备份队列<code>emptyQueue</code>，一个是数据队列<code>dataQueue</code>；</p></li>
<li><p>在确认栈顶时，依次<code>dequeue</code>至备份队列，置换备份队列和数据队列的引用即可</p></li>
</ol><pre class="brush:php;toolbar:false">class QueueStack {
  constructor() {
    this.queue_1 = new Queue();
    this.queue_2 = new Queue();
    this._dataQueue = null; // 放数据的队列
    this._emptyQueue = null; // 空队列,备份使用
  }

  // 确认哪个队列放数据,哪个队列做备份空队列
  _initQueue() {
    if (this.queue_1.isEmpty() && this.queue_2.isEmpty()) {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    } else if (this.queue_1.isEmpty()) {
      this._dataQueue = this.queue_2;
      this._emptyQueue = this.queue_1;
    } else {
      this._dataQueue = this.queue_1;
      this._emptyQueue = this.queue_2;
    }
  };

  push(item) {
    this.init_queue();
    this._dataQueue.enqueue(item);
  };

  peek() {
    this.init_queue();
    return this._dataQueue.tail();
  }

  pop() {
    this.init_queue();
    while (this._dataQueue.size() > 1) {
      this._emptyQueue.enqueue(this._dataQueue.dequeue());
    }
    return this._dataQueue.dequeue();
  };
};

ログイン後にコピー

学习了栈和队列这类简单的数据结构，我们会发现。数据结构并没有之前想象中那么神秘，它们只是规定了这类数据结构的操作方式：栈只能对栈顶进行操作，队列只能在尾部添加在头部弹出；且它们不关心内部的元素状态。

以上がJavaScript でのスタックとキューのアルゴリズム分析の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。