(JAVA) Realizzare stack con complessita' O(1)...

[Fuzzo]

Salve a tutti!
Ho scritto una classe Stack (relizzato con un array) ma nel farlo ho tralasciato un particolare: tutte le funzioni devono avere complessita' costante O(1).
Si tratta di:
push(Object);
pop();
top();
isEmpty();
reverse();
Per le prime 4 credo si possa fare con un campo dati che indica la posizione del prossimo oggetto: push diventa un'assegnazione, top un return, pop un return e un'assegnazione. isEmpty e' gia' O(1).

Il problema ce l'ho con reverse, che inverte a specchio tutti gli elementi dello stack
Questo non saprei farlo senza un for che mi fa salire la complessita' ad O(n).

Qualche idea?

Grazie in anticipo!

[PGI-Bis]

A naso direi che basti assegnare al riferimento (indice nel caso di un array) che punta al nodo di inserimento-estrazione il valore del nodo opposto. Il che è più o meno complicato a seconda di come hai realizzato i nodi perchè può richiedere un mutamento nel modo in cui ora realizzi le operazioni pop-peek-push, ferma la complessità O(1).

[71104]

potresti tenerti un flag che indica se l'array è reversed oppure no, ma il problema è che se fai un push all'array reversed non hai spazio... potresti fare un array gestito "a ciclo": se l'array è di N locazioni, un "reversed push" oltre la 0 causa una scrittura alla N-1. ma ovviamente devi conoscere in anticipo la dimensione massima dello stack.

[PGI-Bis]

se non ha spazio può espandere l'array, è pesante ma sempre O(1).

[71104]

Originariamente inviato da PGI-Bis

se non ha spazio può espandere l'array, è pesante ma sempre O(1).

se espande l'array ottiene delle locazioni oltre la fine, ma se non ha spazio per fare il push reversed lo spazio che gli manca non è alla fine, è all'inizio (gli servirebbero locazioni prima dello 0). potrebbe ottenere le locazioni alla fine e fare la gestione ciclica in effetti, ma è inutile perché per realizzare tutti gli algoritmi in O(1) la dimensione massima dello stack deve essere nota a priori, altrimenti (assumendo di gestire l'array ciclico) si presenta il seguente problema: ho N locazioni da 0 a N-1, faccio K push "in avanti", metto il flag di reverse, e faccio N-K push all'indietro; ho riempito tutto l'array. ora che succede se faccio un altro push? altre locazioni la posso ottenere solo alla fine dell'array, ma non è lì che voglio mettere il mio nuovo elemento...

[thebol]

doublelinkedlist, un puntatore all'ultimo elemento inserito, un puntatore al primo elemento inserito(per la reverse), un booleano per la direzione(e per capire se quando fai pop poi devi usare il prev o il succ, uguale per la push)

naturlamente devi gestire la doublelinkedlist, oppure usarne una gia fatta.


ps.cosi a sentimento eh, potrebbe essere una castroneria

[71104]

infatti così funziona, ma io avevo capito che il realizzare lo stack utilizzando un array era un requisito...

[thebol]

Originariamente inviato da 71104

infatti così funziona, ma io avevo capito che il realizzare lo stack utilizzando un array era un requisito...

dal post non sembra un requisito


ps.scusate la niubbaggine, ma sono a digiuno di c & company da molto....ma come si espande un array?

[Fuzzo]

Grazie ragazzi!
Desidero aggiungere qualche informazione al mio precedente post:

• Nessuna (double)linked list, lo stack è gestito con un Array di Object classico
• Se riempio l'array, in automatico viene chiamato il metodo espandi() che duplica la dimensione dell'array e copia gli elementi (questo metodo non deve essere O(1))
• Nessuna gestione dell'Array a ciclo

PGI-Bis
se non ha spazio può espandere l'array, è pesante ma sempre O(1).

Come faccio ad espandere l'array in O(1)? La copia degli elementi dal vecchio al nuovo non mi spara la complessità ad O(n)?

71104
se espande l'array ottiene delle locazioni oltre la fine, ma se non ha spazio per fare il push reversed lo spazio che gli manca non è alla fine, è all'inizio (gli servirebbero locazioni prima dello 0). potrebbe ottenere le locazioni alla fine e fare la gestione ciclica in effetti, ma è inutile perché per realizzare tutti gli algoritmi in O(1) la dimensione massima dello stack deve essere nota a priori, altrimenti (assumendo di gestire l'array ciclico) si presenta il seguente problema: ho N locazioni da 0 a N-1, faccio K push "in avanti", metto il flag di reverse, e faccio N-K push all'indietro; ho riempito tutto l'array. ora che succede se faccio un altro push? altre locazioni la posso ottenere solo alla fine dell'array, ma non è lì che voglio mettere il mio nuovo elemento...

Hai centrato il punto!

Idea: e se ad ogni push e pop al posto di mettere e togliere da un solo array metto e tolgo da 2 array distinti? Uno ovviamente è gestito "al contrario" del seconddo. Così facendo la reverse non fa altro che cambiare i due riferiementi... che ne dite?

[71104]

Come faccio ad espandere l'array in O(1)? La copia degli elementi dal vecchio al nuovo non mi spara la complessità ad O(n)?

se in C usi la realloc è improbabile che il blocco debba essere spostato e quindi ricopiato, ma tu stai usando new quindi si, è O(n) perché lo devi ricopiare.

Idea: e se ad ogni push e pop al posto di mettere e togliere da un solo array metto e tolgo da 2 array distinti? Uno ovviamente è gestito "al contrario" del seconddo. Così facendo la reverse non fa altro che cambiare i due riferiementi... che ne dite?

ottima idea... non ci avevo pensato!

non serve neanche che li "gestisci al contrario" come dici tu, basta che siano due!!

supponi di avere due array, A e B, e di conoscerli tramite i rispettivi puntatori *A e *B:

• push aggiunge un elemento all'array puntato da *A (lo esapnde se necessario)
• pop leva un elemento dall'array puntato da *A
• reverse scambia i valori di *A e *B

fine :|

è geniale!!

[thebol]

si però utilizzi il doppio della memoria

certo che però funziona e ti tieni l'O(1)

[Fuzzo]

Certo, utilizzo il doppio della memoria ma mi rimane O(1), che è il mio scopo finale

Grazie ragazzi

[PGI-Bis]

Per espandere l'array crei un nuovo array più grande e usi System.arraycopy per trasferire il blocco di memoria rappresentato dal vecchio nel nuovo, a partire da un certo offset.

[71104]

Originariamente inviato da thebol

si però utilizzi il doppio della memoria

si ma solo nel caso pessimo: nel caso ottimale ne usi esattamente tanta quanta te ne serve. in certi casi può risultare meglio della lista doppiamente linkata, dove ne usi sempre e comunque di più

[PGI-Bis]

Perchè solo nel caso pessimo? A me sembra che sia sempre il doppio come dice thebol.

[71104]

Originariamente inviato da PGI-Bis

Perchè solo nel caso pessimo? A me sembra che sia sempre il doppio come dice thebol.

no: è il doppio (anzi per l'esattezza il doppio meno 1) solo quando entrambi gli array sono stati entrambi riallocati; ma se sono entrambi pieni li sfrutti al meglio.

[PGI-Bis]

Allora non ho capito la soluzione. Hai due array A e B:

A [ ][ ][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]

push aggiunge un elemento ad A. Con due push (o segnala il cursore):

A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]

Cos'è che fa reverse ora?

[PGI-Bis]

Uppo, 71104: sai che noi matti siamo curiosi

Magari è persino meglio della soluzione ad array unico. Non farti pregare.

[71104]

e sta calmo, stavo a magnà

hai questi:

A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]


ora se fai reverse non cambia nulla, però grazie al fatto che tu scambi i puntatori ciò che tu vedi è questo:

A [o][ ][ ][ ][ ][ ]
B [x][ ][ ][ ][ ][ ]

[marco.r]

Originariamente inviato da PGI-Bis

Allora non ho capito la soluzione. Hai due array A e B:

A [ ][ ][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]

push aggiunge un elemento ad A. Con due push (o segnala il cursore):

A [x][o][ ][ ][ ][ ]
B [ ][ ][ ][ ][ ][ ]

Cos'è che fa reverse ora?

L'idea e' molto chiara se immagini di "appicicare" le basi dei due array per farne uno che abbia gli elementi che invece di partire da un lato partano dal centro.
Riscrivendo il disegno di sopra nel seguente modo:

[ ][ ][ ][ ][ ][ ] B A [ ][ ][ ][ ][ ][ ]

Forse ti sara' piu' chiaro.
Parti con A e aggiungi verso destra

                      -->
[ ][ ][ ][ ][ ][ ] B A [x][ ][ ][ ][ ][ ]
...
[ ][ ][ ][ ][ ][ ] B A [x][x][x][x][x][x]

Quando riempi a semplicemente espandi il doppio array verso destra

[ ][ ][ ][ ][ ][ ] B A [x][x][x][x][x][x][ ][ ][ ][ ][ ][ ]

Quando fai la reverse scambi di ruolo i due array e cominci ad aggiugnere a sinistra

               <--
[ ][ ][ ][ ][x][x] B A [x][x][x][x][x][x][ ][ ][ ][ ][ ][ ]

Per gestire il caso pila vuota basta tenere un contatore.