Razred Stack(E)

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Vsebina

Razred Stack<E>

Razred Stack predstavlja podatkovno strukturo sklad, ki je organizirana po principu LIFO (Last In First Out - Zadnji Noter Prvi Ven). Sklad je urejeni seznam, pri katerem elemente (objekte) dodajamo na vrh in jih z vrha tudi jemljemo. Pri skladu se vse dogaja na vrhu sklada. Sklad si lahko predstavljamo kot:

sklad stolov image:Stoli.jpg

sklad kovancev image:Kovanci.jpg

V Javi je razred Stack predstavljen kot razširitev razreda Vector s 5 operacijami, ki omogočajo, da se Vector (vektor) obnaša kot Stack (sklad). Ogledali si bomo operacije:

  • empty()
  • pop()
  • push(E object)
  • peek()
  • search()

Znak <E> pomeni, da bomo v sklad shranjevali objekte tipa E. Java 5 pozna generične tipe, ki nam omogočajo, da že prevajalnik zazna napačno rabo podatkovne strukture in se pritoži, če želimo v njo shraniti kaj drugega kot smo to določili na začetku ob deklaraciji. Druga prednost je samodejno pretvarjanje tipa (casting) pri branju podatkov iz podatkovne strukture.

  • Sklad celih števil naredimo na naslednji način:
  Stack<Integer> sklad = new Stack<Integer>();
  • Sklad nizov naredimo na naslednji način:
  Stack<String> sklad = new Stack<String>();
  • Sklad avtomobilov naredimo na naslednji način:
  Stack<Avtomobili> sklad = new Stack<Avtomobili>();


Konstruktorji

Stack()

  • Ustvari nov prazen Stack (sklad), ki bo vseboval objekte tipa Object (torej praktično poljubnega tipa).
     Stack i = new Stack();
  • Ustvari nov prazen Stack, ki bo vseboval objekte tipa Integer.
     Stack<Integer> skladStevil = new Stack<Integer>();
  • Ustvari nov prazen Stack, ki bo vseboval objekte tipa Zival.
     Stack<Zival> skladZivali = new Stack<Zival>();


Pomembnejše objektne metode v razredu Stack

Kot smo že prej povedali v sklad elemente (objekte) dodajamo (push) na vrh in jih z vrha tudi jemljemo (pop).

image:Stack.jpg

public boolean empty()

Pove ali je sklad prazen. Metoda vrne:

  • true, če je sklad prazen.
         sklad.push(new Integer(4));
         sklad.pop();
         System.out.println(sklad.empty());
  • false, če je sklad poln.
         sklad.push(new Integer(4));
         sklad.push(new Integer(3));
         System.out.println(sklad.empty());

public E peek()

Vrne objekt na vrhu sklada. Če je sklad prazen vrne izjemo EmptyStackException.

        System.out.println(sklad.peek());

public E pop()

Odstrani vrhnji objekt iz sklada in ga vrne. Če je sklad prazen vrne izjemo EmptyStackException.

        sklad.pop();

public E push(E objekt)

Doda objekt tipa E na vrh sklada. Vstavimo objekt 4 na vrh sklada s.

      s.push(new Integer(4));

Vstavimo objekt beseda na vrh sklada sklad.

     sklad.push(new String("beseda"));

public int search(Object o)

Vrne mesto objekta o.

  • Če je objekt na vrhu, vrne 1.
     sklad.push(new String("breza"));
     System.out.println(sklad.search(new String("breza")));
  • Če objekta ni v skladu, vrne -1.
     sklad.push(new Integer(4));
     sklad.push(new Integer(1));
     sklad.push(new Integer(6));
     sklad.push(new Integer(55));
     System.out.println(sklad.search(new Integer(3)));
  • Če se objekt o nahaja v skladu, vrne razdaljo med vrhnjim objektom in objektom o.
     sklad.push(new Integer(4));
     sklad.push(new Integer(1));
     sklad.push(new Integer(6));
     sklad.push(new Integer(55));
     System.out.println(sklad.search(new Integer(4)));


V tem primeru izpiše 4.


Primera:

1.

V sklad vstavljamo števila 6662.6, 772.6, 12.5, 12.6, 999.9, 62.5, 32.4, 22.6, 192.6, 1.6 . Poišči na katerem mestu je število 12.6.

  1.  
  2. public class Sklad1{
  3. public static void main(String[] args){
  4. Stack<Double> sklad = new Stack<Double>(); //ustvarimo nov sklad realnih števil
  5. // vstavljamo števila v sklad
  6. sklad.push(1.6);
  7. sklad.push(192.6);
  8. sklad.push(22.6);
  9. sklad.push(32.4);
  10. sklad.push(62.5);
  11. sklad.push(999.9);
  12. sklad.push(12.6);
  13. sklad.push(12.5);
  14. sklad.push(772.6);
  15. sklad.push(6662.6);
  16. System.out.print(sklad.search(new Double(12.6))); //v slkadu poišče stevilo 12.6, in vrne na katerem mestu se nahaja
  17. }
  18. }

2.

Janko je napačno sprogramiral robota. Namesto, da bi bili zabojniki zloženi (levo je naveden zgornji zaboj skladovnice) v naslednjem vrstnem redu 2, 1, 4, 3, 5, so zloženi 1, 2, 3, 4, 5. Pomagaj mu popraviti program tako, da bo robot pravilno preložil napačno zložene zabojnike.

  1.  
  2. public class Sklad2{
  3. public static void main(String[] args){
  4. Stack<Integer> sklad = new Stack<Integer>(); //ustvarimo dva nova sklada celih števil
  5. Stack<Integer> resitev = new Stack<Integer>();
  6. //vstavljamo števila v sklad
  7. sklad.push(5);
  8. sklad.push(4);
  9. sklad.push(3);
  10. sklad.push(2);
  11. sklad.push(1);
  12. while(!sklad.empty()){
  13. // prvi par, ki ga je potrebno zamenjati
  14. Integer temp = sklad.peek();
  15. sklad.pop();
  16. if(!sklad.empty()){
  17. // drugi par, ki ga je potrebno zamenjati
  18. Integer temp1 = sklad.peek();
  19. sklad.pop();
  20. // obrnemo par
  21. resitev.push(temp1);
  22. resitev.push(temp);
  23. }
  24. else{
  25. resitev.push(temp);
  26. }
  27. }
  28. // objekte preložimo nazaj v sklad
  29. while(!resitev.empty()){
  30. sklad.push(resitev.peek());
  31. resitev.pop();
  32. }
  33. // objekte izpišemo
  34. while(!sklad.empty()){
  35. System.out.print(sklad.peek() + " ");
  36. sklad.pop();
  37. }
  38. }
  39. }

Glej tudi

Sklad

Osebna orodja