Stack har kun den ene ende åben til at skubbe og poppe dataelementerne på den anden side Køen har begge ender åbne for enqueuing og dequeuing dataelementerne.
Stak og kø er de datastrukturer, der bruges til lagring af dataelementer, og er faktisk baseret på en reel verdenskvivalent. Stakken er for eksempel en stak cd'er, hvor du kan tage ud og lægge cd i toppen af stakken af cd'er. Tilsvarende er køen en kø for teaterbilletter, hvor personen står i første omgang, dvs. foran køen vil blive serveret først, og den nye person, der ankommer, vises på bagsiden af køen (bagenden af køen).
Sammenligningstabel
| Grundlag for sammenligning | Stak | Kø |
|---|---|---|
| Arbejdsprincip | LIFO (sidst i første ud) | FIFO (først i første ud) |
| Struktur | Samme ende bruges til at indsætte og slette elementer. | Den ene ende bruges til indsættelse, dvs. bagenden og en anden ende bruges til sletning af elementer, dvs. forenden. |
| Antal anvendte pointer | En | To (i simpelt kø tilfælde) |
| Operationer udført | Tryk og pop | Enqueue og dequeue |
| Undersøgelse af tom tilstand | Top == -1 | Forside == -1 || Forside == Bag + 1 |
| Undersøgelse af fuld betingelse | Top == Max - 1 | Bageste == Max - 1 |
| Varianter | Det har ikke varianter. | Det har varianter som cirkulær kø, prioritetskø, dobbeltkødet kø. |
| Implementering | enklere | Komparativt kompleks |
Definition af Stack
En Stack er en ikke-primitive lineære datastruktur. Det er en ordnet liste, hvor det nye element tilføjes, og eksisterende element slettes fra kun den ene ende, kaldet som toppen af stakken (TOS). Da al sletning og indsættelse i en stak udføres fra toppen af stakken, bliver det sidste element, der er tilføjet, det første der fjernes fra stakken. Det er grunden til, at stakken hedder sidst-i-først-ud-typen (LIFO).
Bemærk, at elementet, der ofte er adgang til i stakken, er det øverste element, mens det sidste tilgængelige element er i bunden af stakken.
Eksempel
Nogle af jer må spise kiks (eller Poppins). Hvis man antager, er kun den ene side af dækslet revet, og kiks er taget ud en efter en. Dette er det, der kaldes popping, og på samme måde, hvis du vil bevare nogle kiks for en tid senere, vil du sætte dem tilbage i pakken gennem samme revne ende kaldes skubbe.
Definition af kø
En kø er en lineær datastruktur, der kommer i kategorien af den ikke-primitive type. Det er en samling af lignende typer af elementer. Tilsætningen af nye elementer finder sted i den ene ende kaldet bagenden. Tilsvarende finder sletning af de eksisterende elementer sted i den anden ende, der hedder Front-end, og det er logisk en første i første ud (FIFO) type liste.
Eksempel
I vores daglige liv kommer vi på tværs af mange situationer, hvor vi venter på den ønskede service, der er vi nødt til at komme ind på ventelinjen for vores tur til at blive serviceret. Denne ventekø kan betragtes som en kø.
Nøgleforskelle mellem stak og kø
- Stack følger LIFO mekanisme på den anden side Kø følger FIFO mekanisme for at tilføje og fjerne elementer.
- I en stak bruges den samme ende til at indsætte og slette elementerne. Tværtimod anvendes to forskellige ender i køen for at indsætte og slette elementerne.
- Som Stack har kun en åben ende, der er grunden til at bruge kun en pointer til at referere til toppen af stakken. Men køen bruger to pointers til at henvise til forreste og bageste ende af køen.
- Stack udfører to operationer kendt som push og pop i Queue, der er kendt som enqueue og dequeue.
- Implementering af stack er nemmere, mens køimplementering er vanskelig.
- Kø har varianter som cirkulær kø, prioritetskø, dobbeltkødet kø osv. Derimod har stakken ikke varianter.
Stack Implementation
Stakken kan anvendes på to måder:
- Statisk implementering bruger arrays til at oprette en stak. Statisk implementering er dog en ubesværet teknik, men er ikke en fleksibel måde at skabe, da størrelsen af stakken skal udformes under programdesign, hvorefter størrelsen ikke kan varieres. Derudover er statisk implementering ikke særlig effektiv med hensyn til hukommelsesudnyttelse. Da en array (til implementering af stakken) er erklæret før starten af operationen (ved programdesigntid). Nu, hvis antallet af elementer, der skal sorteres, er meget mindre i stakken, vil den statisk allokerede hukommelse blive spildt. På den anden side, hvis der er flere elementer, der skal lagres i stakken, kan vi ikke ændre størrelsen på arrayet for at øge dets kapacitet, så den kan rumme nye elementer.
- Dynamisk implementering kaldes også linket liste repræsentation og bruger peger til at implementere stak typen af datastruktur.
Kø-implementering
Kø kan implementeres på to måder:
- Statisk implementering : Hvis en kø implementeres ved hjælp af arrayer, skal det præcise antal elementer, vi ønsker at gemme i køen, sikres forud, fordi størrelsen af arrayet skal deklareres på designtidspunktet eller inden behandlingen starter. I dette tilfælde vil begyndelsen af arrayet blive forreste af køen, og den sidste placering af arrayet vil fungere som bagsiden af køen. Følgende relation giver hele elementerne i køen, når de implementeres ved hjælp af arrayer:
front - bag + 1
Hvis "bag <foran" så vil der ikke være noget element i køen eller køen vil altid være tom. - Dynamisk implementering : Implementering af køer ved hjælp af peger, den største ulempe er, at en node i en koblet repræsentation forbruger mere hukommelsesplads end et tilsvarende element i arrayrepræsentationen. Da der er mindst to felter i hver node en til datafeltet og andre til at gemme adressen til den næste node, mens der kun er knyttet datafelt i koblet repræsentation. Fortjenesten ved at bruge den linkede repræsentation bliver tydelig, når det er nødvendigt at indsætte eller slette et element midt i en gruppe af andre elementer.
Operationer på Stack
De grundlæggende operationer, der kan betjenes på stakken, er som følger:
- PUSH : Når et nyt element er tilføjet til toppen af stakken, kaldes PUSH-drift. Ved at skubbe et element i stakken påberåves tilføjelse af elementet, da det nye element vil blive indsat øverst. Efter hver push-operation øges toppen med en. Hvis arrayet er fuld, og der ikke kan tilføjes noget nyt, hedder det STACK-FULL tilstand eller STACK OVERFLOW. PUSH OPERATION - funktion i C:
I betragtning af stakken er erklæret 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 af stakken, er det kendt som POP-drift. Stakken er reduceret med en, efter hver popoperation. Hvis der ikke er noget element tilbage på stakken og popen udføres, vil det resultere i STACK UNDERFLOW tilstand, hvilket betyder at din stak er tom. POP OPERATION - funktioner i C:
I betragtning af stakken er erklæret 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æggende operationer, der kan udføres i kø, er:
- Enqueue : At indsætte et element i en kø. Funktionsfunktion i C:
Kø er erklæret 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 : At slette et element fra køen. Funktionsfunktion i C:
Kø er erklæret 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") ;}}
Anvendelser af Stack
- Parsering i en compiler.
- Java virtuelle maskine.
- Fortryd i en tekstbehandler.
- Tilbage knap i en webbrowser.
- PostScript-sprog til printere.
- Implementering af funktionsopkald i en compiler.
Applikationer af kø
- Databuffere
- Asynkron dataoverførsel (fil IO, rør, stikkontakter).
- Allotering af anmodninger på en delt ressource (printer, processor).
- Trafikanalyse.
- Bestem antallet af kasserere at have på et supermarked.
Konklusion
Stak og kø er lineære datastrukturer adskiller sig på visse måder som arbejdsmekanisme, struktur, implementering, varianter, men begge bruges til at lagre elementerne i listen og udføre operationer på listen som tilføjelse og sletning af elementerne. Selv om der er nogle begrænsninger af den enkle kø, der er indsamlet ved at bruge andre køetyper.
