12. Verem adattípus

A verem az informatika számos területén használandó adattípus, amelynek a lényege az, hogy ha egy verembe sorban egymás után bedobunk adatokat, akkor az adatok egymás fölé kerülnek. Ha ki akarunk venni belőle adatot, akkor mindig a verem tetején lévőt vehetjük ki.

A verembe tett adatok mennyisége mindig korlátos. Ha tele van a verem, akkor nem tudunk további adatot betenni. Ha üres a verem, akkor nem tudunk kivenni adatot!

Hol használnak ilyen szerkezeteket?

Az operációs rendszer, a processzor a multitaszk során verembe helyezi az előzőleg félretett alkalmazás legfontosabb adatait. Ha egy programon belül meghívunk egy függvényt, akkor a program pillanatnyi állspotát verembe teszi a processzor és veremben hozza létre a függvényben használandó lokális adatokat is.

Ezt az adatszerkezetet nevezik Last In First Out = LIFO adatszerkezetnek is.

A megvalósítása tipikusan egyszerűen egy tömb lehet. Egy mutato, nevű változó értéke mutatja, hogy hol van az első üres hely a tömbben. Ha új adatot akarunk betenni, akkor a mutato által mutatott tömbelembe tesszük az adatot, majd növeljük mutato-t eggyel. Ha a mutato értéke eléri a ömb elemszámát betelik a tömb.

Ha ki akarunk venni egy elemet, akkor a mutato értékét csökkentjük eggyel és az általa mutatott helyen lévő adatot adjuk vissza a hívónak. Ha a kivétel előtt a mutato==0, akkor üres a tömb.

A FIFO adatszerkezethez hasonlóan oldjuk meg a problémát. Készítünk egy keretprogramot, amely véletlenszerűen tölt adatokat a verembe és vesz ki onnan.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace lifo
{
  class Program
  {
    public static void Main(string[] args)
    {
      Lifo q = new Lifo();
      Random r = new Random();
      Random v1 = new Random();
      Random v2 = new Random();
      int bev = 60; //A bemenő adat valószínűsége 0..100 között.
      int kiv = 40; //A sorból kivenni való adat valószínűsége 0..100 között.     

      int adat;
      int ki;
      Console.Clear();
      for (int i = 0 ; i<100; i++)
      {
        adat = r.Next(0, 100);
        Console.Write("Be: ");
 
        if(v1.Next(0,100) < 60 )
        {
          Console.Write(adat);
          q.verembe(adat);
        }
        else
        {
          Console.Write("- ");
        }
        Console.Write(" ===> ");

        if( v2.Next(0,100) < 40 )
        {
          ki = q.verembol();
          Console.Write("Ki: {0}", ki);
        }else{
          Console.Write("Ki: - ");
        }
        q.allapot();
      }			
      Console.Write("Press any key to continue . . . ");
      Console.ReadKey(true);
    }
  }
	
  class Lifo
  {
    //privát állapotleíró változók
    private const int hossz = 10;       //A tároló tömb hossza
    private int[] verem = new int[hossz]; //A sorban lévő adatokat tároló tömb
    private int mutato;                 //Hol van az első szabad hely a tömbben
    private int db = 0;                //Hányadik adatátvitel zajlik
		
    //Az osztály konstruktora inicializálja a
    public Lifo(){
      mutato = 0;
    }

    //Ez a metódus teszi be a sor végére az új adatot
    public void verembe(int adat)
    {
      //Ha van hely még a sorban, akkor beteszi az adatot a végére
      if(mutato < hossz-1)     
      {
        verem[mutato] = adat; 
        mutato++;
      }
      else
      {
        Console.Write(" !Betelt! ");
      }
    }
		
    //Ez a metódus adja vissza a sor első tagját
    public int verembol()
    {
      int vissza;
      //Ha nem üres a sor akkor ki tudunk venni adatot
      if (mutato > 0 )
      {
        vissza = verem[mutato-1];
	mutato--;          
      }
      else
      { 
        vissza = -1;        //A -1 jelentése: nincs érvényes visszatérő adat
        Console.Write(" !Üres! ");
      }
      return vissza;
    }

    // Ez a metódus a sor állapotát írja ki
    public void allapot()
    {
      Console.Write(" Verem: ");
      for(int i=0 ; i< hossz ; i++)
      {
        Console.Write("{0,2}, ", verem[i]);
      }
      Console.WriteLine();
      db++;
    }
  }	
}