Stack har endast ena änden öppen för att trycka och poppa dataelementen å andra sidan Queue har båda ändarna öppna för enqueuing och dequeuing dataelementen.
Stack och kö är datastrukturerna som används för att lagra dataelement och är faktiskt baserade på en viss ekvivalent. Stacken är till exempel en stapel av CD-skivor där du kan ta ut och sätta in CD-skivan överst på stapeln av CD-skivor. På samma sätt är kön en kö för teaterbiljetter där personen står i första hand, dvs könens främre del kommer att serveras först och den nya personen som kommer fram kommer att dyka upp i könens baksida (bakre delen av kön).
Jämförelsediagram
| Grunder för jämförelse | Stack | Kö |
|---|---|---|
| Arbetsprincip | LIFO (senast i första utgåvan) | FIFO (först i första utgåvan) |
| Strukturera | Samma ände används för att infoga och ta bort element. | En ände används för infogning, dvs bakre änden och en annan ände används för att radera element, dvs frontänden. |
| Antal använda pekare | Ett | Två (i enkla köfall) |
| Operationer utförda | Tryck och Pop | Enqueue och dequeue |
| Undersökning av tomt tillstånd | Top == -1 | Fram == -1 || Fram == Bak + 1 |
| Undersökning av fullständigt skick | Överst == Max - 1 | Bakre == Max - 1 |
| varianter | Det har inga varianter. | Det har varianter som cirkelkö, prioritetskö, dubbelt avslutad kö. |
| Genomförande | enklare | Jämförelsevis komplex |
Definition av stapel
En stapel är en icke-primitiv linjär datastruktur. Det är en beställd lista där det nya objektet läggs till och det befintliga elementet raderas från en enda ände, kallad som toppen av stapeln (TOS). Eftersom all borttagning och infogning i en stapel görs från toppen av stapeln, kommer det sista elementet att vara det första som ska tas bort från stapeln. Det är anledningen till att stacken heter Last-in-First-out (LIFO) typ av lista.
Observera att det element som ofta är tillgängligt i stapeln är det översta elementet, medan det sista tillgängliga elementet ligger i botten av stapeln.
Exempel
Vissa av er kan äta kex (eller Poppins). Om du antar att endast en sida av kåpan är trasig och kakor tas ut en efter en. Det här kallas popping, och på samma sätt, om du vill behålla några kex under en längre tid, kommer du att sätta tillbaka dem i packen genom samma slitna ände kallas att trycka.
Definition av kö
En kö är en linjär datastruktur som kommer i kategorin av den icke-primitiva typen. Det är en samling av liknande typer av element. Tillägget av nya element sker i ena änden kallad bakre änden. På samma sätt sker radering av de befintliga elementen i den andra änden som heter Front-end, och det är logiskt en lista som först i först ut (FIFO).
Exempel
I vårt dagliga liv stöter vi på många situationer där vi väntar på önskad service, där vi måste komma in i väntelinjen för vår tur att bli service. Den här väntan köen kan ses som en kö.
Viktiga skillnader mellan stack och kö
- Stack följer LIFO-mekanismen å andra sidan Queue följer FIFO-mekanismen för att lägga till och ta bort element.
- I en stapel används samma ände för att infoga och radera elementen. Tvärtom används två olika ändar i kön för att infoga och radera elementen.
- Som Stack har bara en öppen ände som är anledningen till att endast en pekare används för att referera till toppen av stapeln. Men kö använder två pekare för att referera fram och bakre delen av kön.
- Stack utför två operationer som kallas push och pop medan i Que är känd som enqueue och dequeue.
- Stackimplementering är lättare medan köförloppet är knepigt.
- Kö har varianter som cirkelkö, prioritetskö, dubbelt slutad kö osv. Stack har däremot inte varianter.
Stack Implementation
Stacken kan appliceras på två sätt:
- Statisk implementering använder arrays för att skapa en stapel. Statisk implementering är dock en enkel teknik men det är inte ett flexibelt sätt att skapa, eftersom deklarationen av stackens storlek måste göras under programdesign, varefter storleken inte kan varieras. Dessutom är statisk implementering inte särskilt effektiv när det gäller minnesutnyttjande. Eftersom en array (för implementeringsstack) deklareras före operationens start (vid programdesigntiden). Nu om antalet element som ska sorteras är mycket mindre i stapeln blir det statiskt tilldelade minnet bortkastat. Å andra sidan, om det finns fler antal element som ska lagras i stapeln då kan vi inte ändra storleken på matrisen för att öka dess kapacitet så att den kan rymma nya element.
- Dynamiskt genomförande kallas också länkad listrepresentation och använder pekare för att implementera stapeltypen av datastrukturen.
Köthantering
Kö kan implementeras på två sätt:
- Statisk implementering : Om en kö implementeras med hjälp av arrayer måste det exakta antalet element som vi vill lagra i köen försäkras tidigare, eftersom storleken på arrayen måste deklareras vid designtiden eller innan bearbetningen börjar. I det här fallet kommer början på matrisen att bli framkanten av kön, och den sista placeringen av matrisen kommer att fungera som bakom kön. Följande relation ger hela elementen i köen när de implementeras med hjälp av arrays:
fram - bak + 1
Om "bakre <front" kommer det inte att finnas något element i kön eller köen kommer alltid att vara tom. - Dynamiskt genomförande : Implementera köer med hjälp av pekare, den största nackdelen är att en nod i en länkad representation förbrukar mer minnesutrymme än ett motsvarande element i matrisrepresentationen. Eftersom det finns minst två fält i varje nod en för datafältet och andra för att lagra adressen till nästa nod medan det i länkad representation endast finns datafält. Förtjänsten att använda den länkade representationen blir uppenbar när det är nödvändigt att infoga eller radera ett element i mitten av en grupp andra element.
Operationer på stacken
De grundläggande operationer som kan drivas på stapeln är följande:
- PUSH : när ett nytt element läggs till toppen av stapeln kallas PUSH-drift. Genom att trycka på ett element i stapeln åberopas tillsatsen av elementet, eftersom det nya elementet kommer att sättas in på toppen. Efter varje tryckning ökar toppen med en. Om matrisen är full och inget nytt element kan läggas till kallas det STACK-FULL-tillståndet eller STACK-OVERFLOW. PUSH OPERATION - funktion i C:
Med tanke på stapeln förklaras somint 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 : När ett element raderas från toppen av stapeln kallas POP-funktionen. Stacken minskas med en, efter varje popoperation. Om det inte finns något element kvar på stapeln och popen utförs, kommer det att resultera i STACK UNDERFLOW-tillstånd vilket betyder att din stack är tom. POP OPERATION - funktioner i C:
Med tanke på stapeln förklaras somint 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");}}
Operationer på en kö
De grundläggande operationer som kan utföras i kö är:
- Enqueue : Att sätta in ett element i en kö. Funktionsfunktionen i C:
Kö är deklarerad somint 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 : Att radera ett element från kön. Funktionsfunktionen i C:
Kö är deklarerad somint 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") ;}}
Stackansökningar
- Parsning i en kompilator.
- Java virtuell maskin.
- Ångra i en ordbehandlare.
- Tillbaka-knappen i en webbläsare.
- PostScript-språk för skrivare.
- Implementera funktionen samtal i en kompilator.
Applikationer av kö
- Databuffertar
- Asynkron dataöverföring (fil IO, rör, uttag).
- Tilldela förfrågningar på en gemensam resurs (skrivare, processor).
- Trafikanalys.
- Bestäm antalet kassörer att ha i en stormarknad.
Slutsats
Stack och Que ä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 några begränsningar av den enkla köen som återvinns genom att använda andra typer av kö.
