Stack heeft slechts één uiteinde open om de gegevenselementen aan de andere kant te duwen en te laten verschijnen. Wachtrij heeft beide uiteinden open voor het in wachtrij plaatsen en uit de wacht halen van de gegevenselementen.
Stack en wachtrij zijn de datastructuren die worden gebruikt voor het opslaan van gegevenselementen en zijn feitelijk gebaseerd op een equivalent in de echte wereld. De stapel is bijvoorbeeld een stapel CD's waar je een CD uit kunt nemen en erin kunt leggen via de bovenkant van de stapel CD's. Op dezelfde manier is de wachtrij een wachtrij voor Theatre-tickets waarbij de persoon die op de eerste plaats staat, dwz aan de voorkant van de wachtrij, als eerste wordt geserveerd en de nieuwe persoon aankomt achter in de wachtrij verschijnt (achterkant van de wachtrij).
Vergelijkingstabel
| Basis voor vergelijking | stack | Wachtrij |
|---|---|---|
| Werkend principe | LIFO (Last in First out) | FIFO (First in First out) |
| Structuur | Hetzelfde uiteinde wordt gebruikt om elementen in te voegen en te verwijderen. | Het ene uiteinde wordt gebruikt voor het invoegen, dat wil zeggen het achterste uiteinde en een ander uiteinde wordt gebruikt voor het verwijderen van elementen, dat wil zeggen voorste uiteinde. |
| Aantal gebruikte wijzers | een | Twee (in eenvoudige wachtrij) |
| Operaties uitgevoerd | Push en pop | In wachtrij plaatsen en uitzetten |
| Onderzoek van lege staat | Top == -1 | Voorkant == -1 || Voorkant == Achterkant + 1 |
| Onderzoek van de volledige toestand | Boven == Max - 1 | Achterkant == Max - 1 |
| varianten | Het heeft geen varianten. | Het heeft varianten zoals circulaire wachtrij, wachtrij met prioriteit, wachtrij met dubbele wachtrij. |
| Implementatie | eenvoudiger | Comparatief complex |
Definitie van Stack
Een stapel is een niet-primitieve lineaire gegevensstructuur. Het is een geordende lijst waarin het nieuwe item wordt toegevoegd en het bestaande element wordt verwijderd uit slechts één uiteinde, genoemd als de bovenkant van de stapel (TOS). Omdat alle verwijderingen en invoegingen in een stapel vanaf de bovenkant van de stapel worden gedaan, zal het laatst toegevoegde element het eerste element zijn dat van de stapel wordt verwijderd. Dat is de reden waarom stack Last-in-First-out (LIFO) type lijst wordt genoemd.
Merk op dat het element dat vaak in de stapel wordt benaderd, het bovenste element is, terwijl het laatste beschikbare element zich onderaan de stapel bevindt.
Voorbeeld
Sommigen van jullie kunnen koekjes eten (of Poppins). Als u aanneemt, is slechts één zijde van het deksel gescheurd en worden koekjes één voor één uitgenomen. Dit wordt knallen genoemd en op dezelfde manier, als je een tijdje wat koekjes wilt bewaren, zul je ze terug in het pakket stoppen door hetzelfde gescheurde uiteinde dat duwen wordt genoemd.
Definitie van wachtrij
Een wachtrij is een lineaire gegevensstructuur die voorkomt in de categorie van het niet-primitieve type. Het is een verzameling van hetzelfde type elementen. De toevoeging van nieuwe elementen vindt plaats aan de ene kant, de achterkant genaamd. Evenzo vindt het verwijderen van de bestaande elementen plaats aan de andere kant, de Front-end, en het is logisch gezien een FIFO-lijst (First in first out).
Voorbeeld
In ons dagelijks leven komen we veel situaties tegen waar we op de gewenste service wachten, daar moeten we in de wachtrij komen voor onze beurt om onderhoud te krijgen. Deze wachtrij kan worden gezien als een wachtrij.
Belangrijkste verschillen tussen stapel en wachtrij
- Stack volgt het LIFO-mechanisme aan de andere kant Wachtrij volgt FIFO-mechanisme om elementen toe te voegen en te verwijderen.
- In een stapel wordt hetzelfde uiteinde gebruikt om de elementen in te voegen en te verwijderen. Integendeel, in de wachtrij worden twee verschillende einden gebruikt om de elementen in te voegen en te verwijderen.
- Omdat Stack slechts één open uiteinde heeft, is dit de reden dat er slechts één aanwijzer wordt gebruikt om naar de bovenkant van de stapel te verwijzen. Maar de wachtrij gebruikt twee wijzers om naar voren en naar de achterkant van de wachtrij te verwijzen.
- Stack voert twee bewerkingen uit die bekend staan als push en pop terwijl ze in de wachtrij staan. Dit staat bekend als wachtrijen en uitzetten.
- De implementatie van stacks is eenvoudiger terwijl de implementatie van de wachtrij lastig is.
- Wachtrij heeft varianten zoals circulaire wachtrij, wachtrij met prioriteit, wachtrij met dubbele wachtrij, enz. Stack heeft daarentegen geen varianten.
Stack-implementatie
De stapel kan op twee manieren worden toegepast:
- Statische implementatie maakt gebruik van arrays om een stapel te maken. Statische implementatie is echter een moeiteloze techniek, maar is geen flexibele manier van creëren, omdat de verklaring van de grootte van de stapel moet worden gedaan tijdens het ontwerpen van het programma, daarna kan de grootte niet worden gevarieerd. Bovendien is statische implementatie niet erg efficiënt met betrekking tot geheugengebruik. Aangezien een array (voor het implementeren van stack) wordt gedeclareerd vóór het begin van de bewerking (tijdens het ontwerp van het programma). Als nu het aantal te sorteren elementen in de stapel erg klein is, wordt het statisch toegewezen geheugen verspild. Aan de andere kant kunnen we, als er meer elementen in de stapel worden opgeslagen, de grootte van de array niet kunnen wijzigen om de capaciteit ervan te vergroten, zodat er ruimte is voor nieuwe elementen.
- Dynamische implementatie wordt ook wel gekoppelde lijstweergave genoemd en gebruikt aanwijzers om het stapeltype van gegevensstructuur te implementeren.
Wachtrij-implementatie
Wachtrij kan op twee manieren worden geïmplementeerd:
- Statische implementatie : als een wachtrij wordt geïmplementeerd met behulp van arrays, moet het exacte aantal elementen dat we in de wachtrij willen opslaan, vooraf worden gegarandeerd, omdat de grootte van de array moet worden gedeclareerd tijdens het ontwerp of voordat de verwerking begint. In dit geval wordt het begin van de array de voorkant van de wachtrij en de laatste locatie van de array fungeert als de achterkant van de wachtrij. De volgende relatie geeft de volledige elementen in de wachtrij wanneer geïmplementeerd met arrays:
voor - achter + 1
Als "rear <front" dan zal er geen element in de wachtrij staan of zal de wachtrij altijd leeg zijn. - Dynamische implementatie : het implementeren van wachtrijen met pointers, het grootste nadeel is dat een knooppunt in een gekoppelde weergave meer geheugenruimte verbruikt dan een overeenkomstig element in de array-representatie. Aangezien er in elk knooppunt ten minste twee velden zijn, één voor het gegevensveld en andere om het adres van het volgende knooppunt op te slaan, terwijl in gekoppelde weergave alleen een gegevensveld aanwezig is. De verdienste van het gebruik van de gekoppelde weergave wordt duidelijk wanneer het nodig is om een element in te voegen of te verwijderen in het midden van een groep andere elementen.
Operaties op stapel
De basisbewerkingen die op de stapel kunnen worden uitgevoerd, zijn als volgt:
- PUSH : wanneer een nieuw element aan de bovenkant van de stapel wordt toegevoegd, wordt dit de PUSH-bewerking genoemd. Door een element in de stapel te duwen, wordt het element aangeroepen, omdat het nieuwe element bovenaan wordt ingevoegd. Na elke drukhandeling wordt de bovenkant met één verhoogd. Als de array vol is en er geen nieuw element kan worden toegevoegd, wordt dit de STACK-FULL-conditie of STACK OVERFLOW genoemd. DUSBEDIENING - functie in C:
Overwegen dat stack wordt gedeclareerd alsint 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 : wanneer een element van de bovenkant van de stapel wordt verwijderd, staat dit bekend als POP-bewerking. De stapel wordt met één verlaagd, na elke popbewerking. Als er geen element meer op de stapel staat en de pop wordt uitgevoerd, resulteert dit in de STACK UNDERFLOW-conditie, wat betekent dat je stapel leeg is. POP-OPERATIE - functies in C:
Overwegen dat stack wordt gedeclareerd alsint 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");}}
Operaties in een wachtrij
De basisbewerkingen die in de wachtrij kunnen worden uitgevoerd, zijn:
- Enqueue : om een element in een wachtrij in te voegen. Bewonderende bewerkingsfunctie in C:
Wachtrij wordt gedeclareerd alsint 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") ;}} - Wachtrij : om een element uit de wachtrij te verwijderen. Afleidende bedieningsfunctie in C:
Wachtrij wordt gedeclareerd alsint 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") ;}}
Toepassingen van Stack
- Parsing in een compiler.
- Java virtuele machine.
- Ongedaan maken in een tekstverwerker.
- Terugknop in een webbrowser.
- PostScript-taal voor printers.
- Functieaanroepen implementeren in een compiler.
Toepassingen van wachtrij
- Gegevensbuffers
- Asynchrone gegevensoverdracht (bestands-IO, leidingen, sockets).
- Toewijzen van aanvragen voor een gedeelde bron (printer, processor).
- Verkeersanalyse.
- Bepaal het aantal kassiers in een supermarkt.
Conclusie
Stapel en wachtrij zijn lineaire gegevensstructuren die verschillen op bepaalde manieren, zoals werkmechanisme, structuur, implementatie, varianten maar beide worden gebruikt voor het opslaan van de elementen in de lijst en het uitvoeren van bewerkingen in de lijst, zoals optellen en verwijderen van de elementen. Hoewel er enkele beperkingen zijn aan de eenvoudige wachtrij die wordt terugverdiend door andere soorten wachtrijen te gebruiken.
