Stacks e code basati su array vs elenchi

Question

Sto cercando di confrontare i tassi di crescita (sia in fase di esecuzione che di spazio) per le operazioni stack e code quando implementati come array e come elenchi collegati. Finora sono stato in grado di trovare solo tempi medi di esecuzione dei casi per la coda pop() s, ma nulla che esplori in modo esaustivo queste due strutture di dati e paragoni i loro comportamenti di run-time/spazio.

In particolare, sto cercando di confrontare push() e pop() sia per le code e pile, implementato come sia array e le liste concatenate (quindi 2 operazioni x 2 x 2 strutture implementazioni, o 8 valori).

Inoltre, apprezzerei i valori migliori, medi e pessimi per entrambi, e tutto ciò che riguarda la quantità di spazio che consumano.

La cosa più vicina che ho potuto trovare è questa "scheda madre di tutti i fogli elettronici" pdf che è chiaramente un foglio di trucchi di livello avanzato o master di algoritmi avanzati e funzioni discrete.

Sto solo cercando un modo per determinare quando e dove dovrei utilizzare un'implementazione basata su array rispetto a un'implementazione basata su elenchi per stack e code.

Answer 1

Esistono diversi modi per implementare code e stack con elenchi e matrici collegati e non sono sicuro di quali si stiano cercando. Prima di analizzare una qualsiasi di queste strutture, tuttavia, esaminiamo alcune importanti considerazioni sul runtime per le strutture di dati di cui sopra.

In un elenco a collegamento singolo con solo un puntatore testa, il costo per anteporre un valore è O (1) - semplicemente creiamo il nuovo elemento, leghiamo il puntatore al punto precedente, quindi aggiorniamo il puntatore della testa. Il costo per eliminare il primo elemento è anche O (1), operazione che viene eseguita aggiornando il puntatore head per puntare all'elemento dopo il capo corrente, quindi liberando la memoria per la vecchia testata (se viene eseguita una gestione esplicita della memoria). Tuttavia, i fattori costanti in questi termini O (1) possono essere elevati a causa della spesa delle allocazioni dinamiche. L'overhead di memoria dell'elenco collegato è solitamente O (n) memoria extra totale dovuta alla memorizzazione di un puntatore aggiuntivo in ciascun elemento.

In una matrice dinamica, è possibile accedere a qualsiasi elemento in O (1). Possiamo anche aggiungere un elemento in amortized O(1), il che significa che il tempo totale per n inserimenti è O (n), sebbene i limiti di tempo effettivi su ogni inserimento possano essere molto peggiori.In genere, gli array dinamici vengono implementati inserendo la maggior parte degli inserimenti in O (1) aggiungendo spazio preallocato, ma eseguendo un numero limitato di inserimenti nel tempo Θ (n) raddoppiando la capacità dell'array e copiando gli elementi. Esistono tecniche per cercare di ridurlo allocando uno spazio extra e copiando pigramente gli elementi (vedi this data structure, per esempio). In genere, l'utilizzo della memoria di un array dinamico è abbastanza buono - quando l'array è completamente pieno, ad esempio, c'è solo O (1) overhead - anche se subito dopo che l'array ha raddoppiato le dimensioni potrebbe esserci O (n) inutilizzato elementi allocati nell'array. Poiché le allocazioni sono infrequenti e gli accessi sono veloci, gli array dinamici sono in genere più veloci degli elenchi collegati.

Ora, pensiamo a come implementare uno stack e una coda utilizzando un elenco collegato o un array dinamico. Ci sono molti modi per farlo, quindi mi si assume che si sta utilizzando le seguenti implementazioni:

• Stack:
  • lista collegata: Come singly-linked list con un puntatore di testa.
  • Array: Come dynamic array
• coda:
  • lista collegata: Come lista semplicemente legata con un puntatore testa e coda.
  • Array: come circular buffer supportato da un array.

Consideriamo uno alla volta.

Stack supportato da un elenco collegato separatamente. Poiché un elenco collegato singolarmente supporta O (1) time ante e delete-first, il costo da spingere o inserire in uno stack con backlist collegato è anche O (1) worst case. Tuttavia, ogni nuovo elemento aggiunto richiede una nuova allocazione e le allocazioni possono essere costose rispetto ad altre operazioni.

Stack supportato da un array dinamico. La spinta allo stack può essere implementata aggiungendo un nuovo elemento all'array dinamico, che impiega il tempo O (1) e il tempo O (n) peggiori. Popping dallo stack può essere implementato rimuovendo solo l'ultimo elemento, che viene eseguito nel caso peggiore O (1) (o O (1) ammortizzato se si desidera provare a recuperare spazio inutilizzato). In altre parole, l'implementazione più comune è il push o pop di O (1) best-case, il push O (n) nel caso peggiore e il pop O (1) pop e il push O (1) e O (1) pop ammortizzati.

Coda supportata da un elenco collegato singolarmente. L'accodamento nella lista concatenata può essere implementato accodando alla parte posteriore dell'elenco linkato separatamente, che impiega il tempo O (1) nel caso peggiore. La dequeuing può essere implementata rimuovendo il primo elemento, che prende anche il tempo peggiore O (1). Ciò richiede anche una nuova allocazione per accodamento, che può essere lento.

Coda supportata da un buffer circolare crescente. L'accodamento nel buffer circolare funziona inserendo qualcosa nella successiva posizione libera nel buffer circolare. Questo funziona aumentando la matrice se necessario, quindi inserendo il nuovo elemento. Usando un'analisi simile per l'array dinamico, ciò richiede il tempo ottimale O (1), il caso peggiore O (n) e il tempo ammortizzato O (1). La rimozione delle code dal buffer funziona rimuovendo il primo elemento del buffer circolare, che nel caso peggiore richiede tempo O (1).

Per riassumere, tutte le strutture supportano la pressione e il popping di elementi in tempo O (n). Le versioni delle liste collegate hanno un comportamento peggiore, ma potrebbero avere un runtime complessivo peggiore a causa del numero di allocazioni eseguite. Le versioni dell'array sono più lente nel caso peggiore, ma offrono prestazioni complessive migliori se il tempo per operazione non è troppo importante.

Un'altra opzione che si desidera esaminare per l'implementazione di stack è la VList, una struttura dati recente che è un ibrido di un elenco collegato e un array dinamico. Rende meno allocazioni di una lista collegata e ha meno puntatori in essa, anche se l'utilizzo dello spazio è un po 'più alto nel peggiore dei casi. Potresti anche voler esaminare le chunklist, che sono un altro ibrido di matrici e liste concatenate, che possono essere utilizzate sia per gli stack che per le code.

Spero che questo aiuti!

Answer 2

Scusate se ho frainteso la vostra domanda, ma se non l'ho fatto, credo che questa sia la risposta che state cercando.

Con un vettore, è possibile aggiungere/eliminare elementi in modo efficiente alla fine del contenitore. Con un deque, è possibile aggiungere/eliminare in modo efficiente gli elementi all'inizio/alla fine del contenitore. Con un elenco, puoi inserire/eliminare in modo efficiente elementi in qualsiasi punto del contenitore.

vettori/deque consentono iteratori di accesso casuale. Gli elenchi consentono solo l'accesso sequenziale.

Il modo in cui è necessario utilizzare e memorizzare i dati è il modo in cui si determina quale è più appropriato.

EDIT:

C'è molto di più per questo, la mia risposta è molto generalizzato. Posso approfondire se sono in grado di capire di cosa si tratta.