Stack-ul are doar un capăt deschis pentru împingerea și scoaterea elementelor de date pe cealaltă parte. Coada are ambele capete deschise pentru enqueuing și dequeuing elementele de date.
Stive și coadă sunt structurile de date utilizate pentru stocarea elementelor de date și se bazează, de fapt, pe anumite echivalente din lumea reală. De exemplu, stiva este o stivă de CD-uri unde puteți scoate și pune CD-ul prin partea superioară a teancului de CD-uri. În mod similar, Coada de așteptare este o coadă pentru bilete de teatru, în care persoana care stă în primul rând, adică partea frontală a coadă, va fi servită mai întâi și noua persoană care va sosi va apărea în partea din spate a coada de așteptare.
Diagramă de comparație
| Bazele de comparație | Grămadă | Coadă |
|---|---|---|
| Principiul de funcționare | LIFO (ultima în prima afară) | FIFO (primul la început) |
| Structura | Același scop este folosit pentru a insera și șterge elemente. | Un capăt este utilizat pentru inserare, adică capătul posterior și altul este utilizat pentru ștergerea elementelor, adică a capătului din față. |
| Numărul de indicii utilizați | unu | Două (în caz de coadă simplu) |
| Operațiunile efectuate | Push și Pop | Înclinați și deghizați |
| Examinarea stării goale | Sus == -1 | Față == -1 || Față == Spate + 1 |
| Examinarea stării complete | Sus == Max - 1 | Spate == Max - 1 |
| variante | Nu are variante. | Are variante precum coada circulară, coada de priorități, coada dublă închisă. |
| Punerea în aplicare | Simpler | Comparativ complex |
Definiția Stack
Stack-ul este o structură liniară non-primitivă. Este o listă ordonată în care elementul nou este adăugat, iar elementul existent este șters de la un singur capăt, numit ca vârful stivei (TOS). Deoarece toate ștergerea și inserarea într-un teanc se face din partea de sus a stivei, ultimul element adăugat va fi primul care va fi eliminat din stivă. Acesta este motivul pentru care stiva se numește lista de tip Last-in-First-out (LIFO).
Rețineți că elementul adesea accesat în teanc este cel mai de sus element, în timp ce ultimul element disponibil este în partea de jos a stivei.
Exemplu
Unii dintre voi pot mânca biscuiți (sau Poppins). Dacă presupuiți că numai o parte a capacului este ruptă și biscuiții sunt luați unul câte unul. Aceasta este ceea ce se numește popping și, în mod similar, dacă doriți să păstrați niște biscuiți pentru ceva timp mai târziu, le veți pune înapoi în pachet prin același sfârșit sfâșiat, numit împingere.
Definiția Queue
O coadă este o structură de date liniară vine în categoria tipului non-primitiv. Este o colecție de tipuri similare de elemente. Adăugarea de elemente noi are loc la un capăt numit spate. În mod similar, ștergerea elementelor existente are loc la celălalt capăt numit front-end și este logic o listă de tip First in first out (FIFO).
Exemplu
În viața noastră de zi cu zi, întâlnim multe situații în care așteptăm serviciul dorit, acolo trebuie să intrăm în linia de așteptare pentru ca rândul nostru să se descurce. Această coadă de așteptare poate fi considerată ca o coadă.
Diferențele cheie între stiva și coadă
- Stivele urmează mecanismul LIFO, pe de altă parte, Queue urmează mecanismul FIFO pentru a adăuga și elimina elemente.
- Într-un teanc, același scop este folosit pentru a insera și a șterge elementele. Dimpotrivă, în coadă sunt folosite două capete diferite pentru a insera și a șterge elementele.
- Deoarece stack-ul are doar un singur capăt deschis, acesta este motivul pentru care se utilizează doar un singur pointer pentru a se referi la partea superioară a teancului. Dar coada utilizează două indicatoare pentru a face referire la partea frontală și cea din spate a coadajului.
- Stack efectuează două operații cunoscute sub numele de "împingere" și "pop" în timp ce în coadă este cunoscută sub numele de "enqueue" și "dequeue".
- Implementarea stivei este mai ușoară, în timp ce implementarea Queue-ului este dificilă.
- Coada are variante cum ar fi coada circulară, coada de priorități, coada dublă închisă etc. În contrast, stiva nu are variante.
Implementarea stivei
Stiva poate fi aplicată în două moduri:
- Implementarea statică folosește arrays pentru a crea un stack. Implementarea statică este, totuși, o tehnică fără efort, dar nu este o modalitate flexibilă de creare, deoarece declararea dimensiunii stivei trebuie făcută în timpul proiectării programului, după care dimensiunea nu poate fi variată. În plus, implementarea statică nu este foarte eficientă în ceea ce privește utilizarea memoriei. Deoarece o matrice (pentru implementarea stiva) este declarată înainte de începerea operației (la momentul programării programului). Acum, dacă numărul de elemente care urmează a fi sortate este foarte scăzut în stivă, memoria alocată static va fi risipită. Pe de altă parte, dacă există mai multe elemente care trebuie stocate în stivă, nu putem schimba dimensiunea matricei pentru a-i crește capacitatea, astfel încât să poată găzdui elemente noi.
- Implementarea dinamică este, de asemenea, numită reprezentare a listei asociate și utilizează pointeri pentru a implementa tipul de structură de tip stivă.
Implementarea coada
Coada poate fi implementată în două moduri:
- Implementarea statică : dacă o coadă este implementată utilizând matrice, trebuie asigurat anterior numărul exact al elementelor pe care dorim să le stocăm în coadă, deoarece dimensiunea matricei trebuie declarată la momentul proiectării sau înainte de începerea procesării. În acest caz, începutul matricei va deveni partea frontală a coadă, iar ultima locație a matricei va acționa ca partea din spate a coadajului. Următoarea relație dă că toate elementele există în coadă atunci când sunt implementate folosind matrice:
față - spate + 1
În cazul în care "spate <față" nu va exista niciun element în coada de așteptare sau coada va fi întotdeauna goală. - Implementarea dinamică : Implementarea cozilor cu indicii, principalul dezavantaj este că un nod dintr-o reprezentare legată consumă mai mult spațiu de memorie decât un element corespondent în reprezentarea matricei. Deoarece există cel puțin două câmpuri în fiecare nod pentru câmpul de date și altele pentru a stoca adresa nodului următor, în timp ce în reprezentarea legată există doar câmpul de date. Meritul utilizării reprezentării legate devine evident atunci când este necesar să inserați sau să ștergeți un element în mijlocul unui grup de alte elemente.
Operațiuni pe Stack
Operațiile de bază care pot fi operate pe stivă sunt următoarele:
- PUSH : atunci când un element nou este adăugat în partea de sus a stivei este cunoscut sub numele de operație PUSH. Apăsarea unui element în stivă invocă adăugarea elementului, deoarece elementul nou va fi introdus în partea de sus. După fiecare operație de împingere, partea superioară este mărită cu una. Dacă matricea este plină și nu poate fi adăugat niciun element nou, se numește stare STACK-FULL sau STACK OVERFLOW. PUSH OPERATION - funcționează în C:
Considerând că stiva este declarată caint 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 : Când un element este șters din partea superioară a stivei, acesta este cunoscut ca funcționare POP. Stiva este scăzută cu una, după fiecare operație pop. Dacă nu mai rămâne niciun element pe stivă și popul este executat, atunci aceasta va duce la condiția STACK UNDERFLOW ceea ce înseamnă că stiva este goală. POP OPERATION - funcționează în C:
Considerând că stiva este declarată caint 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");}}
Operațiuni pe o coadă
Operațiile de bază care pot fi executate pe coadă sunt:
- Enqueue : Pentru a insera un element într-o coadă. Funcția de operare de intrare în C:
Coada este declarată caint 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 : Pentru a șterge un element din coadă.Funcționarea funcției de declanșare în C:
Coada este declarată caint 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") ;}}
Aplicații ale Stack
- Parsarea într-un compilator.
- Mașină virtuală Java.
- Anulați un procesor de text.
- Butonul Înapoi într-un browser Web.
- Limba PostScript pentru imprimante.
- Implementarea apelurilor funcției într-un compilator.
Aplicații ale coada
- Buffere de date
- Transfer de date asincron (fișier IO, țevi, prize).
- Alocarea cererilor pe o resursă partajată (imprimantă, procesor).
- Analiza traficului.
- Determinați numărul de casieri pe care îl aveți la un supermarket.
Concluzie
Stack și Queue sunt structuri de date liniare care diferă în anumite moduri, cum ar fi mecanismul de lucru, structura, implementarea, variantele, dar ambele sunt utilizate pentru stocarea elementelor din listă și pentru efectuarea operațiilor pe listă, cum ar fi adăugarea și ștergerea elementelor. Deși există anumite limitări ale coadajului simplu, care este recuperat prin utilizarea altor tipuri de coadă.
