Podstawowe pojęcia dotyczące kolejek


Tematy pokrewne   Podrozdziały
Podstawowe operacje na tablicach
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach cyklicznych jednokierunkowych

Kolejki
Podstawowe pojęcia dotyczące kolejek
Kolejki priorytetowe

  Kolejka jako tablica
Kolejka jako lista
Kolejka cykliczna

Kolejka (ang. queue) jest sekwencyjną strukturą danych o takiej własności, iż element zapisany jako pierwszy jest również odczytywany jako pierwszy. Taka struktura w literaturze informatycznej nosi nazwę FIFO (ang. First In First Out – pierwszy wchodzi, pierwszy wychodzi). Kolejkę możemy sobie wyobrazić jako tubę – elementy wstawiamy do tuby z jednej strony, po czym przesuwają się one wewnątrz i wychodzą z drugiej strony w tej samej kolejności, w jakiej zostały do tuby włożone.

 

 

Dla kolejki są zdefiniowane operacje:

Jeśli porównasz te operacje z operacjami dostępnymi dla stosu, to okaże się, że obie te struktury są bardzo do siebie podobne. Różnią się jedynie kolejnością dostępu do elementów.

 

Kolejka jako tablica

Naturalną strukturą danych dla kolejek jest lista, jednakże w prostszych przypadkach kolejkę da się zrealizować w tablicy. W takim przypadku musimy założyć z góry maksymalny rozmiar kolejki (ilość przechowywanych w niej elementów). Będziemy potrzebowali trzech zmiennych:

 

Q  –  tablica, w której będzie tworzona kolejka. Tablica ma n elementów, indeksy rozpoczynają się od 0.
qptr  – indeks elementu, który jest początkiem kolejki
qcnt  – liczba elementów, którą przechowuje kolejka

 

Kolejkę tworzą kolejne elementy o indeksach rozpoczynających się od qptr. Na początku qptr wskazuje pierwszy element tablicy o indeksie 0:

 

 

Koniec kolejki wyznacza indeks równy qptr + qcnt. Jeśli indeks ten wykracza poza ostatni element tablicy, to należy go zmniejszyć o n. Dopisanie elementu zwiększa licznik qcnt o 1:

 

 

Odczyt elementu z kolejki polega na przetworzeniu elementu o indeksie qptr. Usunięcie elementu z kolejki polega na zwiększeniu o 1 indeksu qptr. Jeśli po zwiększeniu qptr wskazuje poza ostatni element tablicy, to qptr należy wyzerować – kolejka znów rozpocznie się od początku tablicy. Licznik qptr zawsze zmniejszamy o 1.

 

 

Zwróć uwagę, że w tej implementacji kolejka nie zajmuje stałego położenia w tablicy. Co więcej, jej elementy mogą być rozdzielone:

 

 

Kolejka w tablicy – algorytm sprawdzania, czy kolejka jest pusta

Wejście
qcnt    liczba elementów przechowywana w kolejce
Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:
K01 Jeśli qcnt = 0, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Lazarus Code::Blocks Free Basic
function empty : boolean;
begin
  if qcnt = 0 then empty := true
  else empty := false;
end;
bool empty(void)
{
  return !qcnt;
}
Function empty() As Integer
  If qcnt = 0 Then Return 1
  Return 0
End Function

 

Kolejka w tablicy – algorytm odczytu kolejki

Wejście
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:
K01 Jeśli qcnt = 0, to zakończ z wynikiem wartość specjalna ; kolejka pusta?
K02: Zakończ z wynikiem Q[qptr]  

 

Lazarus
function front : typ_danych;
begin
  if qcnt = 0 then front := wartość_specjalna
  else             front := Q[qptr];
end;
Code::Blocks
typ_danych front()
{
  if(qcnt) return Q[qptr];
  else     return wartość_specjalna;
}
Free Basic
Function front() As typ_danych
  If qcnt = 0 then
    front = wartość_specjalna
  Else
    front = Q(qptr)
  End If
End Function

 

Kolejka w tablicy – algorytm zapisu do kolejki

Wejście
n   liczba elementów w tablicy
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
v   dopisywany element
Wyjście:

Jeśli w tablicy jest miejsce, to do kolejki zostaje dopisana nowa wartość. Inaczej kolejka nie jest zmieniana.

Elementy pomocnicze:
i  –  indeks
Lista kroków:
K01 Jeśli qcnt = n, to zakończ ; sprawdzamy, czy w tablicy jest miejsce na nowy element
K02: iqptr + qcnt ; wyznaczamy położenie końca kolejki
K03: Jeśli in, to ii - n ; korygujemy i w razie potrzeby
K04: Q[i] ← v ; umieszczamy element na końcu kolejki
K05: qcntqcnt + 1 ; zwiększamy liczbę elementów
K06: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure push(v : typ_danych);
var
  i : integer;
begin
  if qcnt < n then
  begin
    i := qptr + qcnt;
    if i >= n then dec(i,n);
    Q[i] := v;
    inc(qcnt);
  end;
end;
void push(typ_danych v)
{
  int i;
  if(qcnt < n)
  {
    i = qptr + qcnt++;
    if(i >= n) i -= n;
    Q[i] = v;
  }
}
Sub push(v As typ_danych)
  Dim i As Integer
  If qcnt < n then
    i = qptr + qcnt
    If i >= n Then i -= n
    Q(i) = v
    qcnt += 1
  End If
End Sub

 

Kolejka w tablicy – algorytm usuwania z kolejki

Wejście
n   liczba elementów w tablicy
Q   tablica, w której przechowywana jest kolejka
qcnt    liczba elementów przechowywana w kolejce
qptr   indeks początku kolejki
Wyjście:

Kolejka pomniejszona o pierwszy element.

Lista kroków:
K01 Jeśli qcnt = 0, to zakończ ; sprawdzamy, czy kolejka zawiera jakieś elementy
K02: qcntqcnt - 1 ; zmniejszamy licznik elementów
K03: qptrqptr + 1 ; przesuwamy początek kolejki
K04: Jeśli qptr = n, to qptr ← 0 ; korygujemy indeks początku kolejki
K05: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure pop;
begin
  if qcnt > 0 then
  begin
    dec(qcnt);
    inc(qptr);
    if qptr = n then qptr := 0;
  end;
end;
void pop()
{
  if(qcnt)
  {
    qcnt--;
    qptr++;
    if(qptr == n) qptr = 0;
  }
}
Sub pop
  If qcnt > 0 Then
    qcnt -= 1
    qptr += 1
    If qptr = n Then qptr = 0
  End If
End Sub

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Poniższy program przedstawia sposób implementacji kolejki w tablicy. Tworzy on obiekt zawierający tablicę liczb całkowitych, wskaźnik początku kolejki i licznik jej elementów oraz metody obsługi tej struktury. Rozmiar tablicy jest określany przy tworzeniu obiektu. W kolejce zostaje zapisanych 10 liczb, a następnie są one odczytywane i wyświetlane.

 

Lazarus
// Kolejka w tablicy
// Data: 28.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program arrqueue;

  type
    Tinteger = array of integer;

// Definicja typu obiektowego queue
//---------------------------------

  queue = object
    private
      n    : integer;   // rozmiar tablicy
      qptr : integer;   // wskaźnik początku kolejki
      qcnt : integer;   // licznik elementów
      Q    : Tinteger;  // tablica dynamiczna

    public
      constructor init(x : integer);
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
constructor queue.init(x : integer);
begin
  n := x;
  SetLength(Q,x);
  qptr := 0;  // początek kolejki na początku tablicy
  qcnt := 0;  // pusta kolejka
end;

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
destructor queue.destroy;
begin
  SetLength(Q,0);
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if qcnt = 0 then empty := true
  else empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if qcnt = 0 then front := -MAXINT
  else             front := Q[qptr];

end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  i : integer;
begin
  if qcnt < n then
  begin
    i := qptr + qcnt;
    if i >= n then dec(i,n);
    Q[i] := v;
    inc(qcnt);
  end;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
begin
  if qcnt > 0 then
  begin
    dec(qcnt);
    inc(qptr);
    if qptr = n then qptr := 0;
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;
  i : integer;

begin
  Q.init(10);

  for i := 1 to 10 do Q.push(i);

  while not Q.empty do
  begin
    writeln(Q.front);
    Q.pop;
  end;

  Q.destroy;
end.
Code::Blocks
// Kolejka w tablicy
// Data: 28.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    int n;      // rozmiar tablicy
    int qptr;   // wskaźnik początku kolejki
    int qcnt;   // licznik elementów
    int * Q;    // tablica dynamiczna

  public:
    queue(int x); // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
queue::queue(int x)
{
  n = x;
  Q = new int[x];
  qptr = qcnt = 0;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
queue::~queue()
{
  delete [] Q;
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !qcnt;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(qcnt) return Q[qptr];
  return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  int i;
  if(qcnt < n)
  {
    i = qptr + qcnt++;
    if(i >= n) i -= n;
    Q[i] = v;
  }
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(qcnt)
  {
    qcnt--;
    qptr++;
    if(qptr == n) qptr = 0;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  queue Q(10); // tworzymy kolejkę na 10 elementów
  int i;

  for(i = 1; i <= 10; i++) Q.push(i);

  while(!Q.empty())
  {
    cout << Q.front() << endl;
    Q.pop();
  }
}
Free Basic
' Kolejka w tablicy
' Data: 28.10.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu obiektowego queue
'---------------------------------

Type queue
  Private:
    n    As Integer      ' rozmiar tablicy
    qptr As Integer      ' wskaźnik początku kolejki
    qcnt As Integer      ' licznik elementów
    Q   As Integer Ptr  ' tablica dynamiczna

  Public:
    Declare Constructor(ByVal x As Integer)
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------
' Program główny
'---------------

Dim Q As queue = 10
Dim i As Integer

For i = 1 To 10: Q.push(i): Next

While Q.empty() = 0
  Print Q.front()
  Q.pop()
Wend

End

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy tablicę dla kolejki
'-----------------------------------------
Constructor queue(ByVal x As Integer)
  n = x
  Q = New Integer [x]
  qptr = 0
  qcnt = 0
End Constructor

' Destruktor - zwalnia tablicę dynamiczną
'----------------------------------------
Destructor queue()
  Delete [] Q
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If qcnt = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If qcnt = 0 then
    front = -MAXINT
  Else
    front = Q[qptr]
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim i As Integer
  If qcnt < n then
    i = qptr + qcnt
    If i >= n Then i -= n
    Q[i] = v
    qcnt += 1
  End If
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  If qcnt > 0 Then
    qcnt -= 1
    qptr += 1
    If qptr = n Then qptr = 0
  End If
End Sub
Wynik
1
2
3
4
5
6
7
8
9
10

 

Kolejka jako lista

Do realizacji kolejki posłużymy się lekko zmodyfikowaną listą jednokierunkową. Będziemy potrzebowali dwóch wskaźników:

 

head  –  wskaźnik pierwszego elementu na liście
tail  – wskaźnik ostatniego elementu na liście

 

Nowe elementy dodajemy na koniec listy – dzięki wskaźnikowi tail szybko będziemy mogli znaleźć ostatni element i dołączyć za nim element wstawiany. Pobieranie elementów będzie się odbywało z początku listy. Budowa elementów listy jest typowa: każdy zawiera pole next, które wskazuje kolejny element na liście, oraz pole data, które zawiera przechowywane dane:

Typ elementu listy

Lazarus Code::Blocks Free Basic
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : typ_danych;
  end;
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
Type slistEl
  next As slistEl Ptr
  data As typ_danych
End Type

 

Kolejka na liście – algorytm sprawdzania, czy kolejka jest pusta

Wejście
head    wskaźnik początku kolejki
Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:
K01 Jeśli head = nil, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Lazarus Code::Blocks Free Basic
function empty : boolean;
begin
  if head = nil then empty := true
  else empty := false;
end;
bool empty(void)
{
  return !head;
}
Function empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

 

Kolejka na liście – algorytm odczytu kolejki

Wejście
head    wskaźnik pierwszego elementu listy
Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:
K01 Jeśli head = 0, to zakończ z wynikiem wartość specjalna ; kolejka pusta?
K02: Zakończ z wynikiem (headdata)  

 

Lazarus
function front : typ_danych;
begin
  if head = nil then front := wartość_specjalna
  else               front := head^.data;
end;
Code::Blocks
typ_danych front()
{
  if(head) return head->data;
  else     return wartość_specjalna;
}
Free Basic
Function front() As typ_danych
  If head = 0 then
    front = wartość_specjalna
  Else
    front = head->data
  End If
End Function

 

Kolejka na liście – algorytm zapisu do kolejki

Wejście
head    wskaźnik pierwszego elementu listy
tail   wskaźnik ostatniego elementu listy
v   dopisywany element
Wyjście:

Kolejka z dopisanym na końcu elementem o wartości v.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Utwórz nowy element listy  
K02: p ← adres nowego elementu  
K03: (pnext) ← nil ; inicjujemy pola nowego elementu
K04: (pdata) ← v  
K05: Jeśli tail ≠ nil, to idź do K08 ; sprawdzamy, czy lista jest pusta
K06: headp ; jeśli tak, to wprowadzamy do niej element jako pierwszy i ostatni
K07 Idź do K09  
K08: (tailnext) ← p ; inaczej element dołączamy na koniec listy
K09: tailp ; ustawiamy element jako ostatni na liście
K10: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure push(v : typ_danych);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;
void push(typ_danych v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}
Sub push(v As typ_danych)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

 

Kolejka na liście – algorytm usuwania z kolejki

Wejście
head    wskaźnik pierwszego elementu listy
tail   wskaźnik ostatniego elementu listy
Wyjście:

Kolejka pomniejszona o pierwszy element.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Jeśli head = nil, to zakończ ; jeśli lista jest pusta, kończymy
K02: phead ;zapamiętujemy adres pierwszego elementu
K03: head ← (headnext) ;odłączamy od listy pierwszy element
K04: Jeśli head = nil, to tail ← nil ; jeśli lista stała się pusta, to nie posiada ostatniego elementu
K05: Usuń z pamięci element wskazywany przez p  
K06: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;
void pop()
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }  
}
Sub pop
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Poniższy program przedstawia sposób implementacji kolejki za pomocą listy. W kolejce zostaje zapisanych 10 liczb, a następnie są one odczytywane i wyświetlane.

 

Lazarus Code::Blocks Free Basic
// Kolejka na liście
// Data: 28.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program lqueue;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      head : PslistEl;
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  head := nil;
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if head = nil then empty := true
  else               empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if head = nil then front := -MAXINT
  else               front := head^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.next := nil;
  p^.data := v;
  if tail = nil then head := p
  else tail^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if head <> nil then
  begin
    p := head;
    head := head^.next;
    if head = nil then tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;   // kolejka
  i : integer;

begin
  Q.init;

  for i := 1 to 10 do Q.push(i);

  while not Q.empty do
  begin
    writeln(Q.front);
    Q.pop;
  end;

  Q.destroy;
end.
// Kolejka na liście
// Data: 28.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * head;
    slistEl * tail;

  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  head = tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(head) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !head;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(head) return head->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->next = NULL;
  p->data = v;
  if(tail) tail->next = p;
  else     head = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(head)
  {
    slistEl * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  queue Q; // kolejka
  int i;

  for(i = 1; i <= 10; i++) Q.push(i);

  while(!Q.empty())
  {
    cout << Q.front() << endl;
    Q.pop();
  }
}
' Kolejka na liście
' Data: 28.10.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    head As slistEl Ptr
    tail As slistEl Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  head = 0
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While empty = 0: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If head = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If head = 0 then
    front = -MAXINT
  Else
    front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->next = 0
  p->data = v
  If tail = 0 Then
    head = p
  Else
    tail->next = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If head Then
    p = head
    head = head->next
    If head = 0 Then tail = 0
    Delete p
  End If
End Sub

'---------------
' Program główny
'---------------

Dim Q As queue
Dim i As Integer

For i = 1 To 10: Q.push(i): Next

While Q.empty() = 0
  Print Q.front()
  Q.pop()
Wend

End

 

Kolejka cykliczna

Jeśli do implementacji kolejki zastosujemy listę cykliczną, to otrzymamy tzw. kolejkę cykliczną (ang. circular queue). W porównaniu ze zwykłą kolejką, kolejka cykliczna wymaga tylko jednego wskaźnika tail, który wskazuje koniec kolejki. Początek kolejki jest następnikiem jej ostatniego elementu.

 

Kolejka cykliczna – algorytm sprawdzania, czy kolejka jest pusta

Wejście
tail    wskaźnik końca kolejki
Wyjście:

True, jeśli kolejka jest pusta, inaczej false

Lista kroków:
K01 Jeśli tail = nil, to zakończ z wynikiem true
K02: Zakończ z wynikiem false

 

Lazarus Code::Blocks Free Basic
function empty : boolean;
begin
  if tail = nil then empty := true
  else empty := false;
end;
bool empty(void)
{
  return !tail;
}
Function empty() As Integer
  If tail = 0 Then Return 1
  Return 0
End Function

 

Kolejka cykliczna – algorytm odczytu kolejki

Wejście
tail    wskaźnik ostatniego elementu listy
Wyjście:

Wartość elementu na początku kolejki lub wartość specjalna, jeśli kolejka jest pusta.

Lista kroków:
K01 Jeśli tail = 0, to zakończ z wynikiem wartość specjalna ; kolejka pusta?
K02: Zakończ z wynikiem ((tailnext)→data) ; zwróć wartość następnego elementu za ostatnim

 

Lazarus
function front : typ_danych;
begin
  if tail = nil then front := wartość_specjalna
  else               front := tail^.next^.data;
end;
Code::Blocks
typ_danych front()
{
  if(tail) return tail->next->data;
  else     return wartość_specjalna;
}
Free Basic
Function front() As typ_danych
  If tail = 0 then
    front = wartość_specjalna
  Else
    front = tail->next->data
  End If
End Function

 

Kolejka cykliczna – algorytm zapisu do kolejki

Wejście
tail   wskaźnik ostatniego elementu listy
v   dopisywany element
Wyjście:

Kolejka z dopisanym na końcu elementem o wartości v.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Utwórz nowy element listy  
K02: p ← adres nowego elementu  
K03: (pdata) ← v ; inicjujemy pola nowego elementu
K04: Jeśli tail = nil, to idź do K08 ; sprawdzamy, czy kolejka jest pusta
K05: (pnext) ← (tailnext) ; następnikiem jest pierwszy element
K06: (tailnext) ← p ; element wstawiamy na listę za ostatnim
K07 Idź do K09  
K08: (pnext) ← p ; następnikiem jest ten sam element
K09: tailp ; nowy element staje się ostatnim
K10: Zakończ  

 

Lazarus Code::Blocks Free Basic
procedure push(v : typ_danych);
var
  p : PslistEl;
begin
  new(p);
  p^.data := v;
  if tail <> nil then
  begin
    p^.next    := tail^.next;
    tail^.next := p;
  end
  else p^.next := p;
  tail := p;
end;
void push(typ_danych v)
{
  slistEl * p = new slistEl;
  p->data = v;
  if(tail)
  {
    p->next    = tail->next;
    tail->next = p;
  }
  else p->next = p;
  tail = p;
}
Sub push(v As typ_danych)
  Dim p As slistEl Ptr
  p = new slistEl
  p->data = v
  If tail Then
    p->next    = tail->next
    tail->next = p
  Else
    p->next    = p
  End If
  tail = p
End Sub

 

Kolejka cykliczna – algorytm usuwania z kolejki

Wejście
tail   wskaźnik ostatniego elementu listy
Wyjście:

Kolejka pomniejszona o pierwszy element.

Elementy pomocnicze:
p  –  wskaźnik elementu listy
Lista kroków:
K01 Jeśli tail = nil, to zakończ ; jeśli lista jest pusta, kończymy
K02: p ← (tailnext) ; w p pierwszy element
K03: Jeśli (pnext) = p, to idź do K06 ; kolejka zawiera tylko jeden element?
K04: (tailnext) ← (pnext) ; usuwamy pierwszy element z listy
K05: Idź do K07  
K06: tail ← nil ; tworzymy pustą listę
K07: Usuń z pamięci element wskazywany przez p  
K08: Zakończ  

 

Lazarus
procedure pop;
var
  p : PslistEl;
begin
  if tail <> nil then
  begin
    p := tail^.next;
    if p^.next <> p then tail^.next := p^.next
    else                 tail := nil;
    dispose(p);
  end;
end;
Code::Blocks
void pop()
{
  if(tail)
  {
    slistEl * p = tail->next;
    if(p->next != p) tail->next = p->next;
    else             tail = NULL;
    delete p;
  }  
}
Free Basic
Sub pop
  Dim p As slistEl Ptr
  If tail Then
    p = tail->next
    If p->next <> p Then
      tail->next = p->next
    Else
      tail = 0
    End If
    Delete p
  End If
End Sub

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Poniższy program przedstawia sposób implementacji kolejki cyklicznej. W kolejce zostaje zapisanych 10 liczb, a następnie są one odczytywane i wyświetlane.

 

Lazarus
// Kolejka cykliczna
// Data: 29.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program cqueue;

// Definicja typu elementów listy
//-------------------------------
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : integer;
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      tail : PslistEl;

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      procedure push(v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  tail := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  while not empty do pop;
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  if tail = nil then empty := true
  else empty := false;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
begin
  if tail = nil then front := -MAXINT
  else               front := tail^.next^.data;
end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(v : integer);
var
  p : PslistEl;
begin
  new(p);
  p^.data := v;
  if tail <> nil then
  begin
    p^.next    := tail^.next;
    tail^.next := p;
  end
  else p^.next := p;
  tail := p;
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PslistEl;
begin
  if tail <> nil then
  begin
    p := tail^.next;
    if p^.next <> p then tail^.next := p^.next
    else                 tail := nil;
    dispose(p);
  end;
end;

//---------------
// Program główny
//---------------

var
  Q : queue;   // kolejka
  i : integer;

begin
  Q.init;

  for i := 1 to 10 do Q.push(i);

  while not Q.empty do
  begin
    writeln(Q.front);
    Q.pop;
  end;

  Q.destroy;
end.
Code::Blocks
// Kolejka cykliczna
// Data: 29.10.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>

using namespace std;

const int MAXINT = -2147483647;

// Definicja typu elementów listy
//-------------------------------
struct slistEl
{
  slistEl * next;
  int data;
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    slistEl * tail;
  public:
    queue();      // konstruktor
    ~queue();     // destruktor
    bool empty(void);
    int  front(void);
    void push(int v);
    void pop(void);
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  tail = NULL;
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  while(tail) pop();
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty(void)
{
  return !tail;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front(void)
{
  if(tail) return tail->next->data;
  else     return -MAXINT;
}

// Zapisuje do kolejki
//--------------------
void queue::push(int v)
{
  slistEl * p = new slistEl;
  p->data = v;
  if(tail)
  {
    p->next    = tail->next;
    tail->next = p;
  }
  else p->next = p;
  tail = p;
}

// Usuwa z kolejki
//----------------
void queue::pop(void)
{
  if(tail)
  {
    slistEl * p = tail->next;
    if(p->next != p) tail->next = p->next;
    else             tail = NULL;
    delete p;
  }
}

//---------------
// Program główny
//---------------

int main()
{
  queue Q; // kolejka
  int i;

  for(i = 1; i <= 10; i++) Q.push(i);

  while(!Q.empty())
  {
    cout << Q.front() << endl;
    Q.pop();
  }
}
Free Basic
' Kolejka cykliczna
' Data: 29.10.2012
' (C)2012 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

' Definicja typu elementów listy
'-------------------------------
Type slistEl
  next As slistEl Ptr
  data As Integer
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    tail As slistEl Ptr
    
  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

'---------------
' Program główny
'---------------

Dim Q As queue
Dim i As Integer

For i = 1 To 10: Q.push(i): Next

While Q.empty() = 0
  Print Q.front()
  Q.pop()
Wend

End

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  tail = 0
End Constructor

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  While Not empty: pop: Wend
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  If tail = 0 Then Return 1
  Return 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  If tail = 0 then
    front = -MAXINT
  Else
    front = tail->next->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal v As Integer)
  Dim p As slistEl Ptr
  p = new slistEl
  p->data = v
  If tail Then
    p->next    = tail->next
    tail->next = p
  Else
    p->next    = p
  End If
  tail = p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim p As slistEl Ptr
  If tail Then
    p = tail->next
    If p->next <> p Then
      tail->next = p->next
    Else
      tail = 0
    End If
    Delete p
  End If
End Sub
Wynik
1
2
3
4
5
6
7
8
9
10

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe