Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Podstawowe pojęcia dotyczące kolejek

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

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.

obrazek

Dla kolejki są zdefiniowane operacje:

  • Sprawdzenie, czy kolejka jest pusta – operacja empty zwraca true, jeśli kolejka nie zawiera żadnego elementu, w przeciwnym razie zwraca false.
  • Odczyt elementu z początku kolejki – operacja front zwraca wskazanie do elementu, który jest pierwszy w kolejce.
  • Zapis elementu na koniec kolejki – operacja push dopisuje nowy element na koniec elementów przechowywanych w kolejce.
  • Usunięcie elementu z kolejki – operacja pop usuwa z kolejki pierwszy element.

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:

obrazek

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:

obrazek

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.

obrazek

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

obrazek

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
Pascal
function empty : boolean;
begin
  if qcnt = 0 then empty := true
  else empty := false;
end;
   C++
bool empty ( void )
{
  return !qcnt;
}
   Basic
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  ]  
Pascal
function front : typ_danych;
begin
  if qcnt = 0 then front := wartość_specjalna
  else             front := Q [ qptr ];
end;
C++
typ_danych front( )
{
  if( qcnt ) return Q [ qptr ];
  else     return wartość_specjalna;
}
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.

Zmienne pomocnicze:

i  –  indeks

Lista kroków:

K01 Jeśli qcnt  = n,
to zakończ
sprawdzamy, czy w tablicy jest miejsce na nowy element
K02: i  ← qptr  + qcnt wyznaczamy położenie końca kolejki
K03: Jeśli i  ≥ n,
to i  ← i  - n
korygujemy i w razie potrzeby
K04: Q [ i  ] ← v umieszczamy element na końcu kolejki
K05: qcnt  ← qcnt  + 1 zwiększamy liczbę elementów
K06: Zakończ  
Pascal
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;
   C++
void push ( typ_danych v )
{
  int i;
  if( qcnt < n )
  {
    i = qptr + qcnt++;
    if( i >= n ) i -= n;
    Q [ i ] = v;
  }
}
   Basic
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: qcnt  ← qcnt  - 1 zmniejszamy licznik elementów
K03: qptr  ← qptr  + 1 przesuwamy początek kolejki
K04: Jeśli qptr  = n, to qptr  ← 0 korygujemy indeks początku kolejki
K05: Zakończ  
Pascal
procedure pop;
begin
  if qcnt > 0 then
  begin
    dec ( qcnt );
    inc ( qptr );
    if qptr = n then qptr := 0;
  end;
end;
   C++
void pop( )
{
  if( qcnt )
  {
    qcnt--;
    qptr++;
    if( qptr == n ) qptr = 0;
  }
}
   Basic
Sub pop
  If qcnt > 0 Then
    qcnt -= 1
    qptr += 1
    If qptr = n Then qptr = 0
  End If
End Sub

Przykładowe programy

Uwaga:

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.
Pascal
// Kolejka w tablicy
// Data: 28.10.2012
// (C)2020 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.
C++
// Kolejka w tablicy
// Data: 28.10.2012
// (C)2020 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( );
  }
}
Basic
' Kolejka w tablicy
' Data: 28.10.2012
' (C)2020 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
Na początek:  podrozdziału   strony 

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

Pascal
type
  PslistEl = ^slistEl;
  slistEl = record
    next  : PslistEl;
    data  : typ_danych;
  end;
 
   C++
struct slistEl
{
  slistEl * next;
  typ_danych data;
};
   Basic
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
Pascal
function empty : boolean;
begin
  if head = nil then empty := true
  else empty := false;
end;
   C++
bool empty ( void )
{
  return !head;
}
   Basic
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  )  
Pascal
function front : typ_danych;
begin
  if head = nil then front := wartość_specjalna
  else               front := head^.data;
end;
C++
typ_danych front( )
{
  if( head ) return head->data;
  else     return wartość_specjalna;
}
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.

Zmienne 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: head  ← p 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: tail  ← p ustawiamy element jako ostatni na liście
K10: Zakończ  
Pascal
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;
   C++
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;
}
   Basic
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.

Zmienne 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: p  ← head ;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  
Pascal
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;
   C++
void pop( )
{
  if( head )
  {
    slistEl * p = head;
    head = head->next;
    if( !head ) tail = NULL;
    delete p;
  }  
}
   Basic
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

Przykładowe programy

Uwaga:

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.
Pascal
// Kolejka na liście
// Data: 28.10.2012
// (C)2020 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.
C++
// Kolejka na liście
// Data: 28.10.2012
// (C)2020 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( );
  }
}
Basic
' Kolejka na liście
' Data: 28.10.2012
' (C)2020 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
Na początek:  podrozdziału   strony 

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.

obrazek

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
Pascal
function empty : boolean;
begin
  if tail = nil then empty := true
  else empty := false;
end;
   C++
bool empty ( void )
{
  return !tail;
}
   Basic
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
Pascal
function front : typ_danych;
begin
  if tail = nil then front := wartość_specjalna
  else               front := tail^.next^.data;
end;
C++
typ_danych front( )
{
  if( tail ) return tail->next->data;
  else     return wartość_specjalna;
}
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.

Zmienne 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 kroku 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 kroku K09  
K08: ( pnext  ) ← p następnikiem jest ten sam element
K09: tail  ← p nowy element staje się ostatnim
K10: Zakończ  
Pascal
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;
   C++
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;
}
   Basic
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.

Zmienne 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 kroku K06
kolejka zawiera tylko jeden element?
K04: ( tailnext  ) ← ( pnext  ) usuwamy pierwszy element z listy
K05: Idź do kroku K07  
K06: tail  ← nil tworzymy pustą listę
K07: Usuń z pamięci element
wskazywany przez p
 
K08: Zakończ  
Pascal
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;
C++
void pop( )
{
  if( tail )
  {
    slistEl * p = tail->next;
    if( p->next != p ) tail->next = p->next;
    else             tail = NULL;
    delete p;
  }  
}
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

Przykładowe programy

Uwaga:

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.
Pascal
// Kolejka cykliczna
// Data: 29.10.2012
// (C)2020 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.
C++
// Kolejka cykliczna
// Data: 29.10.2012
// (C)2020 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( );
  }
}
Basic
' Kolejka cykliczna
' Data: 29.10.2012
' (C)2020 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
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.