Forskellen mellem stak og kø

Indhold

Sammenligningstabel
Definition af stak
Eksempel
Definition af kø
Eksempel
Stakimplementering
Køimplementering
Operationer på stak
Handlinger i en kø
Anvendelser af Stack
Anvendelser af kø
Konklusion

Stabel og kø er begge de ikke-primitive datastrukturer. De største forskelle mellem stak og kø er, at stak bruger LIFO-metode (sidst i første ud) til at få adgang til og tilføje dataelementer, mens køen bruger FIFO-metode (Først i første ud) til at få adgang til og tilføje dataelementer.

Stakken har kun den ene ende åben for at skubbe og sprænge dataelementerne på den anden side Køen har begge ender åben for at udtømme og afmatte dataelementerne.

Stak og kø er de datastrukturer, der bruges til lagring af dataelementer og er faktisk baseret på noget ægteækvivalent. For eksempel er stakken en stak cd'er, hvor du kan tage ud og sætte en cd gennem toppen af stakken med cd'er. På lignende måde er køen en kø for teaterbilletter, hvor den person, der står i første omgang, dvs. forresten af køen, serveres først, og den nye person, der ankommer, vises på bagsiden af køen (bagenden af køen).

Sammenligningstabel
Definition
Vigtige forskelle
Implementering
operationer
Applikationer
Konklusion

Sammenligningstabel


Grundlag for sammenligning	Stak	Kø
Arbejdsprincip	LIFO (sidst først ud)	FIFO (First in First out)
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. frontenden.
Antal anvendte pegepinde	En	To (i enkel køsak)
Foretagne operationer	Tryk og pop	Enqueue og dequeue
Undersøgelse af tom tilstand	Top == -1	Foran == -1 \|\| Foran == Bageste + 1
Undersøgelse af fuld stand	Top == Max - 1	Bageste == Maks - 1
Varianter	Det har ikke varianter.	Det har varianter som cirkulær kø, prioriteringskø, dobbelt afsluttet kø.
Implementering	enklere	Relativt kompleks

Definition af stak

En stak er en ikke-primitiv lineær datastruktur. Det er en ordnet liste, hvor det nye element tilføjes, og det eksisterende element slettes fra den ene ende, kaldet som toppen af stakken (TOS). Da al sletning og indsættelse i en stabel udføres fra toppen af stakken, vil det sidste element, der blev tilføjet, være det første, der fjernes fra stakken. Det er grunden til, at stack kaldes Last-in-First-out (LIFO) type liste.

Bemærk, at det element, der ofte åbnes i stakken, er det øverste element, mens det sidst tilgængelige element er i bunden af stakken.

Eksempel

Nogle af jer spiser måske kiks (eller Poppins). Hvis du antager, er der kun en side af dækslet, der er revet, og kiks tages ud én efter én. Dette kaldes popping, og på lignende måde, hvis du vil bevare nogle kiks i et stykke tid senere, vil du sætte dem tilbage i pakken gennem den samme revne ende kaldes skubbe.

Definition af kø

En kø er en lineær datastruktur kommer i kategorien af den ikke-primitive type. Det er en samling af lignende type elementer. Tilsætningen af nye elementer finder sted i den ene ende kaldet bagenden. På samme måde finder sletning af de eksisterende elementer sted i den anden ende kaldet Front-end, og det er logisk set en liste over først i første ud (FIFO).

Eksempel

I vores daglige liv støder vi på mange situationer, hvor vi ude at vente på den ønskede service, der er vi nødt til at komme ind på ventelinjen for vores tur til at få service. Denne ventekø kan betragtes som en kø.

Stak 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 bruges to forskellige ender i køen til at indsætte og slette elementerne.
Da stak kun har en åben ende, er det grunden til, at du kun bruger en markør til at henvise til toppen af stakken. Men køen bruger to pegepunkter til at henvise foran og bagenden af køen.
Stack udfører to operationer, der er kendt som push and pop, mens de i kø er kendt som enqueue og dequeue.
Stakimplementering er lettere, mens køimplementering er vanskelig.
Kø har varianter som cirkulær kø, prioriteringskø, dobbelt afsluttet kø osv. I modsætning hertil har stak ikke varianter.

Stakimplementering

Stakken kan påføres på to måder:

Statisk implementering bruger arrays til at oprette en stak. Statisk implementering er skønt en ubesværet teknik, men er ikke en fleksibel måde at skabe, da erklæringen af stabelens størrelse skal udføres under programdesign, hvorefter størrelsen ikke kan varieres. Derudover er statisk implementering ikke særlig effektiv med hensyn til hukommelsesudnyttelse. Da en matrix (til implementering af stak) er erklæret inden operationens start (på programdesigntidspunktet). Hvis antallet af elementer, der skal sorteres, er meget mindre i stakken, spildes den statisk tildelte hukommelse. På den anden side, hvis der er flere antal elementer, der skal gemmes i stakken, kan vi ikke være i stand til at ændre størrelsen på arrayet for at øge dens kapacitet, så det kan rumme nye elementer.
Dynamisk implementering kaldes også linkliste-repræsentation og bruger pointers til at implementere stacktypen af datastrukturen.

Køimplementering

Kø kan implementeres på to måder:

Statisk implementering: Hvis en kø implementeres ved hjælp af arrays, skal det nøjagtige antal elementer, vi vil gemme i køen, være sikret forud for, fordi størrelsen på arrayet skal deklareres på designtidspunktet eller før behandlingen starter. I dette tilfælde vil starten af arrayet blive den forreste af køen, og den sidste placering af arrayen fungerer som bagsiden af køen. Følgende forhold viser, at hele elementerne findes i køen, når de implementeres ved hjælp af arrays:
forreste - bageste + 1
Hvis "bag <foran", 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 pegere, den største ulempe er, at en knude i en sammenkoblet repræsentation bruger mere hukommelsesplads end et tilsvarende element i matrixrepræsentationen. Da der er mindst to felter i hver knude et for datafeltet og andet til at gemme adressen på den næste knude, medens der i tilknyttet repræsentation kun er datafelt der. Fortjenesten ved at bruge den tilknyttede repræsentation bliver åbenlyst, når det kræves at indsætte eller slette et element midt i en gruppe af andre elementer.

Operationer på stak

De grundlæggende operationer, der kan betjenes på stakken, er som følger:

SKUBBE: Når et nyt element føjes til toppen af stakken kaldes PUSH-operation. Ved at skubbe et element i stakken påkaldes tilføjelse af elementet, da det nye element indsættes øverst. Efter hver skubbeoperation øges toppen med en. Hvis matrixen er fuld, og der ikke kan tilføjes noget nyt element, kaldes det STACK-FULL-tilstand eller STACK OVERFLOW. PUSH OPERATION - funktion i C:
Betragtning af stak er erklæret som
int stack, top = -1;
tomt skub ()
{
int vare;
hvis (øverste <4)
{
f ("Indtast nummeret");
scanning ("% d", & vare);
top = top + 1;
stak = vare;
}
andet
{
f ("Stakken er fuld");
}
}
POP: Når et element slettes fra toppen af stakken kaldes det POP-operation. Stakken formindskes med en efter hver pop-operation. Hvis der ikke er noget element tilbage på stakken, og popen udføres, vil dette resultere i STACK UNDERFLOW-tilstand, hvilket betyder, at din stak er tom. POP-BETJENING - funktioner i C:
Betragtning af stak er erklæret som
int stack, top = -1;
ugyldig pop ()
{
int vare;
hvis (top> = 4)
{
vare = stak;
top = top - 1;
f ("Antal slettet er =% d", vare);
}
andet
{
f ("Stakken er tom");
}
}

Handlinger i en kø

De grundlæggende handlinger, der kan udføres i køen er:

Sæt i kø: Sådan indsættes et element i en kø. Indtastningsfunktion i C:
Kø erklæres som
int kø, Front = -1 og bageste = -1;
ugyldig tilføjelse ()
{
int vare;
hvis (bag <4)
{
f ("Indtast nummeret");
scanning ("% d", & vare);
if (front == -1)
{
front = 0;
bageste = 0;
}
andet
{
bageste = bageste + 1;
}
kø = vare;
}
andet
{
f ("Køen er fuld");
}
}
dequeue: Sådan slettes et element fra køen. Fremhævelsesfunktion i C:
Kø erklæres som
int kø, Front = -1 og bageste = -1;
ugyldig sletning ()
{
int vare;
hvis (foran! = -1)
{
vare = kø;
if (foran == bag)
{
front = -1;
bageste = -1;
}
andet
{
front = front + 1;
f ("Antal slettet er =% d", vare);
}
}
andet
{
f ("Køen er tom");
}
}

Anvendelser af Stack

Parring i en compiler.
Java virtuel maskine.
Fortryd i en tekstbehandler.
Tilbage-knap i en webbrowser.
PostScript-sprog for ers.
Implementeringsfunktionsopkald i en compiler.

Anvendelser af kø

Data buffere
Asynkron dataoverførsel (fil IO, rør, stikkontakter).
Tildeling af anmodninger på en delt ressource (er, processor).
Trafikanalyse.
Bestem antallet af kasserer, der skal have i et supermarked.

Konklusion

Stabel og kø er lineære datastrukturer er forskellige på visse måder som arbejdsmekanisme, struktur, implementering, varianter, men begge bruges til at gemme elementerne på listen og udføre operationer på listen som tilføjelse og sletning af elementerne. Selvom der er nogle begrænsninger af den enkle kø, der er samlet tilbage ved hjælp af andre typer kø.