Warteschlange
Eine aus Knoten aufgebaute C++-Warteschlange Schritt für Schritt durchgehen.
Alles wird in diesem Browser simuliert; nichts wird an einen Server gesendet.
Werte
Neuen Knoten erstellen
Neuen Knoten erstellen
n_ = 0
Die Warteschlange ist leer
- Gerade hinzugefügt
- Wird gerade entfernt
Schritt 1 / 54
Code
#include <iostream>
using namespace std;
class Nodo { // Ein Knoten enthält die Daten und einen Zeiger auf den nächsten
private: // Private Attribute: nur die Methoden greifen darauf zu
int dato;
Nodo* siguiente;
public:
Nodo(int d) : dato(d), siguiente(nullptr) {}
int getDato() const { return dato; }
Nodo* getSiguiente() const { return siguiente; }
void setDato(int d) { dato = d; }
void setSiguiente(Nodo* s) { siguiente = s; }
};
class Cola {
private: // frente_ verlässt als Nächstes die Schlange, final_ ist der zuletzt Angekommene
Nodo* frente_; // Erster Knoten der Warteschlange
Nodo* final_; // Letzter Knoten der Warteschlange
int n_; // Anzahl der Knoten
public:
Cola() : frente_(nullptr), final_(nullptr), n_(0) {}
// Destructor (no se anima)
~Cola() {
while (frente_ != nullptr) desencolar();
}
void encolar(int valor) { // Hinten einreihen: O(1)
Nodo* nuevo = new Nodo(valor); // Knoten erzeugen
if (final_ == nullptr) { // Ist die Warteschlange leer?
frente_ = final_ = nuevo; // Es ist der einzige Knoten: frente_ und final_ zeigen darauf
} else {
final_->setSiguiente(nuevo); // Der letzte Knoten zeigt auf den neuen
final_ = nuevo; // final_ zeigt jetzt auf den neuen Knoten
}
n_++;
}
void desencolar() { // Vorne entnehmen: O(1)
if (frente_ == nullptr) return; // Leere Warteschlange: nichts zu entfernen
Nodo* temp = frente_; // Vordersten Knoten merken, um ihn freizugeben
frente_ = frente_->getSiguiente(); // frente_ rückt zum nächsten Knoten vor
if (frente_ == nullptr) final_ = nullptr; // Warteschlange ist leer: final_ zeigt auf nichts mehr
delete temp; // Speicher freigeben
n_--;
}
// Muestra la cola del frente al final
void imprimir() const {
cout << "frente ->";
for (Nodo* p = frente_; p != nullptr; p = p->getSiguiente())
cout << " " << p->getDato();
cout << endl;
}
};
int main() {
Cola cola;
cola.encolar(3);
cola.encolar(6);
cola.encolar(9);
cola.imprimir(); // frente -> 3 6 9
cola.desencolar();
cola.imprimir(); // frente -> 6 9
cola.encolar(1);
cola.imprimir(); // frente -> 6 9 1
return 0;
}