Migliore risposta
In informatica , un tipo di dati astratto ( ADT ) è un modello matematico per tipi di dati in cui un tipo di dati è definito dal suo comportamento ( semantica ) dal punto di vista di un utente dei dati, in particolare in termini di valori possibili, possibili operazioni su dati di questo tipo e comportamento di queste operazioni. Ciò contrasta con le strutture di dati , che sono rappresentazioni concrete di dati e sono il punto di vista di un implementatore, non di un utente.
Da Struttura dati :
In informatica , un struttura dei dati è un modo particolare di organizzare i dati in un computer in modo che possano essere utilizzati in modo efficiente .
Le strutture di dati possono implementare uno o più tipi di dati astratti particolari (ADT), che sono i mezzi per specificare il contratto di operazioni e la loro complessità
Una struttura dati è unimplementazione concreta del contratto fornito da un ADT
Ciò significa:
1. ADT è una rappresentazione astratta , dal punto di vista dellutente
2. DS è una rappresentazione concreta , non dal punto di vista dellutente
In termini semplici:
1. Stack è ADT , specifica solo che ci dovrebbe essere un push, pop, ecc. che lutente può utilizzare.
2. Stack (come altri ADT come Queue) è implementato utilizzando DS come array o elenco (elenco collegato, ecc.)
Riepilogo:
Stack non è DS, è ADT e viene implementato utilizzando altri DS.
Spero di aver aiutato.
Buona fortuna
Risposta
Pile
Una pila è un contenitore di oggetti che vengono inseriti e rimossi secondo il principio dellultimo in primo luogo (LIFO). Negli stack pushdown sono consentite solo due operazioni: spingere lelemento nello stack e pop lelemento fuori dalla pila. Uno stack è una struttura di dati ad accesso limitato: gli elementi possono essere aggiunti e rimossi dallo stack solo in alto. push aggiunge un elemento in cima alla pila, pop rimuove lelemento dallalto . Unanalogia utile è pensare a una pila di libri; puoi rimuovere solo il libro in alto, inoltre puoi aggiungere un nuovo libro in alto.
Uno stack è una struttura di dati ricorsiva . Ecco una definizione strutturale di uno Stack:
Applicazioni
- Lapplicazione più semplice di uno stack è invertire una parola. Spingi una data parola nello stack – lettera per lettera – e poi estrai le lettere dallo stack.
- Unaltra applicazione è un meccanismo di “annullamento” negli editor di testo; questa operazione viene eseguita mantenendo tutte le modifiche al testo in una pila. Backtracking . Questo è un processo quando è necessario accedere allelemento di dati più recente in una serie di elementi. Pensa a un labirinto oa un labirinto: come fai a trovare una via da unentrata a unuscita? Una volta raggiunto un vicolo cieco, devi tornare sui tuoi passi. Ma tornare indietro dove? al punto di scelta precedente. Pertanto, in ogni punto di scelta si memorizzano in una pila tutte le scelte possibili. Quindi tornare indietro significa semplicemente estrarre una scelta successiva dallo stack.
- Elaborazione del linguaggio: lo spazio per i parametri e le variabili locali viene creato internamente utilizzando uno stack.compiler. per la ricorsione
Implementazione
Nella libreria standard di classi, lo stack del tipo di dati è un adapter , il che significa che uno stack è costruito sopra altre strutture di dati. La struttura sottostante per uno stack potrebbe essere un array, un vettore, un ArrayList, un elenco collegato o qualsiasi altra raccolta. Indipendentemente dal tipo di struttura dati sottostante, uno Stack deve implementare la stessa funzionalità.Ciò si ottiene fornendo uninterfaccia unica:
public interface StackInterface
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
Il Limmagine seguente mostra lidea di implementazione per composizione .
Un altro requisito di implementazione (oltre allinterfaccia precedente) è che tutte le operazioni sullo stack devono essere eseguite in
tempo costante O (1)
. Tempo costante significa che esiste una costante k tale che unoperazione richiede k nanosecondi di tempo di calcolo indipendentemente dalla dimensione dello stack.
Implementazione basata su array
In unimplementazione basata su array manteniamo i seguenti campi: un array A di dimensione predefinita (≥ 1 ), la variabile top che fa riferimento allelemento superiore nello stack e la capacità che si riferisce alla dimensione dellarray. La variabile top cambia da -1 a capacity - 1. Diciamo che uno stack è vuoto quando top = -1 e lo stack è pieno quando top = capacity-1.
In un fisso -size stack astraction, la capacità rimane invariata, quindi quando top raggiunge capacità , lo stack loggetto genera uneccezione.
In unastrazione dello stack dinamico quando top raggiunge la capacità , raddoppiamo la dimensione dello stack.
Implementazione basata su elenchi collegati
Basati su elenchi collegati limplementazione fornisce la migliore implementazione dello stack dinamico (dal punto di vista dellefficienza).
Sorgente – Stack e code