Podstawowe struktury danych

Dryobates

Stos, kolejka i lista nie są niestety predefiniowanymi strukturami danych w Pascalu, ale to nie znaczy, że nie możemy ich sobie stworzyć. W tym celu musimy wykorzystać wskaźniki.

Stos to jedna z najprostrzych struktur. Wyobraźmy sobie stos leżących książek jedna na drugiej. Możemy kłaść tylko na wierzch stosu i tylko z wierzchu zdejmować (jeżeli wyciągniemy ze środka, to się nam zawali stos). Tak samo jest ze stosem w programowaniu. Żeby dostać się do następnego elementu musimy najpierw ściągnąć coś z góry.
Zadeklarujmy więc sobie jeden element takiego stosu:

type PStos = ^TStos;
  TStos = record
    Liczba: Byte; 
    Nastepny: PStos;
  end;

Możemy oczywiście dodać też inne pola. Dla nas najważniejsze jest pole "Nastepny", które wskazuje na następny element w stosie (leżący "pod" naszym elementem). Pierwsza książka, leży na stole, więc wskazuje na nil (brak książek). Utwórzmy więc pierszy element:

  Pocz := nil;
  WriteLn('Podaj liczbę');
  Read(Liczba);
  if Liczba <> 0 then
    if Pocz = nil then
    begin
      New(Pocz);
      Pocz^.Liczba := Liczba;
      Pocz^.Nastepny := nil;
    end;

Więc teraz czas napisać procedurkę, która będzie wrzucać elementy na stos:

  procedure DodajS(var Pocz: PStos; Liczba: Byte);
  var
    Nowy: PStos;
  begin
    New(Nowy);
    Nowy^.Liczba := Liczba;
    Nowy^.Nastepny := Pocz;
    Pocz := Nowy;
  end;

Nowy element wskazuje na ostatni, który jest na górze, a Pocz wskazuje na początek stosu, czyli nowo utworzony element.

Jeżeli dodajemy kolejne elementy do stosu, to wkładamy elementy na górę
nil <= 1;
1 <= 2;
1, 2 <= 3;
1, 2, 3
A jeżeli zdejmujemy ze stosu, to zdejmujemy z góry:
1, 2 => 3;
1 => 2;
nil => 1;
Jak widać wkładaliśmy w kolejności 1, 2, 3, a zdejmujemy odwrotnie 3, 2, 1. Taką strukturę oznacza się jako FILO (First In Last Out). Element, który pierwszy wrzuciliśmy zdejmujemy jako ostatni.
Jest to często bardzo przydatne. Np. naturalną dla człowieka kolejością podawania współczynników wielomianu jest podawanie ich od największej potęgi. Jednak żeby obliczyć np. sumę wielomianu znacznie wygodniej jest dysponować wielomianami uporządkowanymi od najmniejszej potęgi. W takim wypadku stosujemy stos.

Co jednak zrobić, jeżeli potrzebujemy odczytywać także w normalnej kolejności? Wówczas musimy zastosować kolejkę.
Kolejka to taka struktura, w której dodajemy elementy na koniec, a zabieramy z początku. Tak jak kolejka w sklepie (za PRL-u :) ). Pierwszy klient, który przyszedł, zostanie obsłużony jako pierwszy.
Element kolejki może wyglądać tak samo jak element stosu:

PKolejka = PStos;

Tak samo możemy też utworzyć pierwszy element. Jednak już dodawanie elementów różni się od stosu. Jeżeli mamy początek kolejki, to musimy przejść do końca kolejki i tam dodać element:

  procedure DodajK(var Pocz: PKolejka; Liczba: Byte);
  var
    Nowy, Pom: PKolejka;
  begin
    Pom := Pocz;
    while Pom^.Nastepny <> nil do
      Pom := Pom^.Nastepny;
    New(Nowy);
    Nowy^.Liczba := Liczba;
    Nowy^.Nastepny := nil;
    Pom^.Nastepny := Nowy;
  end;

W ten sposób dodajemy elementy na koniec (w praktyce zwykle stosuje sie jeszcze drugi wskaźnik na koniec kolejki, żeby wyeliminować pętlę).
Tutaj, jeżeli będziemy dodawać elementy w kolejności:
nil <= 1
1 <= 2
1, 2 <= 3
1, 2, 3
to też w takiej będziemy ściągać:
1 <= 2, 3
2 <= 3
3 <= nil

Taką strukturę nazywa się FIFO (First In First Out). Pierwszy element który pojawił się w kolejce, jako pierwszy z niej wyjdzie.

Całkiem fajnie. Ale co zrobić, gdy potrzebujemy wstawić coś do środka kolejki? Wówczas trzeba użyć listy jednokierunkowej. Lista jednokierunkowa to taka kolejka czy stos tylko z dodatkową opcją wrzucania elementów gdzieś w środku (ktoś się wpycha w środek kolejki >:[ ).
PLista = PStos;
Więc by wepchnąć coś w środek, tak by znalazło się na pozycji Poz wykonajmy taką procedurę:

  procedure DodajL(var Pocz: PLista; Liczba: Byte; Poz: Integer);
  var
    Nowy, Pom: PLista;
    i: Integer;
  begin
    if Poz = 1 then
    begin
      New(Nowy);
      Nowy^.Liczba := Liczba;
      Nowy^.Nastepny := Pocz;
      Pocz := Nowy;
    end
    else
    begin
      Pom := Pocz;
      for i := 3 to Poz do
        Pom := Pom^.Nastepny;
      New(Nowy);
      Nowy^.Liczba := Liczba;
      Nowy^.Nastepny := Pom^.Nastepny;
      Pom^.Nastepny := Nowy;
    end;
  end;

I już podstawowe struktury mamy za sobą.

Aha... A jak to jeszcze odczytać? Od początku do końca :)

  procedure Wypisz(Pocz: PStos);
  begin
    while Pocz <> nil do
    begin
      WriteLn(Pocz^.Liczba);
      Pocz := Pocz^.Nastepny;
    end;
  end;

Dobrze by było, gdybyśmy posprzątali po sobie usuwajac te struktury (żeby nam nie zabrakło pamięci):

  procedure Usun(var Pocz: PStos);
  var
    Pom: PStos;
  begin
    while Pocz <> nil do
    begin
      Pom := Pocz^.Nastepny;
      Dispose(Pocz);
      Pocz := Pom;
    end;
  end;

Przykładową implementację można znaleźć tutaj

5 komentarzy

Kapustka, jest LIFO -stos i FIFO - kolejka

gdzie jest deklaracja zmiennej "pocz" i jakiego to jest typu ??

w tekście był mały błąd kosmetyczny (coś takiego : begin</b>), więc go poprawiłem. Jednak sam tekst jest faktycznie świetny, wręcz elegancki. :)

pomysły masz świetne, wykonanie też dobre

Oczywiście to jest szczegół, ale w literaturze spotykałem skrót "LIFO" nie wiem, być może "FILO" też jest prawidłowy (naturalnie znaczenie mają dokładnie to samo).