Der Stapel hat nur ein Ende offen, um die Datenelemente zu verschieben und zu löschen. Auf der anderen Seite hat die Warteschlange beide Enden zum Ein- und Ausreißen der Datenelemente geöffnet.
Stapel und Warteschlange sind die Datenstrukturen, die zum Speichern von Datenelementen verwendet werden, und basieren tatsächlich auf einem realen Äquivalent. Zum Beispiel ist der Stapel ein Stapel von CDs, bei dem Sie die CD durch den oberen Stapel von CDs herausnehmen und in eine CD einlegen können. In ähnlicher Weise ist die Warteschlange eine Warteschlange für Theaterkarten, bei der die Person, die an erster Stelle steht, dh vor der Warteschlange, zuerst bedient wird und die neu ankommende Person an der Rückseite der Warteschlange (hinteres Ende der Warteschlange) erscheint.
Vergleichstabelle
| Basis zum Vergleich | 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, dh das hintere Ende und ein anderes Ende zum Löschen von Elementen, dh das vordere Ende. |
| Anzahl der verwendeten Zeiger | Ein | Zwei (im einfachen Warteschlangenfall) |
| Durchgeführte Operationen | Push und Pop | Enqueue und Dequeue |
| Untersuchung des leeren Zustands | Oben == -1 | Vorne == -1 || Vorne == Hinten + 1 |
| Untersuchung des vollen Zustands | Top == Max - 1 | Hinten == Max - 1 |
| Varianten | Es gibt keine Varianten. | Es gibt Varianten wie z. B. Ringwarteschlange, Prioritätswarteschlange und doppelt beendete Warteschlange. |
| Implementierung | Einfacher | Vergleichsweise komplex |
Definition von Stapel
Ein Stack ist eine nicht-primitive lineare Datenstruktur. Es ist eine geordnete Liste, in der das neue Element hinzugefügt und ein vorhandenes Element nur von einem Ende gelöscht wird. Es wird als Top of the Stack (TOS) bezeichnet. Da das gesamte 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 Stack 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 des Deckels zerrissen ist, werden Kekse einzeln herausgenommen. Dies ist das, was Popping genannt wird, und wenn Sie später einige Kekse aufbewahren möchten, setzen Sie sie wieder in das Pack, und zwar über dasselbe abgerissene Ende. Dies wird Pushing genannt.
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, dem hinteren Ende. In ähnlicher Weise erfolgt das Löschen der vorhandenen Elemente am anderen Ende, das als Front-End bezeichnet wird, und ist logisch ein FIFO-Listentyp (FIFO-Typ).
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 Warteschlange stehen, bis wir an der Reihe sind, um gewartet zu werden. Diese Warteschlange kann als Warteschlange betrachtet werden.
Hauptunterschiede zwischen Stack und Queue
- Stack folgt dem LIFO-Mechanismus, während Queue dem FIFO-Mechanismus zum Hinzufügen und Entfernen von Elementen folgt.
- 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.
- Da Stack nur ein offenes Ende hat, ist dies der Grund dafür, dass nur ein Zeiger verwendet wird, um auf die Oberseite des Stacks zu verweisen. Die Warteschlange verwendet jedoch zwei Zeiger, um auf das vordere und das hintere Ende der Warteschlange zu verweisen.
- Stack führt zwei als Push und Pop bezeichnete Operationen aus, während sich in der Warteschlange Enqueue und Dequeue befinden.
- Die Stapelimplementierung ist einfacher, während die Implementierung der Warteschlange schwierig ist.
- In der Warteschlange gibt es Varianten wie z. B. Ringwarteschlange, Prioritätswarteschlange, doppelt beendete Warteschlange usw. Im Gegensatz dazu hat Stack keine Varianten.
Stack-Implementierung
Der Stapel kann auf zwei Arten angewendet werden:
- Bei der statischen Implementierung werden Arrays zum Erstellen eines Stapels verwendet. Die statische Implementierung ist zwar eine mühelose Technik, jedoch keine flexible Art der Erstellung, da die Deklaration der Stackgröße während des Programmdesigns 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 (zum Implementieren des Stacks) vor dem Start der Operation (zum Zeitpunkt des Programmierens) deklariert wird. Wenn nun die Anzahl der zu sortierenden Elemente im Stack sehr gering ist, wird der statisch zugewiesene Speicher verschwendet. Wenn auf der anderen Seite mehr Elemente im Stack gespeichert werden sollen, können wir die Größe des Arrays nicht ändern, um seine Kapazität zu erhöhen, sodass neue Elemente aufgenommen werden können.
- Die dynamische Implementierung wird auch als verkettete Listendarstellung bezeichnet und verwendet Zeiger, um den Stack-Typ der Datenstruktur zu implementieren.
Warteschlangenimplementierung
Die Warteschlange kann auf zwei Arten implementiert werden:
- Statische Implementierung : Wenn eine Warteschlange mit Arrays implementiert wird, muss die genaue Anzahl der Elemente, die wir in der Warteschlange speichern möchten, vorab 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 fungiert als Rückseite der Warteschlange. Die folgende Beziehung gibt an, dass die gesamten Elemente in der Warteschlange vorhanden sind, wenn sie mit Arrays implementiert werden:
vorne - hinten + 1
Wenn "hinten <vorne", ist kein Element in der Warteschlange oder die Warteschlange ist immer leer. - 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 es in jedem Knoten mindestens zwei Felder gibt, eines für das Datenfeld und ein anderes, um die Adresse des nächsten Knotens zu speichern, während in verknüpfter Darstellung nur ein Datenfeld vorhanden ist. Der Nutzen der Verwendung der verknüpften Repräsentation wird offensichtlich, 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, sind wie folgt:
- PUSH : Wenn ein neues Element am oberen Rand des Stapels hinzugefügt wird, wird dies als PUSH-Operation bezeichnet. Durch Drücken eines Elements im Stapel wird das Hinzufügen des Elements aufgerufen, da das neue Element oben eingefügt wird. Nach jedem Druckvorgang wird der Aufsatz um eins erhöht. Wenn das Array voll ist und kein neues Element hinzugefügt werden kann, wird es als STACK-FULL-Bedingung oder STACK OVERFLOW bezeichnet. PUSH OPERATION - Funktion in C:
Die Berücksichtigung von Stack wird als deklariertint stack [5], top = -1;void push(){int item;if (top < 4){printf ("Enter the number") ;scan ("%d", & item) ;top = top + 1;stack [top] = item;}else{printf (" Stack is full");}} - POP : Wenn ein Element vom oberen Rand des Stapels gelöscht wird, wird es als POP-Vorgang bezeichnet. Der Stapel wird nach jedem Pop-Vorgang um eins verringert. Wenn sich auf dem Stack kein Element mehr befindet und der Popup ausgeführt wird, führt dies zu der STACK UNDERFLOW-Bedingung, was bedeutet, dass Ihr Stack leer ist. POP-OPERATION - Funktionen in C:
Die Berücksichtigung von Stack wird als deklariertint stack [5], top = -1;void pop(){int item;if (top >= 4){item = stack [top];top = top - 1;printf ("Number deleted is = %d", item) ;}else{printf (" Stack is empty");}}
Operationen in einer Warteschlange
Die grundlegenden Operationen, die in der Warteschlange ausgeführt werden können, sind:
- Enqueue : Um ein Element in eine Warteschlange einzufügen. Operation der Warteschlangenoperation in C:
Warteschlange wird als deklariertint queue [5], Front = -1 and rear = -1;void add (){int item;if ( rear < 4){printf ("Enter the number") ;scan ("%d", & item) ;if (front == -1){front =0 ;rear =0 ;}else{rear = rear + 1;}queue [rear] = item ;}else{printf ("Queue is full") ;}} - Dequeue : Um ein Element aus der Warteschlange zu löschen. Operation der Warteschlangenoperation in C:
Warteschlange wird als deklariertint queue [5], Front = -1 and rear = -1;void delete (){int item;if ( front ! = -1){item = queue [ front ] ;if (front == rear){front =-1 ;rear =-1 ;}else{front = front + 1;printf ("Number deleted is = %d", item) ;}}else{printf ("Queue is empty") ;}}
Anwendungen von Stack
- Parsing in einem Compiler.
- Java virtuelle Maschine.
- In einem Textverarbeitungsprogramm rückgängig machen.
- Zurück-Schaltfläche in einem Webbrowser.
- PostScript-Sprache für Drucker.
- Funktionsaufrufe in einem Compiler implementieren.
Anwendungen der Warteschlange
- Datenpuffer
- Asynchrone Datenübertragung (File IO, Pipes, Sockets).
- Zuweisen von Anforderungen auf eine gemeinsam genutzte Ressource (Drucker, Prozessor).
- Verkehrsanalyse.
- Bestimmen Sie die Anzahl der Kassierer in einem Supermarkt.
Fazit
Stack und Queue sind lineare Datenstrukturen, die sich in gewisser Weise unterscheiden, wie Arbeitsmechanismus, Struktur, Implementierung und Varianten. Beide werden zum Speichern der Elemente in der Liste und zum Ausführen von Vorgängen in der Liste verwendet, z. B. Hinzufügen und Löschen der Elemente. Es gibt zwar einige Einschränkungen der einfachen Warteschlange, die mit anderen Warteschlangentypen wiederhergestellt wird.
