Skillnaden mellan stack och kö

Innehåll

Jämförelsediagram
Definition av Stack
Exempel
Definition av kö
Exempel
Stack Implementation
Köimplementering
Verksamhet på stacken
Operationer i en kö
Applications of Stack
Applications of Queue
Slutsats

Stack och kö är båda de icke-primitiva datastrukturerna. De viktigaste skillnaderna mellan stack och kö är att stacken använder LIFO-metoden (sist i första ut) för att komma åt och lägga till dataelement medan kö köar FIFO-metoden (First in first out) för att komma åt och lägga till dataelement.

Stack har bara en ände öppen för att trycka och knacka dataelementen å andra sidan Kön har båda ändarna öppna för att täcka och avveckla dataelementen.

Stack och kö är de datastrukturer som används för att lagra dataelement och baseras faktiskt på en verklig ekvivalent. Till exempel är stacken en bunt med CD-skivor där du kan ta ut och lägga in CD-skivan genom toppen av CD-skivan. På liknande sätt är kön en kö för teaterbiljetter där personen som står i första hand, d.v.s. framför kön kommer att serveras först och den nya personen som anländer kommer att visas på baksidan av kön (bakre änden av kön).

Jämförelsediagram
Definition
Viktiga skillnader
Genomförande
Operationer
tillämpningar
Slutsats

Jämförelsediagram


Grund för jämförelse	Stack	Kö
Arbetsprincip	LIFO (Last in First out)	FIFO (First in First out)
Strukturera	Samma slut används för att infoga och ta bort element.	En ände används för införande, d.v.s. bakre ände och en annan ände används för borttagning av element, dvs främre ände.
Antal använda pekare	Ett	Två (i enkel köfall)
Åtgärder utförda	Push och Pop	Enqueue och dequeue
Undersökning av tomt skick	Topp == -1	Fram == -1 \|\| Fram == Bak + 1
Undersökning av fullt skick	Topp == Max - 1	Bak == Max - 1
varianter	Det har inte varianter.	Den har varianter som cirkulär kö, prioriteringskö, dubbel slutad kö.
Genomförande	enklare	Relativt komplex

Definition av Stack

En stack är en icke-primitiv linjär datastruktur. Det är en ordnad lista där det nya objektet läggs till och befintligt element raderas från endast en ände, kallat som toppen av stacken (TOS). Eftersom all radering och infogning i en bunt görs från toppen av bunten, kommer det sista elementet som lagts till att vara det första som tas bort från bunten. Det är anledningen till att stapeln kallas listan för sista-in-först-ut (LIFO).

Observera att elementet som ofta nås i bunten är det översta elementet, medan det sista tillgängliga elementet är i botten av bunten.

Exempel

Några av er kan äta kex (eller Poppins). Om du antar att bara en sida av locket rivs och kex tas ut en efter en. Detta är vad som kallas poppning, och på liknande sätt, om du vill bevara vissa kex under en tid senare, kommer du att sätta tillbaka dem i förpackningen genom samma sönderrivna ände kallas pushing.

Definition av kö

En kö är en linjär datastruktur kommer i kategorin av den icke-primitiva typen. Det är en samling av liknande typ av element. Tillägget av nya element sker i ena änden som kallas bakre ände. På samma sätt sker raderingen av de befintliga elementen i den andra änden, kallad Front-end, och det är logiskt en första i första ut (FIFO) typ av lista.

Exempel

I vårt dagliga liv stöter vi på många situationer där vi vill vänta på önskad service, där måste vi komma in i väntan på vår tur för att få service. Denna väntskö kan betraktas som en kö.

Stack följer LIFO-mekanismen å andra sidan Kön följer FIFO-mekanismen för att lägga till och ta bort element.
I en bunt används samma ände för att infoga och radera elementen. Tvärtom, två olika ändar används i kön för att infoga och radera elementen.
Eftersom Stack endast har en öppen ände är det anledningen till att du bara använder en pekare för att hänvisa till toppen av bunten. Men kön använder två pekare för att hänvisa till könens främre och bakre ände.
Stack utför två operationer som kallas push and pop medan de är kända som enqueue and dequeue.
Stackimplementering är enklare medan implementering av kö är svårt.
Kön har varianter som cirkulär kö, prioriteringskö, dubbel slutad kö osv. I motsats till detta har stack inte varianter.

Stack Implementation

Bunten kan appliceras på två sätt:

Statisk implementering använder matriser för att skapa en bunt. Statisk implementering är dock en enkel teknik men är inte ett flexibelt sätt att skapa, eftersom deklarationen av storleken på stacken måste göras under programutformningen, efter det kan storleken inte varieras. Dessutom är statisk implementering inte särskilt effektiv när det gäller minnesanvändning. Eftersom en matris (för implementering av stack) deklareras innan operationen påbörjas (vid programdesigntid). Om antalet element som ska sorteras är mycket mindre i bunten kommer det statiskt tilldelade minnet att slösas bort. Å andra sidan, om det finns fler antal element som ska lagras i bunten, kan vi inte kunna ändra storleken på matrisen för att öka dess kapacitet, så att den kan rymma nya element.
Dynamisk implementering kallas också länkad listrepresentation och använder pekare för att implementera stapeltypen datastruktur.

Köimplementering

Kön kan implementeras på två sätt:

Statisk implementering: Om en kö implementeras med hjälp av matriser, måste det exakta antalet element vi vill lagra i kön säkerställas före, eftersom storleken på matrisen måste anges vid designtid eller innan behandlingen startar. I det här fallet kommer början av matrisen att bli framsidan av kön, och den sista platsen för matrisen kommer att fungera som baksidan av kön. Följande relation ger hela elementen som finns i kön när de implementeras med hjälp av matriser:
fram - bak + 1
Om "bak <fram" kommer det inget element i kön eller kön kommer alltid att vara tom.
Dynamisk implementering: Implementering av köer med hjälp av pekare, den största nackdelen är att en nod i en länkad representation förbrukar mer minne än ett motsvarande element i matrisrepresentationen. Eftersom det finns minst två fält i varje nod ett för datafältet och annat för att lagra adressen till nästa nod medan i länkad representation endast är datafältet där. Förtjänsten av att använda den länkade representationen blir uppenbar när det krävs att infoga eller radera ett element i mitten av en grupp andra element.

Verksamhet på stacken

De grundläggande operationerna som kan manövreras på bunten är följande:

TRYCK: när ett nytt element läggs till toppen av bunten kallas PUSH-operation. Om du trycker på ett element i bunken påkallas tillägg av elementet, eftersom det nya elementet kommer att läggas upp längst upp. Efter varje tryckoperation ökas toppen med en. Om matrisen är full och inget nytt element kan läggas till kallas det STACK-FULL-tillstånd eller STACK OVERFLOW. PUSH OPERATION - funktion i C:
Att betrakta stack förklaras som
int-stack, topp = -1;
void push ()
{
int artikel;
if (topp <4)
{
f ("Ange numret");
skanna ("% d", & artikel);
topp = topp + 1;
stack = artikel;
}
annan
{
f ("Stack är full");
}
}
POP: När ett element raderas från toppen av stapeln kallas det POP-operation. Bunten minskas med en efter varje popoperation. Om det inte finns något element kvar på bunten och popen utförs, kommer detta att resultera i STACK UNDERFLOW-tillstånd, vilket innebär att din stack är tom. POP-OPERATION - funktioner i C:
Betraktar stacken förklaras som
int-stack, topp = -1;
void pop ()
{
int artikel;
if (överst> = 4)
{
artikel = stack;
topp = topp - 1;
f ("Antalet raderat är =% d", objekt);
}
annan
{
f ("Stack är tom");
}
}

Operationer i en kö

De grundläggande operationerna som kan utföras i kö är:

enqueue: För att infoga ett element i en kö. Funktion för utvärdering av funktion i C:
Kön förklaras som
int-kö, Främre = -1 och bakre = -1;
void add ()
{
int artikel;
if (bak <4)
{
f ("Ange numret");
skanna ("% d", & artikel);
if (front == -1)
{
främre = 0;
bakre = 0;
}
annan
{
bakre = bakre + 1;
}
kö = objekt;
}
annan
{
f ("Kön är full");
}
}
dequeue: För att radera ett element från kön. Funktion för utvärdering av funktion i C:
Kön förklaras som
int-kö, Främre = -1 och bakre = -1;
void delete ()
{
int artikel;
if (front! = -1)
{
objekt = kö;
if (fram = = bak)
{
front = -1;
bakre = -1;
}
annan
{
front = front + 1;
f ("Antalet raderat är =% d", objekt);
}
}
annan
{
f ("Kön är tom");
}
}

Applications of Stack

Analysera i en kompilator.
Java virtuell maskin.
Ångra i en ordbehandlare.
Tillbaka-knapp i en webbläsare.
PostScript-språk för ers.
Implementeringsfunktionen anropar en kompilator.

Applications of Queue

Data buffertar
Asynkron dataöverföring (fil IO, rör, uttag).
Tilldela förfrågningar på en delad resurs (er, processor).
Trafikanalys.
Bestäm antalet kassörer som ska finnas i en stormarknad.

Slutsats

Stack och kö är linjära datastrukturer skiljer sig på vissa sätt som arbetsmekanism, struktur, implementering, varianter men båda används för att lagra elementen i listan och utföra operationer på listan som tillägg och radering av elementen. Även om det finns vissa begränsningar för den enkla kön som återhämtas genom att använda andra typer av kö.