Conţinut

• Diagramă de comparație
• Definiția Stack
• Exemplu
• Definiția Queue
• Exemplu
• Implementarea stivei
• Implementarea cozii
• Operațiuni pe stivă
• Operațiuni pe o coadă
• Aplicații Stack
• Aplicații ale cozii
• Concluzie

Stack și Coadă sunt ambele structuri de date non-primitive. Principalele diferențe între stivă și coadă sunt faptul că stiva utilizează metoda LIFO (ultima în primul ieșire) pentru a accesa și adăuga elemente de date, în timp ce Queue folosește metoda FIFO (First in first out) pentru a accesa și adăuga elemente de date.

Stack are doar un capăt deschis pentru împingerea și apariția elementelor de date, pe de altă parte Queue are ambele capete deschise pentru obținerea și eliminarea elementelor de date.

Stiva și coada sunt structurile de date utilizate pentru stocarea elementelor de date și se bazează de fapt pe un echivalent din lumea reală. De exemplu, stiva este o stivă de CD-uri de unde puteți scoate și introduce în CD prin partea de sus a stivei de CD-uri. În mod similar, Coada este o coadă pentru biletele de la Teatru în care persoana care stă pe primul loc, adică fața cozii va fi servită mai întâi, iar noua persoană sosită va apărea în spatele cozii (partea din spate a cozii).

1. Diagramă de comparație
2. Definiție
3. Diferențele cheie
4. Punerea în aplicare
5. Operațiuni
6. Aplicații
7. Concluzie

Diagramă de comparație

Baza de comparație	Grămadă	Coadă
Principiul de funcționare	LIFO (Last in First out)	FIFO (Primul în primul rând)
Structura	Același capăt este folosit pentru a insera și șterge elemente.	Un capăt este utilizat pentru inserare, adică, partea din spate și un alt capăt este utilizat pentru ștergerea elementelor, adică capătul frontal.
Numărul de indicatoare utilizate	unu	Două (În cazul cozii simple)
Operațiunile efectuate	Împingeți și Pop	Enqueue și dequeue
Examinarea stării goale	Top == -1	Față == -1 || Față == Spate + 1
Examinarea stării complete	Top == Max - 1	Spate == Max - 1
variante	Nu are variante.	Are variante precum coadă circulară, coadă de prioritate, coadă de două ori terminată.
Punerea în aplicare	Simpler	Comparativ complex

Definiția Stack

Un Stack este o structură liniară de date non-primitivă. Este o listă ordonată în care se adaugă noul element și elementul existent este șters dintr-un singur capăt, denumit drept partea superioară a stivei (TOS). Întrucât toată ștergerea și inserarea într-o stivă se face din partea superioară 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 tipul Last-in-First-out (LIFO).

Rețineți că elementul accesat adesea în stivă este cel mai de sus element, în timp ce ultimul element disponibil se află în partea de jos a stivei.

Exemplu

Unii dintre voi pot mânca biscuiți (sau Poppins). Dacă presupuneți, doar o parte a capacului este ruptă, iar biscuiții sunt scoș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, îi veți pune din nou în ambalaj prin același capăt sfâșiat se numește împingere.

Definiția Queue

O coadă este o structură liniară de date intră î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 capăt posterior. În mod similar, ștergerea elementelor existente are loc la celălalt capăt numit Front-end și este, în mod logic, un tip de listă First in first out (FIFO).

Exemplu

În viața noastră de zi cu zi întâlnim multe situații în care așteptăm să așteptăm serviciul dorit, acolo trebuie să ajungem în linia de așteptare pentru a ne întoarce rândul. Această coadă de așteptare poate fi gândită ca o coadă.

1. Stack urmează mecanismul LIFO pe de altă parte Coada urmărește mecanismul FIFO pentru a adăuga și elimina elemente.
2. Într-o stivă, același capăt este utilizat pentru a insera și șterge elementele. Dimpotrivă, în coadă sunt folosite două capete diferite pentru a insera și șterge elementele.
3. Ca Stack au un singur capăt deschis, acesta este motivul pentru care se utilizează un singur indicator pentru a se referi la partea de sus a stivei. Dar coada folosește doi indicatori pentru a referi partea din față și partea din spate a cozii.
4. Stack efectuează două operațiuni cunoscute sub numele de push and pop, în timp ce în Queue, cunoscut sub numele de enqueue și dequeue.
5. Implementarea stivei este mai ușoară, în timp ce implementarea cozii este complicată.
6. Coada are variante precum coada circulară, coada de prioritate, coada de două ori terminată etc. În schimb, stiva nu are variante.

Implementarea stivei

Stiva poate fi aplicată în două moduri:

1. Implementarea statică utilizează tablouri pentru a crea o stivă. Implementarea statică este totuși o tehnică fără efort, dar nu este un mod flexibil de creare, întrucât declararea mărimii 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 un tablou (pentru implementarea stivei) este declarat înainte de începerea operațiunii (la momentul proiectării programului). Acum, dacă numărul de elemente care trebuie sortate este foarte mic în stivă, memoria alocată static va fi irosită. Pe de altă parte, dacă mai sunt mai multe elemente care trebuie stocate în stivă, nu vom putea modifica dimensiunea tabloului pentru a-i crește capacitatea, astfel încât să poată găzdui elemente noi.
2. Implementare dinamică este, de asemenea, numit reprezentare listă legată și folosește indicatoare pentru a implementa tipul de stivă a structurii de date.

Implementarea cozii

Coada poate fi implementată în două moduri:

1. Implementarea statică: Dacă o coadă este implementată folosind matricile, numărul exact de elemente pe care dorim să le stocăm în coadă trebuie asigurat anterior, deoarece dimensiunea tabloului trebuie declarată la momentul proiectării sau înainte de începerea procesării. În acest caz, începutul tabloului va deveni partea din față a cozii, iar ultima locație a tabloului va acționa ca partea din spate a cozii. Următoarea relație oferă ca elementele întregi să existe în coadă atunci când sunt implementate folosind tablouri:
   fata - spate + 1
   Dacă „spate <față”, atunci nu va fi niciun element în coadă sau coada va fi întotdeauna goală.
2. Implementare dinamică: Implementând cozi folosind indicatoare, principalul dezavantaj este că un nod dintr-o reprezentare legată consumă mai mult spațiu de memorie decât un element corespunzător din reprezentarea tabloului. Întrucât există cel puțin două câmpuri în fiecare nod, unul pentru câmpul de date și celălalt pentru a stoca adresa următorului nod, în timp ce în reprezentare legată există doar câmpul de date. Meritul de a utiliza reprezentarea legată 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 stivă

Operațiunile de bază care pot fi operate pe stivă sunt următoarele:

1. APĂSAȚI: când un element nou este adăugat în partea de sus a stivei este cunoscut sub numele de operare PUSH. Apăsarea unui element în stivă invocă adăugarea elementului, deoarece noul element va fi inserat în partea de sus. După fiecare operație de împingere, partea superioară este mărită cu una. Dacă matricea este plină și nu se poate adăuga niciun element nou, se numește STACK-FULL condiție sau STACK OVERFLOW. FUNCȚIONARE PUSH - funcție în C:
   Considerând stiva este declarată ca
   int stack, top = -1;
void push ()
{
element int;
if (top <4)
{
f ("Introduceți numărul");
scanare ("% d", & element);
top = top + 1;
stivă = articol;
}
altfel
{
f („Stiva este plină”);
}
}
2. POP: Când un element este șters din partea superioară a stivei, este cunoscut sub numele de operare POP. Stiva este scăzută cu una, după fiecare operație pop. Dacă nu stă niciun element în stivă și pop-ul este executat, atunci va rezulta starea STACK UNDERFLOW, ceea ce înseamnă că stiva dvs. este goală. OPERAȚIE POP - funcții în C:
   Considerând stiva este declarată ca
   int stack, top = -1;
void pop ()
{
element int;
if (top> = 4)
{
articol = stiva;
top = top - 1;
f ("Numărul șters este =% d", articol);
}
altfel
{
f („Stiva este goală”);
}
}

Operațiuni pe o coadă

Operațiile de bază care pot fi efectuate pe coadă sunt:

1. Puneți în coadă: Pentru a insera un element într-o coadă. Efectuarea funcției de operare în C:
   Coada este declarată ca
   int coadă, Față = -1 și spate = -1;
void add ()
{
element int;
if (spate <4)
{
f ("Introduceți numărul");
scanare ("% d", & element);
if (front == -1)
{
fata = 0;
spate = 0;
}
altfel
{
spate = spate + 1;
}
coadă = element;
}
altfel
{
f ("Coada este plină");
}
}

2. Dequeue: Pentru a șterge un element din coada.Enceperea funcției de operare în C:
   Coada este declarată ca
   int coadă, Față = -1 și spate = -1;
void delete ()
{
element int;
if (front! = -1)
{
item = coada;
if (fata == spate)
{
fata = -1;
spate = -1;
}
altfel
{
fata = fata + 1;
f ("Numărul șters este =% d", articol);
}
}
altfel
{
f ("Coada este goală");
}
}

Aplicații Stack

• Parsing într-un compilator.
• Mașină virtuală Java.
• Anulați un procesor de texte.
• Butonul Înapoi într-un browser Web.
• Limba PostScript pentru ers.
• Implementarea apelurilor funcționale într-un compilator.

Aplicații ale cozii

• Buffere de date
• Transfer asincron de date (fișier IO, conducte, prize).
• Alocarea cererilor pe o resursă partajată (er, procesor).
• Analiza traficului.
• Determinați numărul de casiere pe care le aveți la un supermarket.

Concluzie

Stack și Coada sunt structuri liniare de date diferă în anumite moduri, cum ar fi mecanismul de lucru, structura, implementarea, variante, dar ambele sunt utilizate pentru stocarea elementelor din listă și pentru efectuarea operațiunilor din listă, precum adăugarea și ștergerea elementelor. Deși există unele limitări ale cozii simple, care este retușată prin utilizarea altor tipuri de coadă.