Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki, Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 1
Data wykonania ćwiczenia : 15.03.2012
1.Przemysław Wolski

1. Wstęp teoretyczny

Kolejka jest, podobnie jak stos abstrakcyjną strukturą danych opartą na liście liniowej. Elementy kolejki też są połączone w listę, ale inaczej niż w stosie przebiegają operacje dodawania i usuwania elementów z tej listy. Istnieje kilka odmian kolejek. W najprostszej dodawanie i usuwanie elementów jest zorganizowane według zasady FIFO (ang. First In First Out) – pierwszy nadszedł, pierwszy wychodzi. Elementy dodawane są do kolejki na jej końcu, natomiast usuwane są z jej początku. Mówiąc lub pisząc „kolejka” mamy na myśli opisaną wyżej strukturę. Oprócz niej istnieją również kolejki dwustronne, w których elementy możemy dodawać i usuwać po obu stronach kolejki. Wśród tych kolejek możemy wyróżnić kolejki o ograniczonym wejściu, w których operacja dodawania dotyczy tylko jednego końca kolejki, a operacja usuwania obu, oraz kolejki o ograniczonym wyjściu, w których operacja usuwania dotyczy tylko jednego końca kolejki, a operacja dodawania obu końców. Dalsze rozważania będą dotyczyły tylko kolejki FIFO.

Typ pojedynczego elementu kolejki (typ bazowy kolejki) będzie określony tak samo jak typ bazowy stosu.

1. Przebieg Laboratorium.

Zadanie 1.

Napisz funkcje, które rozszerzą działanie standardowych funkcji dostępu do stosu push i pop w ten sposób, że na stosie zawsze pozostawać będzie określona stała minimalna ilość elementów, oraz wielkość stosu nie przekroczy maksymalnej liczby elementów. Przedstaw rozwiązanie w którym użyjesz zmiennej globalnej do przechowywania ilości elementów na stosie oraz rozwiązanie bez użycia zmiennej globalnej. Funkcje powinny zwracać wartość: true jeśli odłoży element na stos i zdejmie element ze stosu;

false jeśli nie odłoży lub nie zdejmie elementu ze stosu.

program zadanie1a; uses crt; type wskaznik=^element; element=record dana:integer; wsk:wskaznik; end; const max=5; min=1; var p:wskaznik; nu,ne,li:integer; procedure push(var a:wskaznik; y:integer); var top:wskaznik; begin new(top); top^.dana:=y; top^.wsk:=a; a:=top; end; procedure pop(var a:wskaznik; var y:integer); var bottom:wskaznik; begin y:=a^.dana; bottom:=a^.wsk; dispose(a); a:=bottom; end; function nowy_push(var a:wskaznik; y:integer):boolean; begin if li<max then begin push(a,y); nowy_push:=true; li:=li+1; end else nowy_push:=false; end; function nowy_pop(var a:wskaznik; var y:integer):boolean; begin if li>min then begin pop(a,y); nowy_pop:=true; dec(li); end else nowy_pop:=false; end; begin clrscr; li:=0; writeln('Dostepna pamiec: ',MemAvail); while nowy_push(p,nu)=true do begin writeln('Wpisz wartosc'); readln(nu); push(p,nu); dec(ne); end; while nowy_pop(p,nu)=true do begin pop(p,nu); writeln(nu); end; readln; end. writeln('Dostepna pamiec: ',MemAvail); readln; end.

Posłużenie się typem rekordowym służącym do zdefiniowania typu pojedynczego elementu stosu. (poszczególne procedury opisane są w stępie teoretycznym) Procedura umieszczająca nowy element na stosie. Procedura usuwająca element znajdujący się na szczycie stosu Zdefiniowanie nowej procedury push. Przyjęcie wartości „true” jeśli li (licznik) jest mniejszy od maksymalnej liczby elementów. Przyjęcie wartości „false” jeśli li (licznik) przekroczy maksymalną liczbę elementów. Zdefiniowanie nowej procedury pop. Przyjęcie wartości „true” jeśli li (licznik) jest większy od minimalnej liczby elementów. Przyjęcie wartości „false” jeśli li (licznik) jest mniejszy od minimalnej liczby elementów Początek programu głównego. Sprawdzenie dostępnej pamięci. Wprowadzanie wartości na stos. Wypisanie elementów odłożonych na stos. Sprawdzenie wycieków pamięci.

program zadanie1; uses crt; type wskaznik=^element; element=record dana:integer; wsk:wskaznik; end; const max=5; min=1; var p:wskaznik; il:integer; procedure push(var x:wskaznik; y:integer); var top:wskaznik; begin new(top); top^.dana:=y; top^.wsk:=x; x:=top; end; procedure pop(var x:wskaznik; var y:integer); var bottom:wskaznik; begin y:=x^.dana; bottom:=x^.wsk; dispose(x); x:=bottom; end; function nowy_push(var a:wskaznik; le:integer):boolean; var x:integer; begin writeln; if (le>=min) or (le<=max) then nowy_push:=true else nowy_push:=false; while (le>=min) and (le<=max) do begin writeln('Podaj ',le,' element'); readln(x); push(a,x); dec(le); end; writeln; writeln('Odlozone liczby: '); writeln; while p<>nil do begin pop(p,x); writeln(x); end; end; begin clrscr; writeln('Dostepna pamiec: ',MemAvail); writeln('Podaj ilosc elementow: '); readln(il); nowy_push(p,il); writeln; writeln('Dostepna pamiec: ',MemAvail); readln; end.

Posłużenie się typem rekordowym służącym do zdefiniowania typu pojedynczego elementu stosu. (poszczególne procedury opisane są w stępie teoretycznym) Procedura umieszczająca nowy element na stosie. Procedura usuwająca element znajdujący się na szczycie stosu Zdefiniowanie nowej procedury push. Przyjęcie wartości „true” jeśli li (licznik) jest mniejszy od maksymalnej liczby elementów. Przyjęcie wartości „false” jeśli li (licznik) przekroczy maksymalną liczbę elementów. Wypisanie odłożonych na stos liczb. Sprawdzenie dostępnej pamięci. Wprowadzanie wartości na stos. Sprawdzenie wycieków pamięci.

Zrzut ekranu przedstawiający wynik działania programu nr 1.

1. Wnioski

Aby wygodnie korzystać z kolejki wprowadza się dwie zmienne wskaźnikowe „head” (po polsku – głowa) i „tali” (po polsku – ogon), które wskazują odpowiednio na pierwszy i na ostatni element kolejki. Mając określony typ elementu i obie zmienne wskaźnikowe należy jeszcze określić operacje, które będą na tej kolejce wykonywane. Podobnie jak w przypadku stosu tych operacji może być kilka, jednak tutaj zostaną omówione trzy najważniejsze – wstawienia elementu do kolejki (ang. enqueue) i usunięcia elementu z kolejki (ang. dequeue) oraz dodatkowo wyświetlenia wartości pola „dane” wszystkich elementów należących do kolejki.