Newsgroup: it.comp.lang.c++
Titolo: Estrarre l'ultimo dallo stack...

Salve.
Come si emula la funzione pop() di uno stack, quando lo stack č
strutturato in memoria come lista dinamica in cui la testa č il primo
elemento inserito (la base) e la coda č l'ultimo?
Mi spiego: faccio un push() di -nell'ordine- "111", "222", "333".
E ottengo il disegno [A]. Poi faccio pop() e mi dovrebbe restituire [B]:
(best viewed with Courier ^_-)
			[A]					    [B]
		 |_______|		  |\ 	 |_______|
coda  -> |__333__|	  ====| \	 |_______|
		 |__222__|	  ====| /	 |__222__| <- coda
testa -> |__111__|		  |/ 	 |__111__| <- testa
Ma come faccio ad eliminare l'ultimo elemento di una lista dinamica,
senza dover percorrere tutta la lista?
Ho il puntatore alla testa e alla coda. Dovrei partire dalla testa e
arrivare alla coda, conservando il puntatore al penultimo, per poi
eliminare l'ultimo e far diventare il penultimo la coda dello stack.
Come viene risolto il problema? uhm... da reminiscenze di assembly,
ricordo che c'era sempre il puntatore alla base dello stack che non
veniva mai modificato e poi c'era il puntatore "mobile" che puntava
sempre all'ultimo elemento inserito. Il problema č che lě la memoria č
vista come array accessibile tramite indirizzo ([ESP-4], per es.),
mentre qui gli indirizzi io non li conosco. Come si risolve?
A proposito... -lo so che sarebbe piů una domanda non molto aderente al
topic di questo ng, ma l'intero post č un po' OT quindi se mi
perdonerete il post, mi perdonerete anche la domanda :)- quand'č che si
usano le liste dinamiche? Voglio dire... in quale caso (concreto, reale)
č meglio usare una lista piuttosto che vettore+riallocazione ?
Grazie infinite,
ErKaiser
ps. non m'interessa il codice C++, ma la soluzione teorica.
	Oppure postate solo il codice e me lo guardo io.
	be'... non č che sia vietato fare entrambe le cose! ;-P
-- 
ErKanh

 testa -> |__111__|   |/ |__111__| <- testa
Come avrai capito da questa risposta... dal tuo disegno non si capisce nulla
;-)
Quindi ignorero' tutto, anche perche' ho capito poco del tuo problema e
comincio da capo come se la tua fosse una domanda generale....
pensa ad una struttura tipo la seguente:
struct A{
    int val;
    A *next;
};
All'inizio lo stack e' vuoto, stack_ptr (il puntatore al tuo stack) punta a
null.
stack_ptr=0;
Ora lo stack appare come:
//
Overo non c'e', null!
quando aggiungi un elemento allo stack, push(6), allochi un'area di memoria,
tale area di memoria .val prendera' il valore 6 e tale area di memoria .next
prendera' il valore di stack_ptr (in questo caso 0). Per finire stack_ptr lo
fai puntare a questa nuova area.
Ecco come appare la cosa:
6 -> //
dove // indica che se provi ad andare all'elemento dopo (next) non esite, e'
null!
Ora facciamo un'altro inserimento: push(4).
allochi un'altra area di memoria, nel campo val metti 4 e nel campo next il
valore di stack_ptr, poi stack_ptr lo fai puntare a questa nuova struttura.
Ecco come appare ora la cosa:
4 -> 6 -> //
Quando vuoi fare pop(), ovvero leggere e cancellare un elemento, la cosa e'
semplice:
leggi cio' che hai nel capo val, primo compito fatto! Poi memorizzi il
valore di stack_ptr in una var temporanea, fai stack_ptr=stack_ptr.next, per
fare in modo che il tuo puntatore punti all'elemento che ha per valore il 6.
A questo punto dell'elemento che contiene il 4 non te ne fai piu' nulla e lo
devi distruggere... per fare questo fai un delete di quello che avevi messo
nella variabile temporanea. Ora hai:
6 -> //
Ora supponiamo ci sia un'altro pop()....
salvi da qualche parte l'indirizzo puntato da stack_ptr (quello che contiene
il val 6), fai stack_ptr=stack_ptr.next ed ora stack_ptr vale nuovamente 0
(null), e lo stack, come all'inizo, e' vuoto. Per finire distruggi l'area di
memoria che conteneva il 6 (avevi salvato il suo indirzo). Ora hai:
//
In pratica, per uno stack "originale" ti serve un solo puntatore. Il
puntatore all'ultimo elemento inserito.
Ammetto di non aver capito molto del tuo messaggio, ma spero questo possa
esserti di aiuto!
Ho fatto come hai chiesto e ti ho dato solo la teoria... ad ogni modo il
codice C++, una volta capita la teoria, e' davvero banale!
Tommy
P.S. vado di fretta quindi mi scuso per qualsiasi imprecisione sono sicuro
ce ne siano ;-)

piuttosto che vettore+riallocazione ?
Uno dei vantaggi degli elementi di una lista e' che non
si "spostano" mai in memoria e quindi il loro indirizzo
rimane valido e puo' essere passato e conservato anche
da altri.
Inoltre operazioni come cancellazioni in mezzo ad una
lista richiedono solo qualche assegnazione di puntatori
e non richiedono lo scorrere tutta la lista se c'e' modo
di accedere al nodo "precedente"; questa possibilita' di
accesso a volte si ottiene mettendo in ogni nodo *due*
puntatori: uno al nodo precedente e uno al successivo.
Il fatto che l'indirizzo di un nodo non cambia mai
anche se altri elementi vengono aggiunti prima o dopo
l'elemento permette di costruire strutture piu'
complesse basate su liste (ad esempio strutture in cui
ogni nodo si trova *contemporaneamente* in piu' liste
differenti).
HTH
Andrea

 possa esserti di aiuto!
grazie mille lo stesso. :)
Il mio forse è un non-problema: lo stack è progettato in modo errato.
Ciao,
ErKaiser

Il mio forse è un non-problema: lo stack è progettato in modo errato
No, se anche il tuo stack fosse quello progettato meglio al mondo, non ti
serve uno stack! Stai lavorando con la struttura dati non adatta.
Tommy

 puntatori: uno al nodo precedente e uno al successivo.
^_^ Ecco: questo è quel che intendevo. Anch'io avevo pensato a un doppio
puntatore, ma la classe è già scritta: dovrò modificarla interamente e
tanto vale rifarla daccapo, con in mente un vero stack. ^_^
Al tab di 4 caratteri non avevo proprio pensato, è vero. Ma dal quote di
Tommy sembrava che Outlook li avesse proprio tolti del tutto.
Comunque d'ironia non ne ho mai fatta (quantomeno: mai voluta fare) e
chiedo venia se Tommy ne abbia vista. ^_^
Ho scritto messaggi lunghi proprio per essere chiaro, e invece... ^_^
Grazie comunque a entrambi!
Saluti,
ErKaiser