stack cloning - kako izvesti?

[ trodon @ 03.09.2006. 18:45 ] @

Zadatak sa ispita kaze:
Napisati metodu clone(Stack s1, Stack s2) tako da posle izvrshenja s2 bude identichan kao i s1. (nije bash ovakav text ali nadam se da je poenta jasna). Pri tome se ne smeju koristiti dodatni stekovi, nizovi,itd. vec samo prosti podaci, kao npr. "int". Smeju se koristiti samo metode push, pop, isEmpty i peek. Takodje se ne smemo oslanjati ni na implementaciju steka (nebitno da li je realizovan preko linked list-a, array-a, queue-a).Najveci problem ovde je taj shto je lagano klonirati s1, s tim da je s2 obrnut klon, tj. zadnji elemenat s1 postaje prvi elemenat s2. Kako ih uchiniti identichnima pod gore navedenim uslovima???

[ Relaja @ 03.09.2006. 21:16 ] @

pa to ces raditi rekurzivno.

Code:

rek(stack s1, stack& s2){
  if(s1.size())==0)return;
  int vrednost = s1.skini;
  rek(s1,s2);
  s2.push(vrednost);
}

Edit:
s2 moze biti globalna promenljiva
ukoliko s1 ne mora ostati nepromenjen, onda i on moze biti globalna promenljiva..
ovako se samo cuva s1, tj.pocetni stack.

_{[Ovu poruku je menjao Relaja dana 03.09.2006. u 22:27 GMT+1]}

[ trodon @ 04.09.2006. 11:39 ] @

OK, ovo mi je jasno, ja sam ga uradio na slichan nachin, samo iterativno. E sad, hteo bih da te pitam zar to tvoje nece funkcionisati ovako: stack je LIFO, pa ce njegov poslednji elemenat koji je prvi skinut, postati prvi elemenat stacka s2. Na taj nachin se dobija clone, ali obrnut, a meni treba identichan. Mozda je tvoje reshenje tachno, ali te samo molim da mi pojasnish tu rekurziju u tvom reshenju poshto nju malo slabije kapiram.
THX

[ mmwlada @ 04.09.2006. 12:41 ] @

Odgovor koji ti je dao Relaja je tačan. Pazi ovako: Kada uzmeš prvi put iz prvog steka sa

Code:
int x = s1.skini();

Ti si lokalnoj promenljivoj dao vrednost poslednjeg člana steka, a onda to ponovo uradiš za ostatak steka. Na taj način, ako imaš stek sa ovim vrednostima [1,5,3,8] i ako si izbacio 8, ostalo ti je [1,5,3]. Onda kada uradiš rekurzivno za taj stek, ti izbacuješ 3. Zatim 5 i na kraju 1. Onda kada pošalješ prazan stek, funkcija ništa ne uradi, nego se samo vrati nazad u prethodno pozvanu funkciju. Onda se u nov stek upisuje 1, pa 5, pa 3 pa 8. Tako u drugom steku imaš [1,5,3,8], koji je identičan prvom.

[ trodon @ 04.09.2006. 19:15 ] @

Hvala ljudi, skapirao sam!!!

[ emiraga @ 08.09.2006. 02:27 ] @

ako bi napravili neki privremeni stack, onda bi mogli to odraditi i iterativno

Code:
  stack temp;
  while(! s1.empty())
       temp.push(s1.skini());

  while(! temp.empty())
       s2.push(temp.skini());

   return s2;

[ mmwlada @ 08.09.2006. 13:12 ] @

Da, ali u zadatku kaže da ne sme da koristi druge stackove, nizove i slično.

[ DarkMan @ 10.09.2006. 10:27 ] @

Citat:

Relaja: pa to ces raditi rekurzivno.

Code:

rek(stack s1, stack& s2){
  if(s1.size())==0)return;
  int vrednost = s1.skini;
  rek(s1,s2);
  s2.push(vrednost);
}

U sustini i ovde se koristi novi stek.
Kreiran je implicitno kada nije prosledjen po referenci (zato je moguce skidanje sa steka a da se originalni stek ne promeni, jer se u sustini skida sa kopije steka).