Stack har bare en ende åpen for å skyve og poppe dataelementene på den annen side. Køen har begge ender åpne for enqueuing og dequeuing dataelementene.
Stack og kø er datastrukturene som brukes til lagring av dataelementer, og er faktisk basert på noen ekteverdier. Stakken er for eksempel en stabel med CD-er, hvor du kan ta ut og sette inn CD-en gjennom toppen av CD-stakken. Tilsvarende er køen en kø for teaterbilletter hvor personen står i første omgang, dvs. foran køen vil bli servert først, og den nye personen som kommer kommer til å vises på baksiden av køen (bakenden av køen).
Sammenligningstabel
| Grunnlag for sammenligning | Stable | Kø |
|---|---|---|
| Arbeidsprinsipp | LIFO (sist i første ut) | FIFO (først i første ut) |
| Struktur | Samme ende brukes til å sette inn og slette elementer. | Den ene enden brukes til innsetting, dvs. bakenden og en annen ende brukes til sletting av elementer, dvs. forenden. |
| Antall poeng brukt | En | To (i enkel kø tilfelle) |
| Operasjoner utført | Push og Pop | Enqueue og dequeue |
| Undersøkelse av tom tilstand | Topp == -1 | Front == -1 || Front == Bak + 1 |
| Undersøkelse av full tilstand | Topp == Max - 1 | Bak = = Max - 1 |
| varianter | Det har ikke varianter. | Det har varianter som sirkulær kø, prioritetskø, dobbel avslutte kø. |
| Gjennomføring | enklere | Komparativt komplisert |
Definisjon av Stack
En Stack er en ikke-primær lineær datastruktur. Det er en bestilt liste der det nye elementet er lagt til og eksisterende element slettes fra bare en ende, kalt som toppen av stakken (TOS). Siden all deletion og innsetting i en stabel er gjort fra toppen av stabelen, blir det siste elementet som er lagt til, den første som skal fjernes fra stakken. Det er grunnen til at stabelen heter Last-in-First-out (LIFO) type liste.
Merk at elementet som ofte er åpnet i stakken, er det øverste elementet, mens det siste tilgjengelige elementet er i bunnen av stakken.
Eksempel
Noen av dere kan spise kjeks (eller Poppins). Hvis du antar, er bare en side av dekselet revet, og kjeks tas ut en etter en. Dette er det som kalles popping, og på samme måte, hvis du vil bevare noen kjeks for en stund senere, vil du sette dem tilbake i pakken gjennom samme revet ende, kalles pushing.
Definisjon av kø
En kø er en lineær datastruktur som kommer i kategorien av den ikke-primitive typen. Det er en samling av lignende type elementer. Tilsetningen av nye elementer finner sted i den ene enden som kalles bakenden. På samme måte skjer slettingen av de eksisterende elementene i den andre enden kalt Front-enden, og det er logisk en første i første ut (FIFO) type liste.
Eksempel
I vårt daglige liv står vi overfor mange situasjoner der vi venter på ønsket tjeneste, der må vi komme inn i ventelinjen for å få service. Denne ventekøen kan tenkes som en kø.
Viktige forskjeller mellom stakk og kø
- Stack følger LIFO-mekanismen på den annen side Queue følger FIFO-mekanismen for å legge til og fjerne elementer.
- I en stabel brukes den samme enden til å sette inn og slette elementene. Tvert imot brukes to forskjellige ender i køen for å sette inn og slette elementene.
- Som Stack har bare en åpen ende som er grunnen til å bruke bare en peker for å referere til toppen av stakken. Men køen bruker to pekere til å referere frem og bakenden av køen.
- Stack utfører to operasjoner kjent som push og pop mens i Que er kjent som enqueue og dequeue.
- Implementering av stabling er lettere, mens kjøreimplementering er vanskelig.
- Køen har varianter som sirkulær kø, prioritetskø, dobbel avslutte kø, etc. I kontrast har stakken ikke varianter.
Stack Implementering
Stakken kan brukes på to måter:
- Statisk implementering bruker arrays for å lage en stabel. Statisk implementering er imidlertid en uanstrengt teknikk, men er ikke en fleksibel måte å skape, da deklarasjonen av størrelsen på stakken må gjøres under programdesign, etter at størrelsen ikke kan varieres. I tillegg er statisk implementering ikke veldig effektiv med hensyn til minneutnyttelse. Siden en rekkefølge (for implementering av stabel) er deklarert før starten av operasjonen (ved programdesigntid). Nå, hvis antall elementer som skal sorteres er svært mindre i stabelen, vil det statisk allokerte minnet bli bortkastet. På den annen side, hvis det er flere elementer som skal lagres i stabelen, kan vi ikke endre størrelsen på arrayet for å øke kapasiteten, slik at den kan huse nye elementer.
- Dynamisk implementering kalles også koblet listrepresentasjon og bruker pekere for å implementere stabel typen datastruktur.
Kjølimplementering
Køen kan implementeres på to måter:
- Statisk implementering : Hvis en kø er implementert ved hjelp av arrayer, må det nøyaktige antall elementer vi ønsker å lagre i køen, forsikres tidligere, fordi størrelsen på arrayet må deklareres på designtid eller før behandlingen starter. I dette tilfellet blir begynnelsen av arrayet forsiden av køen, og den siste plasseringen av arrayet vil fungere som baksiden av køen. Følgende relasjon gir hele elementene i køen når de implementeres ved hjelp av arrays:
front - bak + 1
Hvis "bak <foran" så vil det ikke være noe element i køen eller køen vil alltid være tom. - Dynamisk implementering : Implementere køer med pekere, den største ulempen er at en node i en koblet representasjon bruker mer minne enn et tilsvarende element i array-representasjonen. Siden det er minst to felter i hver node en for datafeltet og andre for å lagre adressen til den neste noden, mens det i koblet representasjon bare er datafelt der. Verdien av å bruke den koblede representasjonen blir åpenbar når det er nødvendig å sette inn eller slette et element midt i en gruppe andre elementer.
Operasjoner på Stack
De grunnleggende operasjonene som kan betjenes på stakken, er som følger:
- PUSH : Når et nytt element legges til toppen av stabelen, kalles PUSH-operasjonen. Ved å skyve et element i stakken påberopes det å legge til elementet, da det nye elementet blir satt inn øverst. Etter hver trykkoperasjon økes toppen med en. Hvis arrayet er fullt, og ingen nytt element kan legges, kalles det STACK-FULL-tilstand eller STACK OVERFLOW. PUSH OPERATION - funksjon i C:
Vurderer stabel er erklært 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 et element slettes fra toppen av stabelen, kalles det POP-operasjon. Stakken er redusert med en, etter hver popoperasjon. Hvis det ikke er noe element igjen på stakken og popen utføres, vil dette resultere i STACK UNDERFLOW-tilstand som betyr at stakken er tom. POP OPERATION - Funksjoner i C:
Vurderer stabel er erklært 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");}}
Operasjoner på en kø
De grunnleggende operasjonene som kan utføres i kø er:
- Enqueue : For å sette inn et element i en kø. Fungeringsfunksjon i C:
Kø er erklært 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 : For å slette et element fra køen. Fungeringsfunksjon i C:
Kø er erklært 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") ;}}
Programmer av Stack
- Parsing i en kompilator.
- Java virtuell maskin.
- Angre i tekstbehandler.
- Back-knappen i en nettleser.
- PostScript-språk for skrivere.
- Implementere funksjonssamtaler i en kompilator.
Applikasjoner av kø
- Databuffere
- Asynkron dataoverføring (fil IO, rør, stikkontakter).
- Allotting forespørsler på en delt ressurs (skriver, prosessor).
- Trafikkanalyse.
- Bestem antall kasserere å ha på et supermarked.
Konklusjon
Stack and Que er lineære datastrukturer, avviker på enkelte måter som arbeidsmekanisme, struktur, implementering, varianter, men begge brukes til å lagre elementene i listen og utføre operasjoner på listen som tillegg og sletting av elementene. Selv om det er noen begrensninger av den enkle køen som blir hevdet ved å bruke andre typer kø.
