Algorithmusanalyse von Stack und Queue in JavaScript

Der Inhalt dieses Artikels befasst sich mit der Algorithmusanalyse von Stack und Queue in JavaScript. Ich hoffe, dass er für Freunde hilfreich ist.

1. Datenstruktur verstehen

Was ist Datenstruktur? Das Folgende ist eine Erklärung aus Wikipedia

Datenstruktur ist die Art und Weise, wie Computer Daten speichern und organisieren

Datenstruktur bedeutet Schnittstelle oder Kapselung: Eine Datenstruktur kann als Schnittstelle zwischen zwei Funktionen betrachtet werden oder besteht aus Datentypen Zugriffsmethode Kapselung von Speicherinhalten, die aus Gewerkschaften bestehen

Wir verwenden Datenstrukturen in der täglichen Codierung, da Arrays die einfachsten Speicherdatenstrukturen sind. Das Folgende sind gängige Datenstrukturen

• Array

• Stapel

• Warteschlange

• Verknüpfte Liste

• Baum

• Diagramm

• Heap

• Hash

Lernen wir etwas über Stapel und Warteschlangen.

2. Stapel

2.1 Stapeldatenstruktur

Der Stapel ist eine geordnete Sammlung, die dem Last-In-First-Out-Prinzip (LIFO) folgt. Neu hinzugefügte oder zu löschende Elemente werden am selben Ende des Stapels gespeichert, das als oberes Ende des Stapels bezeichnet wird, und das andere Ende wird als unteres Ende des Stapels bezeichnet. Im Stapel befinden sich neue Elemente oben im Stapel und alte Elemente unten.

Analogie zu Gegenständen im Leben: ein Stapel zusammengeschobener Bücher oder Teller

2.2 Implementierung des Stapels

Folgendes Methoden werden häufig in gewöhnlichen Stapeln verwendet:

push fügt ein (oder mehrere) neue Elemente oben im Stapel hinzu

pop überläuft das oberste Element des Stapels und gibt das entfernte Element zurück

peek gibt das oberste Element des Stapels zurück, ohne den Stapel zu ändern

isEmpty gibt „true“ zurück, wenn sich kein Element im Stapel befindet, andernfalls wird „false“ zurückgegeben

size gibt die Anzahl der Elemente zurück der Stapel

clear löscht den Stapel

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 = [];
  }
}

Jetzt blicken wir zurück und überlegen, was der Stapel in der Datenstruktur ist.

Plötzlich stellte ich fest, dass es nicht so magisch war, sondern nur eine Kapselung der Originaldaten. Das Ergebnis der Kapselung ist: kümmert sich nicht um die darin enthaltenen Elemente, sondern betreibt nur das oberste Element des Stapels . In diesem Fall ist die Codierung besser kontrollierbar.

2.3 Anwendung des Stapels

(1) Dezimal zu beliebiger Basis

Anforderungen: Geben Sie bei einer gegebenen Funktion den Zielwert ein und Basis, geben Sie die entsprechende Basiszahl aus (maximal hexadezimal)

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

Analyse: Das Wesentliche der Basiskonvertierung: Teilen Sie den Zielwert nacheinander durch die Basis. Basis, der erhaltene gerundete Wert ist der neue Zielwert, zeichnen Sie den Rest auf, bis der Zielwert kleiner als 0 ist, und kombinieren Sie schließlich die Reste in umgekehrter Reihenfolge. Verwenden Sie den Stapel, um den Rest aufzuzeichnen, ihn in den Stapel zu schieben und ihn beim Kombinieren herauszuholen :

Umgekehrte polnische Ausdrucksformel, auch Postfix-Ausdruck genannt, wandelt komplexe Ausdrücke in Ausdrücke um, die sich auf einfache Operationen stützen können, um Berechnungsergebnisse zu erhalten. Beispielsweise wird

in

// 进制转换
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

umgewandelt

Analyse: Verwenden Sie das Symbol als Triggerknoten. Sobald ein Symbol angetroffen wird, werden die ersten beiden Elemente des Symbols entsprechend dem Symbol bearbeitet und das neue Ergebnis in den Stapel verschoben, bis nur noch ein Element vorhanden ist im Stapel

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

(a+b)*(c+d)a b + c d + * (3 ) Verwenden Sie einen gewöhnlichen Stapel, um einen Stapel mit der -Methode zu implementieren.

Idee:

Verwenden Sie zwei Stapel, um Daten speichern, von denen einer den Namen trägt und speziell zum Speichern verwendet wird. Daten, ein anderer mit dem Namen min, werden speziell zum Speichern der kleinsten Daten im Stapel verwendet. Halten Sie die Anzahl der Elemente in den beiden Stapeln immer gleich. Vergleichen Sie beim Verschieben des Stapels die Größe des verschobenen Elements mit dem obersten Element des Stapels. Wenn es kleiner als das oberste Element des Stapels ist, verschieben Sie es direkt auf den Stapel kopieren, andernfalls das oberste Element des Stapels kopieren und auf den Stapel schieben. Auf diese Weise ist das oberste Element des Stapels von immer der Mindestwert.

function isOperator(str) {
  return ['+', '-', '*', '/'].includes(str);
}
// 逆波兰表达式计算
function clacExp(exp) {
  const stack = new Stack();
  for (let i = 0; i <p><strong>3. Warteschlange</strong><code>dataStack</code><code>minStack</code><code>minStack</code>3.1 Warteschlangendatenstruktur<code>minStack</code></p>Die Warteschlange folgt dem First-In-First-Out (auch FIFO). bekannt als „Wer zuerst kommt, mahlt zuerst“ (eine geordnete Reihe von Dienstleistungsgegenständen). Die Warteschlange fügt am Ende neue Elemente hinzu und entfernt Elemente am oberen Ende. Das zuletzt hinzugefügte Element muss am Ende der Warteschlange eingereiht werden<p><strong></strong></p><p><strong>Analogie: Einkaufswarteschlange im täglichen Leben</strong></p>3.2 Implementierung der Warteschlange<p><span class="img-wrap">Die folgenden Methoden werden üblicherweise in normalen Warteschlangen verwendet: <img src="/static/imghw/default1.png" data-src="https://img.php.cn//upload/image/578/667/838/1547602503534750.png" class="lazy" title="1547602503534750.png" alt="Algorithmusanalyse von Stack und Queue in JavaScript"></span></p><p></p>Einen (oder mehrere) neue Artikel am Ende der Warteschlange hinzufügen <h3></h3><p> </p>

Entfernen Sie das erste Element der Warteschlange (d. h. den Anfang der Warteschlange) und geben Sie das entfernte Element zurück.

• enqueue

Geben Sie das erste Element von zurück das Warteschlangenelement, die Warteschlange nimmt keine Änderungen vor

• dequeue

Gibt das letzte Element der Warteschlange zurück, die Warteschlange nimmt keine Änderungen vor

• 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();
  };
};

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

Das obige ist der detaillierte Inhalt vonAlgorithmusanalyse von Stack und Queue in JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!