Anbefalet, 2020

Redaktørens Valg

Forskel mellem stak og kø

Stack and Que begge er de ikke-primitive datastrukturer. De vigtigste forskelle mellem stakken og køen er, at stakken anvender LIFO (sidste i første ud) -metode for at få adgang til og tilføje dataelementer, mens Queue bruger FIFO (First in first out) -metoden for at få adgang til og tilføje dataelementer.

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 sammenligningStak
ArbejdsprincipLIFO (sidst i første ud)FIFO (først i første ud)
StrukturSamme 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 pointerEnTo (i simpelt kø tilfælde)
Operationer udførtTryk og popEnqueue og dequeue
Undersøgelse af tom tilstandTop == -1Forside == -1 || Forside == Bag + 1
Undersøgelse af fuld betingelse
Top == Max - 1Bageste == Max - 1
VarianterDet har ikke varianter.Det har varianter som cirkulær kø, prioritetskø, dobbeltkødet kø.
ImplementeringenklereKomparativt 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ø

  1. Stack følger LIFO mekanisme på den anden side Kø følger FIFO mekanisme for at tilføje og fjerne elementer.
  2. 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.
  3. 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.
  4. Stack udfører to operationer kendt som push og pop i Queue, der er kendt som enqueue og dequeue.
  5. Implementering af stack er nemmere, mens køimplementering er vanskelig.
  6. 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:

  1. 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.
  2. 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:

  1. 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.
  2. 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:

  1. 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 som
    int 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");
    }
    }
  2. 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 som
    int 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:

  1. Enqueue : At indsætte et element i en kø. Funktionsfunktion i C:
    Kø er erklæret som
    int 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") ;
    }
    }
  2. Dequeue : At slette et element fra køen. Funktionsfunktion i C:
    Kø er erklæret som
    int 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.

Top