Razlika između hrpe i redova

• 2019

Stack and Queue oba su ne-primitivne strukture podataka. Glavne razlike između stogova i reda su to da stog koristi LIFO (posljednji na prvi izlaz) metodu za pristup i dodavanje elemenata podataka, dok Queue koristi FIFO (prvi na prvi izlaz) metodu za pristup i dodavanje elemenata podataka.

Stack ima samo jedan kraj otvoren za guranje i iskakanje podataka elemenata s druge strane Queue ima oba kraja otvorena za enqueuing i dequeuing podataka elemenata.

Stog i red su strukture podataka koje se koriste za pohranjivanje elemenata podataka i zapravo se temelje na nekom ekvivalentu stvarnog svijeta. Na primjer, stog je hrpa CD-a gdje možete izvaditi i staviti CD na vrh hrpe CD-ova. Slično tome, red je red čekanja za kazališne ulaznice gdje će osoba koja stoji na prvom mjestu, tj. Ispred reda čekanja, biti prvi poslužena, a nova osoba koja dolazi stići će se pojaviti na poleđini reda (stražnji kraj reda čekanja).

Tablica usporedbe

Osnova za usporedbu	Stog	Red
Princip rada	LIFO (posljednji na prvom mjestu)	FIFO (prvi na prvom izlazu)
Struktura	Isti se kraj koristi za umetanje i brisanje elemenata.	Jedan kraj se koristi za umetanje, tj. Stražnji kraj, a drugi kraj se koristi za brisanje elemenata, tj. Prednji kraj.
Broj korištenih pokazivača	Jedan	Dva (u slučaju jednostavnog reda čekanja)
Operacije izvršene	Push i pop	Upišite i odjavite
Ispitivanje praznog stanja	Vrh == -1	Naprijed == -1 || Ispred == Straga + 1
Pregled punog stanja	Vrh == Maks - 1	Stražnji == Max - 1
varijante	Nema varijante.	Ima varijante poput kružnog reda, prioritetnog reda, dvostruko završenog reda.
izvršenje	jednostavnije	Komparativno složen

Definicija stog

Stack je ne-primitivna linearna podatkovna struktura. To je uređena lista gdje se dodaje nova stavka i postojeći se element briše samo s jednog kraja, koji se zove vrh stog (TOS). Budući da se sva brisanja i umetanja u stog obavljaju s vrha stog, posljednji dodani element bit će prvi koji će biti uklonjen iz stog. To je razlog zbog kojeg se stog zove Last-in-First-Out (LIFO) tip popisa.

Napominjemo da je element koji se često pristupa u stogu najviši element, dok je zadnji dostupan element na dnu hrpe.

Primjer

Neki od vas mogu jesti keks (ili Poppins). Ako pretpostavite, samo je jedna strana poklopca poderana, a keksi se izvode jedan po jedan. To je ono što se naziva iskakanje, i slično, ako želite sačuvati neke keksove neko vrijeme kasnije, vratit ćete ih natrag u čopor kroz isti poderani kraj koji se zove guranje.

Definicija reda čekanja

Red je linearna podatkovna struktura koja dolazi u kategoriju ne-primitivnog tipa. To je skup sličnih elemenata. Dodavanje novih elemenata odvija se na jednom kraju nazvanom stražnji kraj. Slično tome, brisanje postojećih elemenata odvija se na drugom kraju nazvanom Front-end, a logički je tip popisa First in first out (FIFO).

Primjer

U našem svakodnevnom životu nailazimo na mnoge situacije u kojima čekamo željenu uslugu, tamo moramo ući u red čekanja za naš red za servisiranje. Taj red čekanja može se smatrati redom.

Ključne razlike između skupa i redova

1. Stack slijedi LIFO mehanizam s druge strane Queue slijedi FIFO mehanizam za dodavanje i uklanjanje elemenata.
2. U stog se isti kraj koristi za umetanje i brisanje elemenata. Naprotiv, dva reda se koriste u redu za umetanje i brisanje elemenata.
3. Budući da Stack ima samo jedan otvoreni kraj, to je razlog za korištenje samo jednog pokazivača za upućivanje na vrh stog. No, red koristi dva pokazivača za upućivanje na prednji i stražnji kraj reda.
4. Stack izvršava dvije operacije poznate kao push i pop dok je u Queueu poznat kao enqueue i dequeue.
5. Implementacija stogova je lakša, a implementacija reda je lukav.
6. Red ima varijante poput kružnog reda, prioritetnog reda, dvostruko završenog reda, itd. Nasuprot tome, stog nema varijante.

Implementacija stogova

Stog se može primijeniti na dva načina:

1. Statična implementacija koristi nizove za stvaranje stogova. Statička implementacija je tehnika bez napora, ali nije fleksibilan način stvaranja, budući da se deklaracija o veličini hrpe mora obaviti tijekom izrade programa, nakon čega se veličina ne može mijenjati. Osim toga, statična implementacija nije vrlo učinkovita u pogledu korištenja memorije. Budući da je polje (za implementaciju stog) deklarirano prije početka operacije (u vrijeme programiranja). Sada, ako je broj elemenata koje treba razvrstati u stacku mnogo manji, statički dodijeljena memorija će se izgubiti. S druge strane, ako ima više elemenata koji će se pohraniti u stog tada ne možemo promijeniti veličinu polja kako bi se povećao njegov kapacitet, tako da može primiti nove elemente.
2. Dinamička implementacija također se naziva povezivanje s povezanim popisom i koristi pokazivače za implementaciju tipa podatkovne strukture.

Implementacija reda čekanja

Redovi se mogu implementirati na dva načina:

1. Statička implementacija : Ako je red implementiran pomoću nizova, točan broj elemenata koje želimo pohraniti u red mora biti osiguran prije, jer se veličina polja mora deklarirati u vrijeme dizajna ili prije početka obrade. U tom slučaju, početak niza će postati prednji dio reda, a posljednja lokacija polja djelovat će kao stražnji dio reda. Sljedeći odnos daje cjelovite elemente koji postoje u redu kada se implementiraju pomoću polja:
   sprijeda - straga + 1
   Ako "straga <ispred" tada neće biti elementa u redu čekanja ili red će uvijek biti prazan.
2. Dinamička implementacija : Implementacija redova pomoću pokazivača, glavni nedostatak je da čvor u povezanom predstavljanju troši više memorijskog prostora nego odgovarajući element u prikazu niza. Budući da u svakom čvoru postoje najmanje dva polja za podatkovno polje i drugo za spremanje adrese sljedećeg čvora, dok je u povezanom prikazu samo podatkovno polje. Zasluga korištenja povezane reprezentacije postaje očigledna kada je potrebno umetnuti ili izbrisati element u sredini grupe drugih elemenata.

Operacije na Stacku

Osnovne operacije koje se mogu izvoditi na stog su sljedeće:

1. PUSH : kada se novi element doda na vrh stog poznat je kao PUSH operacija. Guranje elementa u stog poziva na dodavanje elementa, budući da će novi element biti umetnut na vrhu. Nakon svakog potiskivanja, vrh se povećava za jedan. Ako je polje puno i ne može se dodati novi element, to se naziva STACK-FULL uvjet ili STACK OVERFLOW. PUSH OPERATION - funkcija u C:
   S obzirom da je stog deklariran kao
   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 : kada se element briše s vrha hrpe, poznat je kao POP operacija. Stack se smanjuje za jedan, nakon svake operacije popa. Ako nema nijednog elementa na stog i pop se izvodi, to će rezultirati STACK UNDERFLOW uvjetom što znači da je vaš stack Empty. POP OPERACIJA - funkcionira u C:
   S obzirom da je stog deklariran kao
   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");
}
}

Operacije u redu

Osnovne operacije koje se mogu izvršiti na redu su:

1. Enqueue : Za umetanje elementa u red čekanja.
   Red je deklariran kao
   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 : Za brisanje elementa iz reda čekanja.
   Red je deklariran kao
   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") ;
}
}

Aplikacije Stack-a

• Raščlanjivanje u prevodiocu.
• Java virtualni stroj.
• Poništite u programu za obradu teksta.
• Gumb Natrag u web-pregledniku.
• PostScript jezik za pisače.
• Primjena poziva funkcije u kompilatoru.

Aplikacije reda čekanja

• Spremnici podataka
• Asinkroni prijenos podataka (datoteka IO, cijevi, utičnice).
• Dodjela zahtjeva na zajednički resurs (pisač, procesor).
• Analiza prometa.
• Odredite broj blagajnika u supermarketu.

Zaključak

Stack i Queue su linearne strukture podataka koje se razlikuju na određene načine kao što su radni mehanizam, struktura, implementacija, varijante, ali se oba koriste za pohranjivanje elemenata na popisu i izvođenje operacija na popisu kao što su dodavanje i brisanje elemenata. Iako postoje neka ograničenja jednostavnog reda koji se oporavlja pomoću drugih vrsta redova.