LIFO oder FIFO? Leitfaden zu Stapeln/Warteschlangen

Setzt Verständnis der Big-O-Notation voraus. Beispiele sind in JavaScript. Informationsreferenzen „Cracking the Coding Interview“ von Gayle Laakmann McDowell

Heute werden wir zwei wesentliche Datenstrukturen untersuchen: Stapel und Warteschlangen. Wir werden uns mit ihren Konzepten und Anwendungsfällen befassen und sie mithilfe klassischer und prototypbasierter Ansätze in JavaScript implementieren.

---

Stapel: Last In, First Out (LIFO)

Stellen Sie sich einen Stapel Pfannkuchen vor – der letzte, den Sie darauf legen, ist der erste, den Sie essen. Genau so funktioniert eine Stapeldatenstruktur. Es folgt dem Last In, First Out (LIFO)-Prinzip.

Schlüsseloperationen

• push(item): Füge ein Element oben auf dem Stapel hinzu
• pop(): Entferne das oberste Element vom Stapel
• peek(): Gibt das oberste Element zurück, ohne es zu entfernen
• isEmpty(): Überprüfen Sie, ob der Stapel leer ist

Anwendungsfälle

Stapel sind besonders nützlich in Szenarien mit:

• Rekursive Algorithmen
• Rückgängig-Mechanismen in Texteditoren

JavaScript-Implementierung

Klassisches OOP

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

  push(element) {
    this.items.push(element);
  }

  pop() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items.pop();
  }

  peek() {
    if (this.isEmpty()) {
      return "Stack is empty";
    }
    return this.items[this.items.length - 1];
  }

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

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

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

Prototypenbasiert

function Stack() {
  this.items = [];
}

Stack.prototype.push = function(element) {
  this.items.push(element);
};

Stack.prototype.pop = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items.pop();
};

Stack.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Stack is empty";
  }
  return this.items[this.items.length - 1];
};

Stack.prototype.isEmpty = function() {
  return this.items.length === 0;
};

Stack.prototype.size = function() {
  return this.items.length;
};

Stack.prototype.clear = function() {
  this.items = [];
};

---

Warteschlangen: First In, First Out (FIFO)

Lassen Sie uns nun unseren Fokus auf Warteschlangen verlagern. Im Gegensatz zu Stapeln folgen Warteschlangen dem First In, First Out (FIFO)-Prinzip. Stellen Sie sich eine Warteschlange an einem Konzertort vor – die erste Person, die ankommt, ist auch die erste, die eintritt.

Schlüsseloperationen

• enqueue(item): Füge ein Element am Ende der Warteschlange hinzu
• dequeue(): Entferne das erste Element aus der Warteschlange
• peek(): Gibt das erste Element zurück, ohne es zu entfernen
• isEmpty(): Überprüfen Sie, ob die Warteschlange leer ist

Anwendungsfälle

Warteschlangen werden häufig verwendet in:

• Breite-First-Suchalgorithmen
• Aufgabenplanung

JavaScript-Implementierung

Klassisches OOP

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.start = newNode;
      this.end = newNode;
    } else {
      this.end.next = newNode;
      this.end = newNode;
    }
    this.size++;
  }

  dequeue() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    const removedData = this.start.data;
    this.start = this.start.next;
    this.size--;
    if (this.isEmpty()) {
      this.end = null;
    }
    return removedData;
  }

  peek() {
    if (this.isEmpty()) {
      return "Queue is empty";
    }
    return this.start.data;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }

  clear() {
    this.start = null;
    this.end = null;
    this.size = 0;
  }
}

Prototypenbasiert

function Node(data) {
  this.data = data;
  this.next = null;
}

function Queue() {
  this.start = null;
  this.end = null;
  this.size = 0;
}

Queue.prototype.enqueue = function(element) {
  const newNode = new Node(element);
  if (this.isEmpty()) {
    this.start = newNode;
    this.end = newNode;
  } else {
    this.end.next = newNode;
    this.end = newNode;
  }
  this.size++;
};

Queue.prototype.dequeue = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  const removedData = this.start.data;
  this.start = this.start.next;
  this.size--;
  if (this.isEmpty()) {
    this.end = null;
  }
  return removedData;
};

Queue.prototype.peek = function() {
  if (this.isEmpty()) {
    return "Queue is empty";
  }
  return this.start.data;
};

Queue.prototype.isEmpty = function() {
  return this.size === 0;
};

Queue.prototype.getSize = function() {
  return this.size;
};

Queue.prototype.clear = function() {
  this.start = null;
  this.end = null;
  this.size = 0;
};

---

Leistungsanalyse

Sowohl Stapel als auch Warteschlangen bieten $O(1)$O(1) Zeitkomplexität für ihre Kernoperationen (Push/Pop für Stacks, Enqueue/Dequeue für Warteschlangen), wenn sie effizient implementiert wird. Dadurch sind sie für ihre spezifischen Anwendungsfälle äußerst leistungsfähig.

Beide bieten elegante Lösungen für viele gängige Programmierprobleme und bilden die Grundlage für komplexere Datenstrukturen und Algorithmen. Durch das Verständnis und die Implementierung dieser Strukturen in JavaScript sind Sie gut gerüstet, um eine Vielzahl von Leetcode-/Algorithmusproblemen anzugehen?.

Das obige ist der detaillierte Inhalt vonLIFO oder FIFO? Leitfaden zu Stapeln/Warteschlangen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!