Lineární datové struktury II.

Fronta
Tato datová struktur má jako prototyp službu či zařízení, které se stará o komunikaci pratiskárny s prapočítačem. Prapočítač dokáže vmžiku vygenerovat požadavek na vytisknutí tisíce znaků, ale pratiskárna jich dokáže vytisknout jen 50 za sekundu. Prapočítač stojí tisíc dolarů za hodinu provozu, takže se nemůže zdržovat čekáním na pratiskárnu. Proto je tu něco, co vmžiku spolyká výstupní data a pak je ve vhodném tempu předává dál.

Jde tedy o datovou strukturu, která má řešit problém, kdy jedna část programu chrlí data rychleji, než je jiná dokáže zpracovávat, často je pak potřeba při komunikaci se světem, třeba v případě, že uživatel mačká klávesy rychleji, než je stačí program zpracovávat.

Máme k dipozici tři operace: Vložení, Výběr a Test na prázdnou frontu.

[]
Ulož(A)
[A]
Ulož(B)
[AB]
Ulož(C)
[ABC]
Vyber --> A
[BC]
Ulož(D)
[BCD]
Vyber --> B
[CD]
Ulož(E)
[CDE]

atd.

Interně si fronta musí pamatovat, kde má hledat první a kam má přidat poslední prvek. Při realizaci v poli je z důvodů efektivity, tedy aby operace byly O(1), potřeba realizovat frontu tzv. kruhovým uložením. Při dosažení konce pole se další položka přidává na začátek, pokud odtud již někdo zapsaná data vyzvedl. Abychom snadno rozlišili plnou a prázdnou frontu, je v tomto případě lepší jako jednu ze stavových proměnných fronty používat počet položek ve frontě. Pokud bychom použili index začátku a index konce, nebudeme moci přímočaře využít celé pole pro frontu. Pokud má ploe délku 2^n stačí místo operace MOD jen laciný AND.

Pozn. V učebnicích programování často najdete úlohy, na procházení všech stavů nějakého diskrétního systému. Třeba mnoho variací známé úlohy na přelévání vody je snadno řešitlených, pokud si zavedeme podatelnu, kde uložíme všechny stavy, které můžeme z aktuálního dostat jedním přelitím a odkud si vždy vyzvedneme jeden stav k dalšímu přelévání. Podatelna je příkladem realizace fronty. Viz sbírky úloh z programování o tzv. prohledávání do šířky, kde se také dozvíte různé možnosti, jak si zapamatovat, že už jsme v daném stavu byli, což nám zaručí, že program skončí [Příklady z programování].

Jiným příkladem je nalezení nějakého souboru. Pokud by šlo jen o jméno, je to natolik obvyklá oprace, že ji dokážeme realizovat prostředky příkazové řádky:

dir /S/B | grep -i jmeno

(tedy požádáme příkazem dir o vypsání všech souborů v daném adresáři a jeho podadresářích a poté jeho výstup převezme program grep a ten se podívá jestli na nějakém řádku není řetězec "jmeno". Alespoň základní popis důležitého programu grep snad stihneme na poslední přednášce.

Takovýto postup ale nepůjde rozšířit na případ, kdy soubor, který hledáme nezle nalézt jen podle jména. Proto může nastat situace, kdy se budeme muset uchýlit k psaní programu. Ten by pak mohl vypadat takto (hledá se soubor délky 8274, na což je asi taky zbytečné psát program, ale ...) :

program Soubornik;
{Chcete-li program pouzit, vyhlednete si soubor dostatecne skryty 
 hluboko v nejakem podadresari a nastavte konstantu velikost}
uses Sysutils;

const dirsep = '\';
      Velikost =  8274; 


const VelikostPoleProFrontu = 1024;
var DelkaFronty : integer = 0;
    PoleProFrontu : array[0..VelikostPoleProFrontu-1] of string;
    KdeZacinaFronta :  integer = 0;

procedure VlozDoFronty(const A:string);
var KamPsat : integer;
begin
   assert(DelkaFronty<VelikostPoleProFrontu);

......
......
......
end;

function VyzvedniZFronty : string;
begin
   assert(DelkaFronty>0);

......
......
......
end;

procedure SkonciJestliJeToOn(const Adresar: string;const F:TSearchRec);
begin
   if F.Size = Velikost then begin
     Writeln('Nasel jsem ho v adresari ',Adresar,' pod jmenem ',F.Name);
     Readln;
     Halt;
   end;
end;

var F : TSearchRec;
    Adresar : string;


begin
  VlozDoFronty('C:\windows');

  while DelkaFronty > 0 do begin
      Adresar := VyzvedniZFronty;
      if FindFirst(Adresar+DirSep+'*',faAnyFile,F)=0 then
        repeat
          if F.Name[1]<>'.' then begin // . a .. nechci
             if (F.Attr and faDirectory)<>0 then VlozDoFronty(Adresar+dirsep+F.Name)
                                            else SkonciJestliJeToOn(Adresar,F);
          end;
        until FindNext(F) <> 0;
      FindClose(F);
  end;

  Writeln('Nenasel jsem ho');
  readln;
end.
 

Rozmyslíme-li si funkci programu vidíme, že adresářový strom porhledáváme do šířky.

Cvičení: Dopište vytečkované vnitřnosti procedur pro frontu řetězců.