Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki,
Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 1
Kolejki
Data wykonania Data oddania Ocena :
ćwiczenia : sprawozdania :
15.03.2012 21.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.
type
wskaznik=^element;
element=record
dana:integer;
next:wskaznik;
end;
Typ pojedynczego elementu kolejki (typ bazowy kolejki) będzie określony tak samo jak typ bazowy stosu.
2. 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 zadanie1;
uses crt;
type Posłużenie się typem rekordowym służącym do zdefiniowania typu
wskaznik=^element; pojedynczego elementu stosu.
element=record
dana:integer;
wsk:wskaznik;
end;
const
max=5;
min=1;
var
p:wskaznik;
nu,ne,li:integer; (poszczególne procedury opisane są w stępie teoretycznym)
procedure push(var a:wskaznik; y:integer); Procedura umieszczająca nowy element na stosie.
var
top:wskaznik;
begin
new(top);
top^.dana:=y;
top^.wsk:=a;
a:=top;
end;
procedure pop(var a:wskaznik; var y:integer); Procedura usuwająca element znajdujący się na szczycie stosu
var
bottom:wskaznik;
begin
y:=a^.dana;
bottom:=a^.wsk;
dispose(a);
a:=bottom;
end;
function nowy_push(var a:wskaznik; y:integer):boolean; Zdefiniowanie nowej procedury push.
begin
if lipush(a,y);
nowy_push:=true; Przyjęcie wartości  true jeśli li (licznik) jest mniejszy od
li:=li+1; maksymalnej liczby elementów.
end
else
nowy_push:=false; Przyjęcie wartości  false jeśli li (licznik) przekroczy maksymalną
end; liczbę elementów.
function nowy_pop(var a:wskaznik; var y:integer):boolean; Zdefiniowanie nowej procedury pop.
begin
if li>min then begin
pop(a,y);
nowy_pop:=true; Przyjęcie wartości  true jeśli li (licznik) jest większy od
dec(li); minimalnej liczby elementów.
end
else nowy_pop:=false; Przyjęcie wartości  false jeśli li (licznik) jest mniejszy od
end; minimalnej liczby elementów
Początek programu głównego.
begin
clrscr;
li:=0; Sprawdzenie dostępnej pamięci.
writeln('Dostepna pamiec: ',MemAvail);
while nowy_push(p,nu)=true do begin Wprowadzanie wartości na stos.
writeln('Wpisz wartosc');
readln(nu);
push(p,nu);
dec(ne);
end;
while nowy_pop(p,nu)=true do begin Wypisanie elementów odłożonych na stos.
pop(p,nu);
writeln(nu);
end;
readln;
end.
writeln('Dostepna pamiec: ',MemAvail); Sprawdzenie wycieków pamięci.
readln;
end.
Zrzut ekranu przedstawiający wynik działania programu nr 1.
3. Wnioski
Aby wygodnie korzystać z kolejki wprowadza się dwie zmienne wskaz
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
wskaz
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.