Blog

Jun 17, 2023

FIFO vs. LIFO: 4 Unterschiede

FIFO und LIFO sind zwei Arten von Datenstrukturen, die häufig in der Programmierung verwendet werden.

FIFO und LIFO sind zwei Arten von Datenstrukturen, die häufig in der Programmierung verwendet werden.

LIFO vs. FIFO in der Programmierung

Quelle: LinkedInÖffnet ein neues Fenster

LIFO steht für „Last In, First Out“ und verwendet eine Stapeldatenstruktur. In einer LIFO-Datenstruktur wird das neueste dem Stapel hinzugefügte Element zuerst verarbeitet. Andererseits steht FIFO für „First In, First Out“ und verwendet eine Warteschlangendatenstruktur. In einer FIFO-Datenstruktur wird das erste der Warteschlange hinzugefügte Element zuerst verarbeitet.

Die First-In-First-Out-Datenstruktur wird üblicherweise in der Programmierung als Methode zur Verwaltung und Bearbeitung von Datenelementen in einem Computersystem verwendet. Wie der Name schon sagt, priorisiert FIFO Prozesse, die „First In“ sind, was bedeutet, dass es zuerst das Element anspricht, das in das System gelangt ist, und zwar vor allen anderen.

FIFO nutzt eine Datenstruktur vom Typ Warteschlange, bei der das älteste Element vorne bleibt und auf die bevorzugte Verarbeitung wartet. Stellen Sie sich FIFO als „Wer zuerst kommt, mahlt zuerst“ für Programmierelemente vor, wie eine Kassenschlange im Supermarkt, bei der die erste Person in der Schlange zuerst bedient wird.

Die von FIFO verwendete Datenstruktur vom Typ Warteschlange ist eine einfache und intuitive Methode zur Datenverarbeitung und wird in vielen Anwendungen verwendet. Es eignet sich für Anwendungsfälle, in denen die Verarbeitung einer großen Anzahl von Anfragen erforderlich ist, da diese Anfragen in der Reihenfolge ihres Eingangs verarbeitet werden können und Arbeitsabläufe vermieden werden. Da die älteste Anfrage zuerst verarbeitet wird, gilt FIFO als „faire“ Methode zur Datenverarbeitung.

Im FIFO werden Elemente mit der Operation „enqueue“ am Ende der Warteschlange hinzugefügt und das erste Element wird mit der Operation „dequeue“ zur Verarbeitung entfernt. Das Ein- und Ausreihen im FIFO kann als ein Förderband dargestellt werden, bei dem Gegenstände an einem Ende hinzugefügt und am anderen Ende entnommen werden.

Ein wesentlicher Vorteil der Verwendung von FIFO ist seine Einfachheit. Es handelt sich um eine unkomplizierte und leicht verständliche Datenstruktur, die in vielen Programmiersprachen verwendet wird. Ein weiterer Vorteil von FIFO ist seine Eignung für Anwendungen, bei denen Datenelemente in einer strengen Reihenfolge verarbeitet werden müssen. Beispielsweise möchten Sie in einer Druckerwarteschlange die Druckanforderungen in der Reihenfolge ihres Eingangs verarbeiten. FIFO stellt sicher, dass die älteste Druckanforderung zuerst verarbeitet wird.

Mehr sehen: Was ist eine Ursachenanalyse? Arbeiten, Vorlagen und Beispiele

Die Last-In-First-Out-Datenverarbeitungsmethode wird auch häufig in der Programmierung verwendet. Bei dieser Methode verarbeitet das System zuerst den neuesten bzw. „jüngsten“ Eintrag. LIFO kommt häufig in Fällen vor, in denen der letzte Dateneintrag der wichtigste ist – denken Sie an Undo-Redo-Vorgänge oder eine Internet-Verlaufsliste.

Das Grundprinzip von LIFO besteht darin, dass das zuletzt gespeicherte Element als erstes verarbeitet wird. Neuere Elemente werden über älteren platziert und die „frischesten“ werden zur Verarbeitung von oben entfernt. Da der Eingang und der Ausgang für die Daten identisch sind, wird das älteste Element, das als erstes auf die Operation gestoßen ist, als letztes verarbeitet, da es am unteren Ende des Stapels verbleibt.

Stellen Sie sich den LIFO-Stapel als einen Tellerstapel vor, bei dem die zuletzt oben hinzugefügten Teller auch zuerst von oben entnommen werden. Dies steht in scharfem Gegensatz zu der im FIFO verwendeten Datenstruktur vom Typ Warteschlange, bei der das erste Element, das in die Warteschlange gelangt, auch als erstes verarbeitet wird. LIFO-Elemente werden mithilfe einer Push-Operation am Ende des Stapels hinzugefügt. Das neueste Element wird mit einer Pop-Operation verarbeitet.

LIFO eignet sich besser für Anwendungen, die sich nicht auf die Reihenfolge der Datenverarbeitung konzentrieren und stattdessen mehr Wert auf die Aktualität der Daten legen. Webbrowser ermöglichen es Benutzern beispielsweise, mithilfe der Schaltflächen „Zurück“ und „Vorwärts“ zwischen den besuchten Webseiten hin und her zu navigieren. Diese Funktion verwendet eine LIFO-Datenstruktur, um den Verlauf der besuchten Webseiten zu speichern. Sobald auf die Schaltfläche „Zurück“ getippt wird, ruft der Browser die zuletzt besuchte Webseite oben im Datenstapel ab und leitet den Benutzer dorthin zurück.

Mehr sehen: Was ist ETL (Extrahieren, Transformieren, Laden)? Bedeutung, Prozess und Werkzeuge

Lassen Sie uns die wichtigsten Unterschiede zwischen den FIFO- und LIFO-Methoden genauer verstehen.

Diese Datenstruktur folgt dem FIFO-Prinzip, was bedeutet, dass neue Entitäten am Ende der Warteschlange hinzugefügt werden und die Entitäten am Anfang der Warteschlange zuerst verarbeitet werden.

Wie eine normale Menschenschlange an einem Kinokassenschalter oder einer Supermarktkasse hat die Datenstruktur vom Typ „Warteschlange“ zwei Enden. Ein Ende ist die Vorderseite, wo Elemente zur Verarbeitung entfernt werden. Das andere Ende ist die Rückseite, wo neue Entitäten hinzugefügt werden.

Wenn eine neue Entität am Ende der Warteschlange hinzugefügt werden muss, wird der „Enqueue“-Prozess ausgeführt. Wenn andererseits eine Entität zur Verarbeitung vom Anfang der Warteschlange entfernt werden muss, wird der Prozess „Entfernen“ ausgeführt.

Eine weitere Operation, die in Datenstrukturen vom Typ Warteschlange ausgeführt wird, ist als „Peek“ bekannt, bei der die Entität am Anfang der Warteschlange angezeigt wird, ohne dass sie entfernt wird.

Diese Datenstruktur wird in vielen Computersystemen zum Speichern und Verarbeiten von Daten verwendet. Beispielsweise verwenden Netzwerk-Switches, Bridges und Router FIFO, um Datenpakete zu speichern, während sie an ihr Ziel transportiert werden.

Die Warteschlangenimplementierung erfolgt mithilfe unterschiedlicher Datenstrukturen, einschließlich Arrays und verknüpfter Listen. Eine Warteschlange hat keine theoretische Kapazitätsgrenze; In der Praxis können „begrenzte Warteschlangen“ jedoch eine feste Kapazität aufweisen.

Es gibt zahlreiche effiziente Implementierungen von FIFO-Warteschlangen. Sie können Prozesse zum Hinzufügen und Entfernen von Entitäten in konstanter Zeit durchführen (O(1)). Einige Programmiersprachen bieten integrierte Warteschlangenunterstützung. zum Beispiel die „queue“-Schnittstelle in der Java-Bibliothek und die „queue“-Vorlagenklasse in der C++-Standardvorlagenbibliothek.

Während der erstere Vorgang ein Element zur Sammlung hinzufügt, entfernt der letztere das zuletzt hinzugefügte, noch zu entfernende Element. In einem Stapel wird die LIFO-Reihenfolge der Elemente eingehalten.

Genau wie bei einem realen Stapel physischer Gegenstände, die übereinander angeordnet sind (z. B. ein Stapel Teller), müssen die Datenelemente oben vor denen entfernt werden, die sich tiefer im Stapel befinden.

Wie eine Datenstruktur vom Typ Warteschlange ist auch ein Stapel linear. Abstrakter kann man es als eine sequentielle Sammlung betrachten, bei der die Push- und Pop-Vorgänge nur an einem Ende der Struktur stattfinden – der „Oberseite“ des Stapels.

Diese Datenstruktur ermöglicht die Implementierung eines Stapels als einfach verknüpfte Liste und als Zeiger auf das oberste Element.

In einigen Implementierungen verfügen Stacks über mehr Operationen als das einfache „Push“ und „Pop“. Beispielsweise ermöglicht die „Top of Stack“-Operation, ähnlich der „Peek“-Operation in einer Warteschlange, die Beobachtung des obersten Elements, ohne es aus dem Stapel zu entfernen.

Wenn ein leerer Stapel angetroffen wird, tritt bei der Ausführung der „Top of Stack“- oder „Pop“-Operationen eine Unterlaufbedingung auf. Darüber hinaus gibt es Implementierungen, mit denen überprüft werden kann, ob der Stapel leer ist und wie groß der Stapel ist.

Die Stack-Implementierung kann entweder über eine verknüpfte Liste oder ein Array erfolgen. Stapel können als Sonderfälle von Listen angesehen werden und werden nicht durch die Implementierung, sondern durch die Schnittstelle identifiziert – der Benutzer kann Elemente nur mit einigen anderen Hilfsoperationen in die verknüpfte Liste oder das Array verschieben oder einfügen.

Eine Schlüsselanwendung von FIFO istFestplattenplanungsalgorithmenDabei verwenden Festplattencontroller FIFO, um die Reihenfolge der Prozessausführung festzulegen.

Darüber hinaus nutzen zahlreiche Datenstrukturen FIFO zur Datenverarbeitung. Die Hauptstruktur, die FIFO verwendet, ist dieWarteschlange ; andere Varianten nutzen jedoch auch die FIFO-Technik.

FIFO wird auch in verwendetKommunikation und Vernetzung Dabei bleiben Datenpakete mithilfe von FIFO in der erforderlichen Reihenfolge zwischen den Routern. Mit dieser Technik kann der Router die Reihenfolge festlegen, in der Pakete übertragen werden müssen.

Schließlich wird FIFO verwendetBetriebssystemalgorithmen . Prozesse werden in der Reihenfolge ihres Eintreffens nach CPU-Zeit ausgewählt. Wenn beispielsweise mehrere Prozesse auf den CPU-Zugriff warten, werden die früher eingetroffenen Prozesse vom Betriebssystem priorisiert. Dadurch wird sichergestellt, dass alle Prozesse angemessen CPU-Zeit erhalten.

LIFO wird häufig in Datenstrukturen verwendet. DerStapel ist die Hauptdatenstruktur nach dem LIFO-Ansatz. Es wird in mehreren Programmiersprachen zur Datenspeicherung und -verwaltung verwendet. Die Stapeldatenstruktur hat mehrere Anwendungen, einschließlich Ausdrucksauswertung, Speicherverwaltung und Funktionsaufrufe.

LIFO sieht auch Verwendung inSpeicherverwaltung . Beispielsweise nutzt der Stapelspeicherzuweisungsalgorithmus LIFO. Dabei erfolgt die Speicherzuweisung und -freigabe in einer stapelartigen Struktur. Beim Aufruf werden die Daten der Funktion im Stack gespeichert und bei der Rückkehr entfernt.

Eine häufige Anwendung von LIFO ist die'Geschichte' Funktion von Webbrowsern. Wenn ein Benutzer eine Webseite besucht, wird deren URL erfasst und zusammen mit anderen besuchten URLs oben im Stapel hinzugefügt. Sobald die Schaltfläche „Zurück“ gedrückt wird, wird die zuletzt besuchte Webseite vom oberen Rand des Stapels entfernt und dem Benutzer angezeigt.

Ein weiteres Beispiel für LIFO istVorgänge rückgängig machen und wiederholen im Rechnen. Wenn Sie beispielsweise ein Textverarbeitungsprogramm verwenden und eine Formatierungsänderung rückgängig machen möchten, verwenden Sie die Tasten „Strg“ (oder „Befehl“) und „Z“ zusammen. Der vorherige Formatierungsstatus wird dann von der Textverarbeitungssoftware mithilfe einer LIFO-Datenstruktur abgerufen und erneut angewendet. Wenn ein Benutzer gerade eine Datei in den Papierkorb seines Geräts verschoben hat und den Löschvorgang rückgängig machen möchte, tippt er einfach auf die Schaltfläche „Rückgängig“ und die Anwendung ruft die zuletzt gelöschte Datei von oben in der Liste der gelöschten Dateien ab und stellt sie wieder her Datenstapel.

Schließlich verwenden Computernetzwerke LIFO in der „Last-In-First-Out-Warteschlange“. Dies hilft Routern dabei, die Reihenfolge festzulegen, in der Datenpakete zwischen Systemen übertragen werden müssen. Dabei trägt LIFO dazu bei, dass die Datenpakete in einer logischen Reihenfolge beim vorgesehenen Empfänger ankommen.

Ein weiterer Vorteil der FIFO-Methode istfairer Ansatz über alle Prozesse hinweg . Der erste Prozess, der empfangen wird, ist der erste, der ausgeführt wird, gemäß dem Prinzip „Wer zuerst kommt, mahlt zuerst“ (FCFS). Dadurch wird sichergestellt, dass alle Prozesse die gleiche CPU-Auslastung haben und die Möglichkeit einer vorzeitigen Beendigung oder Fehlfunktion minimiert wird.

BezüglichChronologie FIFO sorgt dafür, dass das älteste Element in der Warteschlange bevorzugt verarbeitet wird. Dies wird dadurch erreicht, dass das älteste Element am Anfang der Warteschlange bleibt und ein schneller Zugriff ermöglicht wird.

Da die Notwendigkeit entfällt, das älteste Element zu finden, wird dasAbrufprozess wird effizienter. Die FIFO-Methode eliminiert außerdem die „Wait-and-Hold“-Kriterien und verkürzt so die Datenverarbeitungszeit.

Schließlich gibt es noch den FIFO-AnsatzSpeicherverbrauch behoben . Dies ist ein bemerkenswerter Vorteil, da die Speicherauslastung unabhängig von der Anzahl der ausgeführten Vorgänge konstant bleibt. Dieser Vorteil ist ein Nebenprodukt der Tatsache, dass FIFO keine zusätzlichen Datenstrukturen zur Verwaltung seiner Elemente benötigt.

Beim LIFO-Ansatz wird das zuletzt eingegebene Element bevorzugt verarbeitet. Dies ist besonders nützlich, wenn dieDie meisten neu hinzugefügten Artikel müssen schnell bearbeitet werdenohne dass der Rest des Vorgangs abgeschlossen werden muss.

Schließlich ist LIFO für Anwendungen von Vorteil, bei denen Benutzer Zugriff auf die aktuellsten Informationen benötigenChronologie, wie z. B. Börsenverfolgung oder Finanzdatenanalyse.

Zusätzlich FIFOerlaubt keinen zufälligen Zugriff auf die Elemente . Dadurch wird verhindert, dass die CPU auf alle in der Warteschlange befindlichen Elemente außer dem ersten zugreift, und kann bei bestimmten Prozessen zu Ineffizienz führen, wenn die CPU möglicherweise auf ein bestimmtes Element in der Mitte der Warteschlange zugreifen muss.

Obwohl FIFO für seine Fairness bei der Prozessausführung bekannt ist, ist eskann keine Prozesspriorisierung unterstützen . Dies kann dazu führen, dass kritische Prozesse darauf warten, dass reguläre Prozesse oder Prozesse mit niedrigerer Priorität abgeschlossen werden, was sich auf die Systemeffektivität auswirkt.

Ein weiterer Nachteil von LIFO istInflexibilität ; Für Anwendungen, die einen ausgefeilteren Algorithmus erfordern, ist dies möglicherweise keine effiziente Wahl.

Schließlich ist LIFOnicht effizient in der Speicherverwaltung . Dies liegt daran, dass sich die Speichernutzung in LIFO im Gegensatz zu FIFO (wo der Speicherverbrauch fest ist) mit jedem Vorgang ändert und keine feste Größe für den verbrauchten Speicher bereitgestellt werden kann. Da der Speicherverbrauch für LIFO nicht vorherbestimmt ist, ist die Sicherstellung einer effizienten Ressourcenzuweisung eine Herausforderung.

Mehr sehen: Was ist BDD (Behavior Driven Development)? Bedeutung, Prozess und Beispiele

Der Hauptunterschied zwischen „First In, First Out“ (FIFO) und „Last In, First Out“ (LIFO) in der Programmierung liegt in der Reihenfolge der verarbeiteten Elemente. FIFO verarbeitet das erste Element in der First-Out-Reihenfolge, während LIFO das letzte Element in der First-Out-Reihenfolge verarbeitet.

FIFO ist für Anwendungen vorzuziehen, bei denen die Reihenfolge des Eintreffens von Bedeutung ist und die chronologisch ältesten Daten, wie z. B. die Übertragung von Datenpaketen, wichtiger sind. Umgekehrt wird LIFO für Anwendungen bevorzugt, bei denen die Reihenfolge des Eintreffens weniger wichtig ist und chronologisch neuere Daten von entscheidender Bedeutung sind, wie etwa Funktionsaufrufe und Undo-Redo-Operationen.

In Bezug auf die Datenstrukturen wird FIFO als Warteschlange implementiert, während LIFO als Stapel implementiert wird. Beide Methoden haben Vor- und Nachteile, und die Wahl zwischen ihnen hängt letztendlich von den besonderen Anforderungen der zu entwickelnden Programmieranwendung ab.

Hat Ihnen dieser Artikel dabei geholfen, die wichtigsten Unterschiede zwischen FIFO und LIFO in der Programmierung zu verstehen? Teilen Sie uns Ihre Gedanken auf Facebook, Twitter oder LinkedIn mit!

Bildquelle: Shutterstock

Technischer Schreiber