Inhoud

• Vergelijkingstabel
• Definitie van Stack
• Voorbeeld
• Definitie van wachtrij
• Voorbeeld
• Stack-implementatie
• Wachtrij-implementatie
• Bewerkingen op stapel
• Bewerkingen in een wachtrij
• Toepassingen van Stack
• Toepassingen van wachtrij
• Gevolgtrekking

Stack en Queue zijn beide niet-primitieve gegevensstructuren. De belangrijkste verschillen tussen stack en wachtrij zijn dat stack de LIFO-methode (last in first out) gebruikt voor toegang tot en toevoegen van gegevenselementen, terwijl Queue de FIFO (First in first out) methode gebruikt voor toegang tot en toevoegen van gegevenselementen.

Stack heeft slechts één uiteinde open voor het duwen en laten knallen van de gegevenselementen aan de andere kant. Wachtrij heeft beide uiteinden open voor het opsporen en verwijderen van de gegevenselementen.

Stack en wachtrij zijn de gegevensstructuren die worden gebruikt voor het opslaan van gegevenselementen en zijn eigenlijk gebaseerd op een equivalent uit de echte wereld. De stapel is bijvoorbeeld een stapel CD's die u kunt verwijderen en in de CD kunt plaatsen via de stapel CD's. Evenzo is de wachtrij een wachtrij voor theaterkaartjes waarbij de persoon die op de eerste plaats staat, d.w.z. de voorkant van de wachtrij het eerst wordt bediend en de nieuwe aankomende persoon achter in de wachtrij verschijnt (achterkant van de wachtrij).

1. Vergelijkingstabel
2. Definitie
3. Belangrijkste verschillen
4. Implementatie
5. Activiteiten
6. toepassingen
7. Gevolgtrekking

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.	Eén uiteinde wordt gebruikt voor het inbrengen, d.w.z. achterste uiteinde en een ander uiteinde wordt gebruikt voor het verwijderen van elementen, d.w.z. voorste uiteinde.
Aantal gebruikte wijzers	een	Twee (in eenvoudige wachtrij)
Operaties uitgevoerd	Push en Pop	Enqueue en dequeue
Onderzoek van lege toestand	Boven == -1	Voor == -1 || Voor == achter + 1
Onderzoek van de volledige staat	Boven == Max - 1	Achter == Max - 1
varianten	Het heeft geen varianten.	Het heeft varianten zoals circulaire wachtrij, prioriteitswachtrij, dubbel beëindigde wachtrij.
Implementatie	eenvoudiger	Relatief complex

Definitie van Stack

Een stapel is een niet-primitieve lineaire gegevensstructuur. Het is een geordende lijst waar het nieuwe item wordt toegevoegd en het bestaande element wordt verwijderd van slechts één uiteinde, genoemd als de top van de stapel (TOS). Omdat het verwijderen en invoegen in een stapel vanaf de bovenkant van de stapel gebeurt, zal het laatst toegevoegde element het eerste zijn dat uit de stapel wordt verwijderd. Dat is de reden waarom stack het type LIFO-lijst (Last-in-First-out) wordt genoemd.

Merk op dat het element dat vaak in de stapel wordt gebruikt het bovenste element is, terwijl het laatst beschikbare element zich onderaan de stapel bevindt.

Voorbeeld

Sommigen van jullie eten koekjes (of Poppins). Als je aanneemt, is slechts één kant van de deksel gescheurd en worden de koekjes één voor één verwijderd. Dit wordt knallen genoemd, en op dezelfde manier, als je wat koekjes later voor een tijdje wilt bewaren, doe je ze terug in de verpakking via 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 vergelijkbare elementen. De toevoeging van nieuwe elementen vindt plaats aan het ene uiteinde genaamd achterste uiteinde. Op dezelfde manier vindt het verwijderen van de bestaande elementen plaats aan het andere uiteinde, het Front-end genoemd, en het is logischerwijs een First in first out (FIFO) type lijst.

Voorbeeld

In ons dagelijks leven komen we veel situaties tegen waarin we wachten op de gewenste service, daar moeten we in de wachtrij staan ​​voor onze beurt om service te krijgen. Deze wachtrij kan worden gezien als een wachtrij.

1. Stapel volgt LIFO-mechanisme anderzijds Wachtrij volgt FIFO-mechanisme om elementen toe te voegen en te verwijderen.
2. In een stapel wordt hetzelfde uiteinde gebruikt om de elementen in te voegen en te verwijderen. Integendeel, twee verschillende uiteinden worden in de wachtrij gebruikt om de elementen in te voegen en te verwijderen.
3. Omdat Stack slechts één open einde heeft, is dat de reden om slechts één aanwijzer te gebruiken om naar de bovenkant van de stapel te verwijzen. Maar wachtrij gebruikt twee wijzers om naar de voorkant en de achterkant van de wachtrij te verwijzen.
4. Stack voert twee bewerkingen uit die bekend staan ​​als push en pop, terwijl in wachtrij bekend staat als enqueue en dequeue.
5. Stack-implementatie is eenvoudiger, terwijl Queue-implementatie lastig is.
6. Wachtrij heeft varianten zoals cirkelvormige wachtrij, prioriteitswachtrij, dubbel beëindigde wachtrij, enz. Stack heeft daarentegen geen varianten.

Stack-implementatie

De stapel kan op twee manieren worden toegepast:

1. Statische implementatie gebruikt arrays om een ​​stapel te maken. Statische implementatie is echter een moeiteloze techniek, maar is geen flexibele manier van creëren, omdat de declaratie van de stapelgrootte moet worden gedaan tijdens het ontwerp van het programma, waarna de grootte niet kan worden gevarieerd. Bovendien is statische implementatie niet erg efficiënt met betrekking tot geheugengebruik. Omdat een array (voor het implementeren van een stack) wordt gedeclareerd vóór het begin van de bewerking (tijdens het ontwerpen van het programma). Als het aantal te sorteren elementen nu veel minder in de stapel ligt, gaat het statisch toegewezen geheugen verloren. Aan de andere kant, als er meer aantal elementen in de stapel kan worden opgeslagen, kunnen we de grootte van de array niet wijzigen om de capaciteit te vergroten, zodat deze nieuwe elementen kan bevatten.
2. Dynamische implementatie wordt ook gekoppelde lijstrepresentatie genoemd en gebruikt aanwijzers om het stapeltype gegevensstructuur te implementeren.

Wachtrij-implementatie

Wachtrij kan op twee manieren worden geïmplementeerd:

1. 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 opgegeven tijdens het ontwerp of voordat de verwerking begint. In dit geval wordt het begin van de array de voorkant van de wachtrij en fungeert de laatste locatie van de array als de achterkant van de wachtrij. De volgende relatie geeft dat alle elementen bestaan ​​in de wachtrij wanneer geïmplementeerd met behulp van arrays:
   voor - achter + 1
   Als "achter <voor" dan zal er geen element in de wachtrij staan ​​of zal de wachtrij altijd leeg zijn.
2. Dynamische implementatie: Het implementeren van wachtrijen met behulp van pointers, het belangrijkste nadeel is dat een knooppunt in een gekoppelde weergave meer geheugenruimte inneemt dan een overeenkomstig element in de matrixweergave. Aangezien er in elk knooppunt ten minste twee velden zijn, één voor het gegevensveld en een 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.

Bewerkingen op stapel

De basisbewerkingen die op de stapel kunnen worden uitgevoerd, zijn de volgende:

1. DUWEN: wanneer een nieuw element aan de bovenkant van de stapel wordt toegevoegd, staat dit bekend als PUSH-bewerking. Door een element in de stapel te duwen, wordt het element toegevoegd, omdat het nieuwe element bovenaan wordt ingevoegd. Na elke duwbewerking wordt de bovenkant met één verhoogd. Als de array vol is en er geen nieuw element kan worden toegevoegd, wordt deze STACK-FULL-voorwaarde of STACK OVERFLOW genoemd. PUSH OPERATION - functie in C:
   Gezien stapel wordt verklaard als
   int stack, top = -1;
ongeldige push ()
{
int item;
if (top <4)
{
f ("Voer het nummer in");
scan ("% d", & item);
top = top + 1;
stapel = item;
}
anders
{
f ("Stack is vol");
}
}
2. KNAL: Wanneer een element bovenaan de stapel wordt verwijderd, wordt dit POP-bewerking genoemd. De stapel wordt na elke pop-operatie met één verlaagd. Als er geen element meer op de stapel zit en de pop wordt uitgevoerd, zal dit resulteren in een STACK UNDERFLOW-toestand, wat betekent dat uw stapel leeg is. POP-WERKING - functies in C:
   Gezien stapel wordt verklaard als
   int stack, top = -1;
nietige pop ()
{
int item;
if (top> = 4)
{
item = stapel;
top = top - 1;
f ("Nummer verwijderd is =% d", item);
}
anders
{
f ("Stapel is leeg");
}
}

Bewerkingen in een wachtrij

De basisbewerkingen die kunnen worden uitgevoerd in de wachtrij zijn:

1. enqueue: Om een ​​element in een wachtrij in te voegen.
   Wachtrij wordt verklaard als
   int wachtrij, Front = -1 en rear = -1;
void add ()
{
int item;
if (achter <4)
{
f ("Voer het nummer in");
scan ("% d", & item);
if (voorkant == -1)
{
voorzijde = 0;
achter = 0;
}
anders
{
achter = achter + 1;
}
wachtrij = item;
}
anders
{
f ("Wachtrij is vol");
}
}

2. dequeue: Om een ​​element uit de wachtrij te verwijderen. Bedieningsfunctie in wachtrij in C:
   Wachtrij wordt verklaard als
   int wachtrij, Front = -1 en rear = -1;
nietig verwijderen ()
{
int item;
if (voorkant! = -1)
{
item = wachtrij;
if (voorkant == achterkant)
{
voorzijde = -1;
achter = -1;
}
anders
{
voorzijde = voorzijde + 1;
f ("Nummer verwijderd is =% d", item);
}
}
anders
{
f ("Wachtrij is leeg");
}
}

Toepassingen van Stack

• Parsing in een compiler.
• Java virtuele machine.
• Ongedaan maken in een tekstverwerker.
• Terugknop in een webbrowser.
• PostScript-taal voor ers.
• Implementeren van functie-aanroepen in een compiler.

Toepassingen van wachtrij

• Gegevensbuffers
• Asynchrone gegevensoverdracht (IO-bestand, pijpen, sockets).
• Verzoeken toewijzen aan een gedeelde bron (eh, processor).
• Verkeersanalyse.
• Bepaal het aantal kassiers in een supermarkt.

Gevolgtrekking

Stack en Queue zijn lineaire gegevensstructuren die op bepaalde manieren verschillen, zoals werkmechanisme, structuur, implementatie, varianten, maar beide worden gebruikt voor het opslaan van de elementen in de lijst en het uitvoeren van bewerkingen op de lijst, zoals het toevoegen en verwijderen van de elementen. Hoewel er enkele beperkingen zijn van de eenvoudige wachtrij die wordt terugverdiend door andere soorten wachtrijen te gebruiken.