Stack
Iz E-študij, proste zakladnice študentskega znanja
- Članek govori o skladu (razred Stack) v Javi.
Primer sklada. Rdeč je edini dostopni element.
Podatkovna struktura, ki deluje po principu LIFO (Last in first out)
Primer: zlaganje kovancev
Razred Stack (razširitev razreda Vector)
Vsebina |
Operacije za delo s skladom
- empty()
- pove, ali je sklad prazen
- peek()
- pove, kateri element je na vrhu sklada
- element vzame z vrha sklada in ga vrne nazaj (isto kot da bi naredili pop() in takoj push())
- pop()
- vzame element z vrha sklada
- push (Object)
- doda element na vrh sklada
- search (Object)
- vrne indeks kje se nahaja objekt
Deklaracija razreda Stack
public class Stack extends Vector { public boolean empty() { return size()==0; } public Object peek() { if ( size()==0) throw new EmptyStackException(); return elementAt(size()-1); } public Object pop() { Object o = peek(); //ce ne uspe bo exception removeElementAt(size()-1); return o; } public Object push(Object o) { addElement(o); return o; } public int search(Object o) { int i = lastIndexOf(o); if (i<0) return -1; return size()-i; } public Stack() //konstruktor klice iz nadrejenega razreda { } }
Primeri
Računanje aritmetičnih izrazov v postfiksni obliki (brez oklepajev)
- najprej zapišemo operanda, nato operator: 3 4 + pomeni 3 + 4
Postopek
- beremo od leve proti desni
- če naletimo na operand, ga postavimo na sklad
- če naletimo na operator, vzamemo dva operanda s sklada, izvedemo operacijo in rezultat zapišemo na sklad
Prikaz izračuna
3*(4+5)/10-1
3 4 5 + * 10 / 1 -
Sklad:
ko beremo števila jih samo dodajamo na sklad
| 5 | | 4 | | 3 | #####
Ko preberemo operator vzamemo s sklada 2 elementa in izračunamo rezultat
4 + 5 = 9
rezultat damo nazaj na sklad
| 9 | | 3 | #####
spet dobimo operator, zato vzamemo 2 elementa s sklada in izračunamo rezultat
3 * 9 = 27
in rezultat damo na sklad
| 27 | ######
beremo naprej, število 10 dodamo na sklad
| 10 | | 27 | ######
preberemo operator deljeno, zato delimo
27 / 10 = 2.7
rezultat vrnemo na sklad
| 2.7 | #######
beremo naprej, število 1 dodamo na sklad
| 1 | | 2.7 | #######
preberemo minus, zato odštejemo elementa
2.7 - 1 = 1.7
na skladu dobimo končni rezultat
| 1.7 | #######
Realizacija metode v Javi
import java.util.Stack; public class Kalkulator { public static void main (String[] args) { boolean konec = false; String input; double x, y, z; Stack sklad = new Stack(); while (! konec) { System.out.print("Vnesi operand ali operator: "); input = BranjePodatkov.preberiString(); switch (input.charAt(0)) { case 'K' : System.out.println("Rezultat je: " + sklad.peek()); konec = true; break; case '+' : // y = Double.parseDouble((String)sklad.peek()); // sklad.pop(); y = Double.parseDouble((String)sklad.pop()); x = Double.parseDouble((String)sklad.pop()); z=x+y; sklad.push(new Double(z).toString()); break; case '-' : y = Double.parseDouble((String)sklad.pop()); x = Double.parseDouble((String)sklad.pop()); z=x-y; sklad.push(new Double(z).toString()); break; case '*' : y = Double.parseDouble((String)sklad.pop()); x = Double.parseDouble((String)sklad.pop()); z=x*y; sklad.push(new Double(z).toString()); break; case '/' : y = Double.parseDouble((String)sklad.pop()); x = Double.parseDouble((String)sklad.pop()); z=x/y; sklad.push(new Double(z).toString()); break; default: sklad.push(input); } } } }
Odprava rekurzije s pomočjo sklada (hanojski stolpiči)
Opis problema
n obročev različnih velikosti in 3 palice (A, B, C)
- Začetek
- vsi obroči so na palici A
- zloženi so od največjega do najmanjšega
- Cilj
- prestaviti obroče na palico C s pomočjo pomožne palice B
- Omejitvi
- naenkrat lahko prestavimo en obroč
- nikoli ne smemo prestaviti večji obroč na manjšega
- Narava problema je rekurzivna
- prestavi (n-1) obročev s palice A na palico B
- prestavi en obroč s palice A na palico C
- prestavi (n-1) obročev s palice B na palico C
Rekurzivna rešitev
public class HanoiRek { public static void main (String[] args) { hanoi(3, 'A', 'B', 'C'); } private static void hanoi (int n, char a, char b, char c) { if (n==1) System.out.println("Prestavi obroc s palice "+a+" na palico "+c); else { hanoi(n-1, a, c, b); hanoi(1, a, b, c); hanoi(n-1, b, a, c); } } }
Iterativna rešitev s skladom
- Postopek
- na sklad postavimo začetni zahtevek
- s sklada jemljemo zahtevke in jih obdelujemo
(pri tem se na sklad dodajajo novi zahtevki)
- postopek ponavljamo, dokler sklad ni prazen
- Grob opis postopka
postavi začetni zahtevek na sklad;
dokler sklad ni prazen
{ odvzemi zahtevek s sklada;
obdelaj zahtevek; }
- Predstavitev zahtevka: razred Zahtevek
Štiri atributi:
- n
- število obročev, ki jih je treba prestaviti
- a
- izvor
- b
- pomožna palica
- c
- ponor
- Iterativna rešitev v Javi: razred HanoiIte
import java.util.Stack; public class HanoiIte { public static void main (String[] args) { hanoi(3, 'A', 'B', 'C'); } private static void hanoi (int n, char a, char b, char c) { Stack s = new Stack(); s.push(new Zahtevek(n, a, b, c)); while (!s.empty()) { Zahtevek z = (Zahtevek)s.pop(); n = z.n; a = z.a; b = z.b; c = z.c; if(n==1) System.out.println("Prestavi obroc s palice "+a+" na palico "+c); else { s.push(new Zahtevek(n-1, b, a, c)); s.push(new Zahtevek(1, a, b, c)); s.push(new Zahtevek(n-1, a, c, b)); } } } }
- Zahtevek.java
import java.util.Stack; class Zahtevek { public int m; public char a,b,c; public Zahtevek(int m,char a, char b, char c) { this.m=m; this.a=a; this.b=b; this.c=c; } }
