Applicazione dell'implementazione di 3 stack in un singolo array

3

Bene, ci sono molte discussioni sull'implementazione di 3 (o 2 stack) in un singolo array. Ma qual è il reale bisogno o applicazione per l'implementazione di stack del genere?

Non possiamo assegnare memoria come 3 pile separate [array] stesso? Ad ogni modo stiamo assegnando array[size * 3] in quella singola matrice.

alcuni link che ne discutono alcuni:

posta Dineshkumar 05.06.2013 - 12:24
fonte

2 risposte

4

Molte domande di intervista non hanno alcuno scopo pratico. Sono una sfida per vedere se riesci a pensare a qualcosa di difficile. Le persone che chiedono loro credono che servano come un buon sostituto delle sfide veramente difficili nella loro codifica che non possono essere spiegate in così poco tempo (e le cui soluzioni non possono essere valutate così in fretta).

In Fisica c'è una storia sulla domanda "come misureresti l'altezza di un edificio con un barometro?" La risposta "giusta" consiste nel misurare la pressione dell'aria in alto e in basso e applicare una formula. Le mie risposte "sbagliate" preferite implicano la caduta dall'alto, misurando il tempo fino a quando tocca il terreno, e applicando una formula, o cercando l'architetto / bidello / proprietario dell'edificio e offrendo un mestiere: ti darò questo barometro costoso se mi dici quanto è alto quell'edificio.

Il punto della domanda non era che le persone hanno bisogno di misurare l'altezza con i barometri regolarmente (o mai), ma per vedere se il candidato conosceva la formula per la pressione e l'altezza. Allo stesso modo la tua domanda metterà alla prova se sai come gestire la memoria, ristruttura un approccio semplice (stack) per gestire uno strano vincolo e pensa a cose intelligenti come non spostare l'elemento dallo stack allo stack ma semplicemente aggiornando i link. Mentre può esserci qualche strano caso limite come "ogni pila può avere fino a un milione di oggetti, ma quando uno cresce gli altri si restringono in modo che lo spazio totale non cambi mai" che accade nel mondo reale, non è questo il motivo per cui ti viene chiesto per risolvere il problema.

    
risposta data 05.06.2013 - 13:45
fonte
1

L'implementazione di più stack in un singolo array (elenco collegato) potrebbe utilizzare la memoria in modo più efficiente.

Se hai tre stack in tre array separati, ognuno di essi avrebbe bisogno di uno spazio pre-allocato per consentire elementi futuri, e ciascuno avrebbe bisogno di una nuova memoria da allocare se si riempie. Combinandoli a un singolo array si ridurrebbe la quantità di memoria "extra" che è pre-allocata per le operazioni future e si dovrà allocare nuova memoria meno volte.

Tuttavia, anche gli stack in un singolo array sarebbero più complicati da gestire. Gli elementi dei tre stack saranno intercalati l'uno con l'altro. Quando gli elementi vengono rimossi da una pila, potrebbe lasciare degli spazi. Devi quindi essere in grado di cercare e riempire queste lacune in seguito quando aggiungi un nuovo elemento.

Con la quantità di memoria normalmente disponibile in questi giorni, combinare gli stack in questo modo sarebbe un'ottimizzazione piuttosto estrema. Raramente penseresti di farlo. Ma potrebbe essere utile occasionalmente.

Aggiornamento: Sarebbe molto utile in alcuni casi specializzati. Se si dispone di una situazione in cui si spostano frequentemente elementi tra le pile, la memorizzazione delle pile in un singolo array sarebbe più efficiente. Spostare l'elemento X dallo stack A allo stack B richiederebbe solo la modifica dei collegamenti.

    
risposta data 05.06.2013 - 12:49
fonte

Leggi altre domande sui tag