• Sklad števil, sklad ovc, sklad volkov, sklad nizov, ...

  • Cel kup razredov: za vsak tip (razred) svoj!
  • Nov razred (tip): potreben nov tip sklada
  • Ali pa “čaramo” s pretvarjanjem tipov

• Želimo

  • Nadzor prevajalnika (da ne bomo med ovce dajali volkov)‏

• Skupne točke

  • Vsi so skladi, vsi morajo imeti operacije, kot jih določa APS Sklad

• Razlike:

  • Izključno v tipu podatkov, ki jih hranimo

• Potrebujemo

  • Tip podatkov naj bo parameter

  • Določimo takrat, ko naredimo sklad

    • Je to Sklad števil, sklad volkov, sklad nizov, ...?

using System.Collections; // za običajen sklad

// demonstracija uporabe sklada
Stack mojS = new Stack();
mojS.Push("To"); mojS.Push("je");
mojS.Push("Matija"); mojS.Push("Lokar");
mojS.Push("4000"); mojS.Push("Kranj");
Console.WriteLine("V skladu je " + mojS.Count + " podatkov.");
// izpis
string pod = (string)mojS.Pop(); // sami moramo pretvoriti podatek nazaj v ustrezni tip
Console.WriteLine("Na vrhu v skladu je bil: " + pod);
Console.WriteLine("V skladu je sedaj " + mojS.Count + " podatkov.");
string podPoglej = (string)mojS.Peek(); // sami moramo pretvoriti podatek nazaj v ustrezni tip
Console.WriteLine("Na vrhu v skladu je : " + podPoglej);
Console.WriteLine("V skladu je še vedno " + mojS.Count + " podatkov.");

// demonstracija uporabe sklada
Stack mojS = new Stack();
mojS.Push("Matija");
mojS.Push("Lokar");
mojS.Push(42);
Console.WriteLine("V skladu je " + mojS.Count + " podatkov.");
// izpis
object pod = mojS.Pop(); // v skladu so podatki tipa object (najbolj splošni tip)
Console.WriteLine("Na vrhu v skladu je bil " + pod);
Console.WriteLine("V skladu je sedaj " + mojS.Count + " podatkov.");
string podPoglej = (string)mojS.Peek(); // sami moramo pretvoriti podatek nazaj v ustrezni tip
Console.WriteLine("Na vrhu v skladu je " + podPoglej);
Console.WriteLine("V skladu je še vedno " + mojS.Count + " podatkov.");

// vendar s pod ne moremo početi nič pametnega!

public static void IzpisSklada(Stack skl)
{
    Stack novSk = new Stack();
    Console.WriteLine("..... VRH .....");
    while (skl.Count > 0) // dokler sklad ni prazen
    {
        object elt = skl.Pop(); // vzamemo in odstranimo
        Console.WriteLine(elt);
        novSk.Push(elt); // vstavimo v pomožni sklad
    }
    Console.WriteLine("..... DNO .....");
    // prelagamo nazaj
    while (novSk.Count > 0) // dokler sklad ni prazen
    {
        object elt = novSk.Pop(); // vzamemo in odstranimo
        skl.Push(elt); // vstavimo nazaj v prvotni
    }
}

• C# omogoča tako imenovane generične tipe

  • Sklad<int> sklad = new Sklad<int>(); // sklad celih števil

• Sklad znakov (torej objektov tipa Character).

  • Sklad<Character> nasSklad;
  • nasSklad = new Sklad<Character>();
  • public static Sklad<Character> obrni(Sklad<Character> s){...}
  • Sklad<Character> nasSklad = new Sklad<Character>();
  • Sklad<Character> vrni ;
  • vrni = obrni(nasSklad);

Stack<Double> mojS = new Stack<Double>();
// v mojS lahko vstavljamo le dec. števila
for (int i = 0; i < 5; i++) mojS.Push(i + 0.1);
// in še niz
mojS.Push("Napaka");

Že prevajalnik tu protestira!

Stack<Double> mojS = new Stack<Double>();
// v mojS lahko vstavljamo le dec. števila
for (int i = 0; i < 5; i++) mojS.Push(i + 0.1);
IzpisSklada(mojS);

Stack<string> mojS1 = new Stack<string>();
// v mojS1 lahko vstavljamo le nize
for (int i = 0; i < 5; i++) mojS1.Push("Niz " + i);
IzpisSklada(mojS1);

public static void IzpisSklada<T>(Stack<T> skl)
{
    Stack<T> novSk = new Stack<T>();
    Console.WriteLine("..... VRH .....");
    while (skl.Count > 0) // dokler sklad ni prazen
    {
        T elt = skl.Pop(); // vzamemo in odstranimo
        Console.WriteLine(elt);
        novSk.Push(elt); // vstavimo v pomožni sklad
    }
    Console.WriteLine("..... DNO .....");
    // prelagamo nazaj
    while (novSk.Count > 0) // dokler sklad ni prazen
    {
        skl.Push(novSk.Pop()); // vstavimo nazaj v prvotni
    }
}

public static void IzpisSklada<T>(Stack<T> skl)

• IzpisSklada<T>

  • pove, da je T oznaka za tip
  • Kaj je T, se ugotovi ob klicu iz parametra

• Sklad<T>

  • pove, da naj se iz dejanskega parametra ugotovi, sklad česa smo dobili
  • Kaj je T, se torej ugotovi tu

• Klica:

  • IzpisSklada(mojS)

    • Ob tem klicu (ob tej izvedbi metode IzpisSklada ) je T oznaka za Double , saj je mojS tipa Sklad<Double>

  • IzpisSklada(mojS1)

    • Ob tem klicu (ob tej izvedbi metode IzpisSklada ) je T oznaka za string , saj je mojS1 tipa Sklad<string>

public static void izpisiTabelo(int[] tabela) {
    for (int i = 0; i < tabela.Length; i++)
        Console.Write(tabela[i] + " ");
    Console.WriteLine();
}
public static void izpisiTabelo(double[] tabela) {
    for (int i = 0; i < tabela.Length; i++)
        Console.Write(tabela[i] + " ");
    Console.WriteLine();
}
public static void izpisiTabelo(char[] tabela) {
    for (int i = 0; i < tabela.Length; i++)
        Console.Write(tabela[i] + " ");
    Console.WriteLine();
}

public static void Main(string[] args) {
    int[] intTab = { 1, 2, 3, 4, 5 };
    double[] doubleTab = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
    char[] charTab = { 'H', 'E', 'L', 'L', 'O' };
    Console.WriteLine("Tabela intTab vsebuje:");
    izpisiTabelo(intTab); // izpis tabele intov
    Console.WriteLine("Tabela doubleTab vsebuje:");
    izpisiTabelo(doubleTab); // // izpis tabele Double
    Console.WriteLine("Tabela charTab vsebuje:");
    izpisiTabelo(charTab); // izpis tabele Character
}

Preobteževanje

Za VSAK tip rabimo svojo metodo, čeprav so vse praktično enake!

public static void izpisiTabelo<T>(T[] tabela)
{
    for (int i = 0; i < tabela.Length; i++)
        Console.Write(tabela[i] + " ");
    Console.WriteLine();
}

public static void Main(string[] args)
{
    int[] intTab = { 1, 2, 3, 4, 5 };
    double[] doubleTab = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7 };
    char[] charTab = { 'H', 'E', 'L', 'L', 'O' };
    Console.WriteLine("Tabela intTab vsebuje:");
    izpisiTabelo(intTab); // izpis tabele intov
    Console.WriteLine("Tabela doubleTab vsebuje:");
    izpisiTabelo(doubleTab); // // izpis tabele Double
    Console.WriteLine("Tabela charTab vsebuje:");
    izpisiTabelo(charTab); // izpis tabele Character
}

S K L A D

• Denimo, da razreda Stack nimamo

• Predstavitev s tabelo

• Elemente hranimo v tabeli

• Potrebujemo še indeks vrhnjega elementa

  • indeks zadnjega vstavljenega elementa
  • indeks prvega prostega mesta
• ni težav z zapisom
• problem: omejena velikost

• class Sklad<T>

  • Sedaj se znotraj razreda obnašamo, kot da je T nek konkreten tip
• private T[] s;
• private int kam; // indeks prostora za nasl. element

• Konstruktorji:

  • Sklad() // sklad privzete velikosti
  • Sklad(int vel) // sklad velikosti vel

if (..sklad je poln..)‏
  ERROR (vržemo izjemo)
  // formalno to ni povsem OK: APS Sklad ni nikoli polna
else {
  s[kam] = podatek;
  kam = kam + 1;
};

public void Vstavi(T pod) {
   // vstavi podatek pod v sklad
     if (kam >= s.length)
      throw new Exception("Sklad je poln");
     else {
       s[kam] = pod;
       kam = kam + 1;
   }
}

• Zakaj ne public void Vstavi(T pod) { ?
• Ker že v class Sklad<T> povedali, da je T oznaka za generični tip!

public void Odstrani() {
      // odstrani podatek iz sklada
      if (!this.Prazen())
        kam = kam - 1;
      else throw
         new Exception("sklad je prazen");
   }

public T Vrh() throws Exception {
    // vrne vrhnji element sklada
      if (!this.Prazen())
        return s[kam - 1];         // kam kaže na prvo PROSTO mesto
      else throw
        new Exception("sklad je prazen");
   }

public bool Prazen() {
  /*
     sklad je prazen, če
     kam kaže na 0 (prvo prosto mesto)‏
  */
  return (kam == 0);
}

Ustrezna konstruktorja

public Sklad()  {
  s = new T[MAX_V]
  kam = 0;
}

public Sklad(int vel)   {
  s = new T[vel];
  kam = 0;
}

public class Sklad<T> {
        private T[] tab;
        private int kam; // kazalec na mesto, kjer bomo vstavili nov element
        private const int MAX_V = 20; // privzeta velikost sklada

        // kostruktorji (pripravi)‏

        public Sklad(){
            tab = new T[MAX_V];
            kam = 0;
        }

        public Sklad(int vel){
            tab = new T[vel];
            kam = 0;
        }

        // metode

        public bool Prazen(){
            // ali je sklad prazen
            return (kam == 0);
        }

public void Vstavi(T pod) {
    // vstavi podatek pod v sklad
    if (kam >= tab.Length) throw new Exception("Sklad je poln");
    else    {
        tab[kam] = pod;
        kam = kam + 1;
    }
}

public void Odstrani() {
    // odstrani podatek iz sklada
    if (!this.Prazen())
        kam = kam - 1;
    else throw new Exception("sklad je prazen");
}

public T vrh() {
    // vrne vrhnji element sklada
    if (!this.Prazen())
        return tab[kam - 1]; // kam kaže na prvo PROSTO mesto
    else throw new Exception("sklad je prazen");
}

public override string ToString(){
    string izp = "VRH";
    for (int i = kam - 1; i >= 0; i--)
        izp += " -:- " + tab[i];
    return izp + " DNO";
}

• Saj ne bomo pisali

  • nekSklad.Vsebina = 12;
• Vstavi/Odstrani sta v bistvu metodi set
• Vrh pa metoda get