Cel mai bun răspuns
De la Tip de date abstract:
În informatică , un tip de date abstract ( ADT ) este un model matematic pentru tipuri de date în care un tip de date este definit de comportamentul său ( semantică ) din punctul de vedere al unui user al datelor, în special în ceea ce privește valorile posibile, posibilele operațiuni pe date de acest tip și comportamentul acestor operații. Acest lucru contrastează cu structuri de date , care sunt reprezentări concrete ale datelor și sunt punctul de vedere al unui implementator, nu al unui utilizator.
Din Structura datelor :
În informatică , un structura datelor este un mod particular de organizare a date într-un computer, astfel încât să poată fi utilizate eficient .
Structurile de date pot implementa unul sau mai multe tipuri de date abstracte (ADT), care sunt mijloacele de specificare a contractului de operațiuni și complexitatea
O structură de date este o implementare concretă a contractului furnizat de un ADT
Ce înseamnă asta:
1. ADT este reprezentare abstractă , din punctul de vedere al utilizatorului
2. DS este reprezentare concretă , nu din punctul de vedere al utilizatorului
În termeni simpli:
1. Stiva este ADT , specifică doar că ar trebui să existe un push, pop etc. pentru a fi utilizat de utilizator.
2. Stiva (ca și alte ADT-uri, cum ar fi Coadă) este implementată utilizând DS ca matrice sau listă (listă legată etc.)
Rezumat:
Stiva nu este DS, este ADT și este implementată folosind alte DS.
Speranță care a ajutat.
Mult noroc
Răspuns
Stive
O stivă este un container de obiecte care sunt inserate și îndepărtate conform principiului last-in first-out (LIFO). În stive pushdown sunt permise doar două operații: împingeți elementul în stivă și pop elementul din stivă. O stivă este o structură de date cu acces limitat – elementele pot fi adăugate și eliminate din stivă doar în partea de sus. push adaugă un element în partea de sus a stivei, pop elimină articolul din partea de sus . O analogie utilă este să ne gândim la un teanc de cărți; puteți elimina doar cartea de sus, de asemenea, puteți adăuga o carte nouă în partea de sus.
O stivă este o structură de date recursivă . Iată o definiție structurală a unei stive:
Aplicații
- Cea mai simplă aplicație a unui stack este inversarea unui cuvânt. Apăsați un cuvânt dat în stivă – literă cu literă – și apoi scoateți literele din stivă.
- O altă aplicație este un mecanism de „anulare” în editorii de text; această operațiune se realizează prin păstrarea tuturor modificărilor de text într-o stivă. Backtracking . Acesta este un proces în care trebuie să accesați cel mai recent element de date dintr-o serie de elemente. Gândiți-vă la un labirint sau la un labirint – cum găsiți o cale de la o intrare la o ieșire? Odată ce ați ajuns într-o fundătură, trebuie să vă retrageți. Dar retrogradarea unde? până la punctul de alegere anterior. Prin urmare, la fiecare punct de alegere stocați pe un teanc toate opțiunile posibile. Apoi backtracking înseamnă pur și simplu să alegeți o următoare alegere din stivă.
- Prelucrarea limbii: spațiul pentru parametri și variabilele locale este creat intern utilizând o verificare a sintaxei unui stack.com. pentru recursivitate
Implementare
În biblioteca standard de clase, stiva de tipuri de date este o adaptor , ceea ce înseamnă că o stivă este construită deasupra altor structuri de date. Structura care stă la baza unei stive ar putea fi o matrice, un vector, o ArrayList, lista legată sau orice altă colecție. Indiferent de tipul structurii de date subiacente, o stivă trebuie să implementeze aceeași funcționalitate.Acest lucru se realizează prin furnizarea unei interfețe unice:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
imaginea următoare demonstrează ideea implementării prin compoziție .
O altă cerință de implementare (în plus față de interfața de mai sus) este că toate operațiunile stivei trebuie să ruleze în
timpul constant O (1)
. Timp constant înseamnă că există unele k constante astfel încât o operațiune să ia k nanosecunde de timp de calcul, indiferent de dimensiunea stivei.
Implementare bazată pe matrice
Într-o implementare bazată pe matrice menținem următoarele câmpuri: o matrice A cu o dimensiune implicită (≥ 1 ), variabila top care se referă la elementul de sus din stivă și la capacitate se referă la dimensiunea matricei. Variabila sus se schimbă de la -1 la capacity - 1. Spunem că un teanc este gol când top = -1, iar teancul este plin când top = capacity-1.
Într-un fix -abstracția stivei de dimensiuni, capacitatea rămâne neschimbată, prin urmare, atunci când sus atinge capacitatea , stiva obiectul lansează o excepție.
Într-o abstracție din stivă dinamică atunci când sus atinge capacitate , dublăm dimensiunea stivei.
Implementare bazată pe listă legată
Bazată pe listă legată implementarea oferă cea mai bună implementare a stivei dinamice (din punct de vedere al eficienței).
Sursă – Stive și cozi