Si può usare un albero per creare uno stack?

Question

Si può usare un albero per creare uno stack?

#1 da (2 voti)
#2 da (0 voti)

4

Sono consapevole che elenchi, set e array collegati possono essere utilizzati per creare stack da soli. La teoria dietro questo è

linked-list : in alcune lingue, una lista collegata è sostituibile per una matrice. Le pile sono operazioni First In First Out.

array : i metodi push e pop richiamano un comportamento simile allo stack.

set : un set è esattamente uguale a un array, tranne per il fatto che non presenta elementi duplicati.

Sto facendo fatica a trovare un modo in cui un albero può essere usato per creare uno stack

data-structures trees stack

posta Joseph Monroe 08.02.2016 - 21:54

fonte

2 risposte

Leggi altre domande sui tag data-structures trees stack

Quali algoritmi devo esaminare? Come funziona I / O per database di grandi dimensioni?

score 2 · Answer 1

Banalmente.

Il tuo oggetto stack mantiene semplicemente un albero di interi. L'operazione Push è identica all'inserimento di un oggetto nell'albero la cui chiave è maggiore di una chiave nel massimo corrente. Questa dovrebbe essere la chiave nella nota fondamentale e il nuovo nodo diventa la nuova radice.

L'operazione Pop è la rimozione del nodo con la chiave più grande (la radice).

Questo approccio dovrebbe ancora funzionare con gli alberi di auto-bilanciamento, anche se per quelli sarà più lento (dal momento che la chiave massima non è più nella radice e quindi l'accesso richiede O (ln N) piuttosto che O (1)).

Il contenuto delle posizioni dello stack sarebbe semplicemente un contenuto aggiuntivo nei nodi dell'albero.

score 0 · Answer 2

0

C'è già una buona risposta, ma potresti anche implementare un max-heap e quindi inserire un elemento con una priorità uguale al numero di elementi attualmente nel tuo heap.

risposta data 09.02.2016 - 04:39

fonte