Inhalt

• Vergleichstabelle
• Definition von Stapel
• Beispiel
• Definition von Warteschlange
• Beispiel
• Stack-Implementierung
• Implementierung der Warteschlange
• Operationen auf Stapel
• Operationen in einer Warteschlange
• Anwendungen des Stapels
• Anwendungen der Warteschlange
• Fazit

Stack und Queue sind beide nicht-primitive Datenstrukturen. Die Hauptunterschiede zwischen Stapel und Warteschlange bestehen darin, dass der Stapel die LIFO-Methode (last in first out) verwendet, um auf Datenelemente zuzugreifen und diese hinzuzufügen, während die Warteschlange die FIFO-Methode (first in first out) verwendet, um auf Datenelemente zuzugreifen und Datenelemente hinzuzufügen.

Im Stapel ist nur ein Ende zum Verschieben und Platzieren der Datenelemente offen. In der Warteschlange sind beide Enden zum Ein- und Ausreihen der Datenelemente offen.

Stapel und Warteschlange sind die Datenstrukturen, die zum Speichern von Datenelementen verwendet werden, und basieren tatsächlich auf einem realen Äquivalent. Beispielsweise handelt es sich bei dem Stapel um einen Stapel von CDs, auf denen Sie CDs herausnehmen und über den Stapel von CDs einlegen können. In ähnlicher Weise ist die Warteschlange eine Warteschlange für Theaterkarten, in der die Person, die an erster Stelle steht, d. H. Die Vorderseite der Warteschlange, zuerst bedient wird und die neue ankommende Person hinten in der Warteschlange (hinteres Ende der Warteschlange) erscheint.

1. Vergleichstabelle
2. Definition
3. Hauptunterschiede
4. Implementierung
5. Operationen
6. Anwendungen
7. Fazit

Vergleichstabelle

Vergleichsbasis	Stapel	Warteschlange
Arbeitsprinzip	LIFO (Last in First out)	FIFO (First in First out)
Struktur	Das gleiche Ende wird zum Einfügen und Löschen von Elementen verwendet.	Ein Ende wird zum Einfügen verwendet, d. H. Das hintere Ende und ein anderes Ende wird zum Löschen von Elementen verwendet, d. H. Das vordere Ende.
Anzahl der verwendeten Zeiger	Ein	Zwei (im einfachen Warteschlangenkoffer)
Operationen durchgeführt	Push and Pop	Enqueue und Dequeue
Prüfung des leeren Zustands	Oben == -1	Vorne == -1 || Vorne == Hinten + 1
Prüfung des vollständigen Zustands	Oben == Max - 1	Hinten == Max - 1
Varianten	Es gibt keine Varianten.	Es hat Varianten wie zirkuläre Warteschlange, Prioritätswarteschlange, doppelt beendete Warteschlange.
Implementierung	Einfacher	Vergleichsweise komplex

Definition von Stapel

Ein Stapel ist eine nicht-primitive lineare Datenstruktur. Hierbei handelt es sich um eine geordnete Liste, in der das neue Element hinzugefügt und vorhandene Elemente nur an einem Ende gelöscht werden. Dies wird als oberste Ebene des Stapels (Top of the Stack, TOS) bezeichnet. Da das Löschen und Einfügen in einen Stapel von oben erfolgt, wird das zuletzt hinzugefügte Element als erstes aus dem Stapel entfernt. Aus diesem Grund wird der Stapel als LIFO-Listentyp (Last-in-First-out) bezeichnet.

Beachten Sie, dass das Element, auf das häufig im Stapel zugegriffen wird, das oberste Element ist, während sich das letzte verfügbare Element im unteren Bereich des Stapels befindet.

Beispiel

Einige von Ihnen können Kekse (oder Poppins) essen. Wenn Sie davon ausgehen, dass nur eine Seite der Abdeckung zerrissen ist, werden die Kekse nacheinander herausgenommen. Dies nennt man Knallen, und wenn Sie einige Kekse später für einige Zeit aufbewahren möchten, werden Sie sie durch dasselbe zerrissene Ende in die Packung zurücklegen, das auch als Schieben bezeichnet wird.

Definition von Warteschlange

Eine Warteschlange ist eine lineare Datenstruktur, die in die Kategorie des nicht-primitiven Typs fällt. Es ist eine Sammlung ähnlicher Elemente. Das Hinzufügen neuer Elemente erfolgt an einem Ende, das als hinteres Ende bezeichnet wird. In ähnlicher Weise erfolgt das Löschen der vorhandenen Elemente am anderen Ende, das als Front-End bezeichnet wird, und es handelt sich logischerweise um einen FIFO-Listentyp (First in first out).

Beispiel

In unserem täglichen Leben stoßen wir auf viele Situationen, in denen wir auf den gewünschten Service warten müssen. Dort müssen wir in die Warteschlange treten, bis wir an der Reihe sind, um gewartet zu werden. Diese Warteschlange kann als Warteschlange angesehen werden.

1. Stack follows LIFO-Mechanismus auf der anderen Seite Queue follows FIFO-Mechanismus zum Hinzufügen und Entfernen von Elementen.
2. In einem Stapel wird dasselbe Ende zum Einfügen und Löschen der Elemente verwendet. Im Gegensatz dazu werden in der Warteschlange zwei verschiedene Enden verwendet, um die Elemente einzufügen und zu löschen.
3. Da Stapel nur ein offenes Ende haben, wird nur ein Zeiger verwendet, um auf die Oberseite des Stapels zu verweisen. Die Warteschlange verwendet jedoch zwei Zeiger, um auf das vordere und das hintere Ende der Warteschlange zu verweisen.
4. Stack führt zwei Operationen aus, die als Push und Pop bezeichnet werden, während es in der Warteschlange als Enqueue und Dequeue bezeichnet wird.
5. Die Implementierung von Stacks ist einfacher, während die Implementierung von Warteschlangen schwierig ist.
6. Die Warteschlange verfügt über Varianten wie zirkuläre Warteschlange, Prioritätswarteschlange, Warteschlange mit doppeltem Ende usw. Im Gegensatz dazu verfügt der Stapel über keine Varianten.

Stack-Implementierung

Der Stapel kann auf zwei Arten angewendet werden:

1. Statische Implementierung Erstellt mithilfe von Arrays einen Stapel. Die statische Implementierung ist zwar eine mühelose Technik, stellt jedoch keine flexible Art der Erstellung dar, da die Angabe der Größe des Stapels während der Programmgestaltung erfolgen muss. Danach kann die Größe nicht mehr geändert werden. Darüber hinaus ist die statische Implementierung hinsichtlich der Speichernutzung nicht sehr effizient. Da ein Array (zur Implementierung des Stacks) vor dem Start der Operation (zur Programmentwurfszeit) deklariert wird. Wenn nun die Anzahl der zu sortierenden Elemente im Stapel sehr gering ist, wird der statisch zugewiesene Speicher verschwendet. Wenn jedoch mehr Elemente im Stapel gespeichert werden sollen, können wir die Größe des Arrays nicht ändern, um dessen Kapazität zu erhöhen, sodass neue Elemente darin Platz finden.
2. Dynamische Implementierung wird auch als verknüpfte Listendarstellung bezeichnet und verwendet Zeiger zum Implementieren des Stapeltyps der Datenstruktur.

Implementierung der Warteschlange

Queue kann auf zwei Arten implementiert werden:

1. Statische Implementierung: Wenn eine Warteschlange mithilfe von Arrays implementiert wird, muss die genaue Anzahl der Elemente, die in der Warteschlange gespeichert werden sollen, vorher sichergestellt werden, da die Größe des Arrays zur Entwurfszeit oder vor Beginn der Verarbeitung deklariert werden muss. In diesem Fall wird der Anfang des Arrays zur Vorderseite der Warteschlange und die letzte Position des Arrays zur Rückseite der Warteschlange. Die folgende Beziehung gibt an, dass die gesamten Elemente in der Warteschlange vorhanden sind, wenn sie mithilfe von Arrays implementiert werden:
   vorne - hinten + 1
   Wenn „hinten <vorne“, befindet sich kein Element in der Warteschlange oder die Warteschlange ist immer leer.
2. Dynamische Implementierung: Beim Implementieren von Warteschlangen mithilfe von Zeigern besteht der Hauptnachteil darin, dass ein Knoten in einer verknüpften Darstellung mehr Speicherplatz beansprucht als ein entsprechendes Element in der Array-Darstellung. Da in jedem Knoten mindestens zwei Felder vorhanden sind, eines für das Datenfeld und eines zum Speichern der Adresse des nächsten Knotens, während in der verknüpften Darstellung nur das Datenfeld vorhanden ist. Der Nutzen der verknüpften Darstellung wird deutlich, wenn ein Element in der Mitte einer Gruppe anderer Elemente eingefügt oder gelöscht werden muss.

Operationen auf Stapel

Die grundlegenden Operationen, die auf dem Stapel ausgeführt werden können, lauten wie folgt:

1. DRÜCKEN: Wenn ein neues Element am Anfang des Stapels hinzugefügt wird, wird dies als PUSH-Operation bezeichnet. Wenn Sie ein Element in den Stapel schieben, wird das Element hinzugefügt, da das neue Element oben eingefügt wird. Nach jedem Druckvorgang wird das Verdeck um eins erhöht. Wenn das Array voll ist und kein neues Element hinzugefügt werden kann, heißt es STACK-FULL-Bedingung oder STACK OVERFLOW. DRÜCKEN - Funktion in C:
   Berücksichtigender Stack wird als deklariert
   int stack, top = -1;
nichtig drücken ()
{
int item;
if (top <4)
{
f ("Nummer eingeben");
scannen ("% d", & item);
top = top + 1;
stack = item;
}
sonst
{
f ("Stapel ist voll");
}
}
2. POP: Wenn ein Element oben im Stapel gelöscht wird, spricht man von einer POP-Operation. Der Stapel wird nach jeder Pop-Operation um eins verringert. Wenn sich kein Element mehr auf dem Stapel befindet und das Popup ausgeführt wird, führt dies zu der Bedingung STACK UNDERFLOW, was bedeutet, dass Ihr Stapel leer ist. POP-BETRIEB - Funktionen in C:
   Berücksichtigender Stack wird als deklariert
   int stack, top = -1;
void pop ()
{
int item;
if (top> = 4)
{
item = stack;
top = top - 1;
f ("Die gelöschte Nummer ist =% d", Element);
}
sonst
{
f ("Stapel ist leer");
}
}

Operationen in einer Warteschlange

Die grundlegenden Operationen, die für die Warteschlange ausgeführt werden können, sind:

1. Enqueue: So fügen Sie ein Element in eine Warteschlange ein:
   Warteschlange wird als deklariert
   int queue, Front = -1 und Rear = -1;
void add ()
{
int item;
if (hinten <4)
{
f ("Nummer eingeben");
scannen ("% d", & item);
if (front == -1)
{
front = 0;
hinten = 0;
}
sonst
{
hinten = hinten + 1;
}
Warteschlange = Element;
}
sonst
{
f ("Warteschlange ist voll");
}
}

2. Dequeue: So löschen Sie ein Element aus der Warteschlange:
   Warteschlange wird als deklariert
   int queue, Front = -1 und Rear = -1;
nichtig löschen ()
{
int item;
if (front! = -1)
{
item = queue;
if (vorne == hinten)
{
front = -1;
hinten = -1;
}
sonst
{
front = front + 1;
f ("Die gelöschte Nummer ist =% d", Element);
}
}
sonst
{
f ("Warteschlange ist leer");
}
}

Anwendungen des Stapels

• Parsing in einem Compiler.
• Java virtuelle Maschine.
• Rückgängig machen in einem Textverarbeitungsprogramm.
• Zurück-Schaltfläche in einem Webbrowser.
• PostScript-Sprache für Ers.
• Funktionsaufrufe in einem Compiler implementieren.

Anwendungen der Warteschlange

• Datenpuffer
• Asynchrone Datenübertragung (Datei-E / A, Pipes, Sockets).
• Zuweisen von Anforderungen zu einer freigegebenen Ressource (äh, Prozessor).
• Verkehrsanalyse.
• Bestimmen Sie die Anzahl der Kassierer in einem Supermarkt.

Fazit

Stapel und Warteschlange sind lineare Datenstrukturen, die sich in bestimmten Punkten wie Arbeitsmechanismus, Struktur, Implementierung und Varianten unterscheiden. Beide werden jedoch zum Speichern der Elemente in der Liste und zum Ausführen von Operationen in der Liste wie Hinzufügen und Löschen der Elemente verwendet. Die einfache Warteschlange weist zwar einige Einschränkungen auf, die durch die Verwendung anderer Arten von Warteschlangen behoben werden.