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

[PGI-Bis]

Ok, non ho capito .

push Pippo:

A [Pippo][null][null][null]...
B [null][null][null]...

push Gianni e push Mario

A [Pippo][Gianni][Mario][null]
B [null][null][null]...

peek restituisce "Mario" (ultimo inserito nella pila).

Ora faccio un reverse e scambio i puntatori. Cioè se faccio peek() l'array sottostante non è più A ma B (è così?). E questo peek mi restituisce Pippo?

Non ci arrivo

[PGI-Bis]

Grazie marco.r, ora ho capito. Ammazza che roba complicata.

push, push, push

[ ][ ][ ][ ][ ][ ]BA[x][x][x][ ][ ][ ][ ]

reverse, push, push, push, push, push

[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ]

reverse, pop, pop, pop, pop, pop

[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]

reverse, push

[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]

e mo? Se faccio due pop? O mi sono incasinato io?

[marco.r]

Originariamente inviato da PGI-Bis

[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]

reverse, push

[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]

e mo? Se faccio due pop? O mi sono incasinato io?

Ad ogni momento devi tenere almeno due indici, ovvero il margine sinistro e quello destro degli elementi utilizzati. Lo zero dei due array non e' altro che un punto di riferimento. Nel caso sopra, avremo un left == 4 e un right == 3 (o 5 e 2 a seconda se indichiamo l'ultimo elemento occupato o il primo libero), per cui col push successivo (supponendo di riempire a destra) andremo a colmare il secondo elemento e right diventera' 2 (risp. 1).

[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]
       ^  ^
       |  |
    left   right

[ ][ ][x][x][x][ ]BA[ ][ ][ ][ ][ ][ ][ ]
       ^     ^
       |     |
    left      right

Tu immagina che "BA" non sia altro che l'origine degli assi, e la pila un verme che si muove a destra e sinistra e si accorgia e si allunga
Ora ti faccio un rapido prototipo in python, cosi' capisci meglio :P.

N.B.: E' chiaro che con una implementazione del genere nel caso peggiore l'occupazione di memoria cresce indefinitamente anche con pochi elementi. Visto che non sempre potro' ridurre le dimensioni degli array.

[PGI-Bis]

Mi pare d'aver capito. Penso che in una scala di voti da zero a trenta una cosa del genere valga trenta. Frustate.

[marco.r]

import Numeric

class Pila:
    def __init__(self,initial_size):
        self.head = 0  # Prossima casella libera
        self.tail = -1 # Casella prima della coda
        A = Numeric.zeros(initial_size)
        B = Numeric.zeros(initial_size)
        self.other = { id(A) : B, id(B) : A }
        self.size = 0
        self.head_array = A
        self.tail_array = A
        self.direction = +1     

    def check_push_bounds(self):
        # sforo "in alto"
        if self.direction == +1 and self.head == len(self.head_array):
            other_array = self.other[ id(self.head_array) ]
            new_size = len(self.head_array) * 2
            new_head = Numeric.resize( self.head_array, (new_size,) )
            self.other = { id(new_head) : other_array, id(other_array) : new_head }
            if self.tail_array == self.head_array:
                self.tail_array = new_head
            self.head_array = new_head
        # sforo in basso, devo passare all'altro array
        if self.direction == -1 and self.head == -1:
            self.head_array = self.other[ id(self.head_array) ]
            self.direction = 1
            self.head = 0
            
    def push(self,x):    
        self.check_push_bounds()
        self.head_array[ self.head ] = x
        self.head+= self.direction
        self.size += 1

    def peek(self):
        if self.size == 0:
            raise Exception('Empty Stack')
        return self.head_array[ self.head - self.direction ]

    def check_pop_bounds(self):
        if self.direction == -1 and self.head == 0:
            self.head_array = self.other[ id(self.head_array) ]
            self.direction = 1
            
    def pop(self):
        if self.size == 0:
            raise Exception('Empty Stack')
        self.check_pop_bounds()
        self.head -= self.direction
        self.size -= 1
        
    def reverse(self):
        x = self.head
        self.head = self.tail
        self.tail = x
        
        x = self.head_array
        self.head_array = self.tail_array
        self.tail_array = x
        
        if self.head_array == self.tail_array:
            self.direction *= -1

Codice blandamente testato che necessita di Numeric (giusto per complicarsi la vita, con le liste di python era piu' semplice, ma forse meno fedele alla richiesta iniziale). Tengo un indice head ed uno tail per indicare l'inizio e la fine del verme . head_array e tail_array indicano su quale array cadono testa e coda. direction indica se sto facendo crescere o calare gli indici (ovvero se il verme si allontana o si avvicina all'origine ). other indica ovviamente "l'altro" array rispetto quello specificato.

[PGI-Bis]

Usa un verme solo.

ArrayStack
    array dati
    intero cursore, coda, numeroTotaleElementi
    booleano invertita

    push valore
        cursore = cellaSuccessiva(cursore)
        dati[cursore] = valore
        aumenta di 1 numeroTotaleElementi
        espandi array se necessario

    valore pop
        valore = dati[cursore]
        cursore = cellaPrecedente(cursore)
        riduci di 1 numeroTotaleElementi

    reverse
        invertita = il contrario di invertita
        scambia cursore con coda

    booleano isEmpty
        numeroTotaleElementi è zero?

    espandi array se necessario
        è necessario se numeroTotaleElementi vale quanto la dimensione di dati
        crea un nuovo array più grande
        se cursore - coda + 1 vale numeroTotaleElementi
            copia dati nel nuovo array più grande
        altrimenti
            copia la parte terminale di array nel nuovo array
            copia la parte iniziale di array nel nuovo array
        scambia array con l'array più grande

    intero cellaPrecedente indice
        se è invertita, restituisce indice + 1, altrimenti indice - 1
        applica all'indice restituito la condizione di circolarità di un anello

    intero cellaSuccessiva indice
        se è invertita, restituisce indice - 1, altrimenti indice + 1
        applica all'indice restituito la condizione di circolarità di un anello

Cursore sta per il punto di ultimo inserimento che nello schema qui sotto è la testa.

push push push

 coda     testa
A[x][x][x][x][ ][ ][ ][ ][ ]

reverse

testa     coda
A[x][x][x][x][ ][ ][ ][ ][ ]

push push push

          coda    testa
A[x][x][x][x][ ][ ][x][x][x]

pop, pop

          coda          testa
A[x][x][x][x][ ][ ][ ][ ][x]

reverse

         testa          coda
A[x][x][x][x][ ][ ][ ][ ][x]

quattro push

                     testa                   coda
A[x][x][x][x][x][x][x][x][ ][ ][ ][ ][ ][ ][ ][x]

Dieci a uno che il prof gli ha fatto fare gli anelli (aka array circolari) prima di rifilargli questo.

[marco.r]

Originariamente inviato da PGI-Bis

Usa un verme solo.
<cut>
Dieci a uno che il prof gli ha fatto fare gli anelli (aka array circolari) prima di rifilargli questo.

Ci avevo pensato, ma vedo un problema: che succede se riempio l'array a meta' strada ?
Supponendo di partire con array di otto elementi,
dopo la seguente sequenza
push push push push reverse push push push push
ti trovi con l'array pieno e con gli estremi che ti toccano a meta' array.
Come espandi l'array per il prossimo elemento ? Idealmente vorresti farlo "in mezzo" all'array, per aver spazio per i prossimi push.
Non mi vienei n mente una soluzione semplice.

[PGI-Bis]

Esattamente come hai detto, "lo apri in due come una mela". E' un anello lo espandi come tale.

La posizione del cursore ti dice dove stà "la metà" e dal suo rapporto con
la coda e il numero totale degli elementi ricavi se il cursore abbia o non abbia fatto "un giro" e in che senso l'abbia fatto.

            
          T  H
[X][X][X][X][X][X][X][X]

se H è maggiore di T e "l'array ha fatto un giro", da zero a T va in testa al nuovo array e da H a length - 1 va in coda.
se H è minore ti T da zero ad H va in testa e da T a length - 1 va in coda al nuovo.
se H è maggiore di T e "l'array non ha fatto un giro" allora copy da T ad H inclusi nel nuovo array, a partire da zero o da T se vuoi lasciare inalterati gli indici della testa e della coda.

[PGI-Bis]

Anzi, è più semplice:

gli elementi da zero al minore tra T ed H vengono copiati nelle posizioni da zero al minore tra T ed H nel nuovo array.
gli elementi dal maggiore tra T ed H e la lunghezza dell'array vegono copiati da
(lunghezza - Max(T, H)) a nuovoArray.length.

Più o meno uno che è tardi e non ci ho voglia di contare tanto

[Aggiunto] No, meglio quella di prima
[Aggiunta all'aggiunto] Anzi, è meglio questo di adesso. Ok, vado a dormire

[marco.r]

Hai ragione. Partivo dal presupposto che se devo ricopiare gli ultimi n elementi non ho piu' l'O(1), pero' in effetti quando espando un array nel caso generale devo comunque copiare i suoi elementi per cui in ogni caso ho l'O(n) ( o l'O(1) ammortizzato se preferisci )

[71104]

Originariamente inviato da PGI-Bis

Grazie marco.r, ora ho capito. Ammazza che roba complicata.

push, push, push

[ ][ ][ ][ ][ ][ ]BA[x][x][x][ ][ ][ ][ ]

reverse, push, push, push, push, push

[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ]

reverse, pop, pop, pop, pop, pop

[ ][ ][x][x][ ][ ]BA[ ][ ][ ][ ][ ][ ][ ]

reverse, push

[ ][ ][x][x][ ][ ]BA[x][ ][ ][ ][ ][ ][ ]

e mo? Se faccio due pop? O mi sono incasinato io?

azz, è vero... non ci avevo pensato...

allora tocca modificare così: oltre ai puntatori *A e *B aggiungiamo i due indici Left e Right: quando hanno un valore positivo indicano in *A, quando è negativo in *B. e sono 1-based e non possono mai essere 0. a questo punto:

• push, se Right è negativo scrive in B[-Right-1], se è positivo scrive in A[Right-1]; incrementa Right; se necessario espande l'array.
• pop, se Right è negativo legge da B[-Right-1], se è positivo da A[Right-1]; decrementa Right e se diventa nullo lo fa diventare -1
• reverse, scambia *A e *B, scambia Left e Right

[71104]

a proposito:

Originariamente inviato da PGI-Bis

reverse, push, push, push, push, push

[ ][ ][x][x][x][x]BA[x][x][x][ ][ ][ ][ ]

c'è un push di troppo

[cionci]

E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed...

[PGI-Bis]

Originariamente inviato da cionci

E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed...

Appunto.

Per l'espansione me n'è venuta un'altra, ancora più facile.

copia da array tutti gli elementi a partire da coda fino a cursore in array più grande a partire da zero. Poi imposta coda a zero, cursore a numero di elementi meno uno e invertita a false.

[71104]

Originariamente inviato da cionci

E se lo facciamo circolare lo stack non è più semplice ?
Basta fare push in coda nel caso sia reversed...

se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.

[PGI-Bis]

Originariamente inviato da 71104

se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.

E questo sarebbe di un qualche impedimento?

[cionci]

Originariamente inviato da 71104

se ne è già parlato prima ma no, perché non si conosce la dimensione massima dello stack.

Se devi implementarlo con un vettore bene o male la conosci la dimensione massima, per l'espansione automatica a stack pieno (che si è detto non deve essere O(1)) si usa l'algoritmo che ha detto sopra PGI-bis...

[71104]

Originariamente inviato da cionci

per l'espansione automatica a stack pieno (che si è detto non deve essere O(1))

ah è vero

[cionci]

Originariamente inviato da PGI-Bis

copia da array tutti gli elementi a partire da coda fino a cursore in array più grande a partire da zero. Poi imposta coda a zero, cursore a numero di elementi meno uno e invertita a false.

O semplicemente si estraggono gli elementi con la pop fino a svuotarlo e dopo si inseriscono all'inizio del nuovo vettore (o dall'elemento uno fino all'N-1, in tal caso si fa uno stack reversed, o dall'elemento N-1 fino allo zero, e si impostano di conseguenza i due puntatori alla testa e alla coda)...