Algorytmy i Struktury Danych - Podstawowe pojęcia dotyczące kolejek

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:

–

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

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 ( head→data )

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:

–

wskaźnik elementu listy

Lista kroków:

K01	Utwórz nowy element listy
K02:	p ← adres nowego elementu
K03:	( p→next ) ← nil	inicjujemy pola nowego elementu
K04:	( p→data ) ← 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:	( tail→next ) ← 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:

–

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 ← ( head→next )	;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

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 ( ( tail→next )→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:

–

wskaźnik elementu listy

Lista kroków:

K01	Utwórz nowy element listy
K02:	p ← adres nowego elementu
K03:	( p→data ) ← v	inicjujemy pola nowego elementu
K04:	Jeśli tail = nil, to idź do kroku K08	sprawdzamy, czy kolejka jest pusta
K05:	( p→next ) ← ( tail→next )	następnikiem jest pierwszy element
K06:	( tail→next ) ← p	element wstawiamy na listę za ostatnim
K07	Idź do kroku K09
K08:	( p→next ) ← 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:

–

wskaźnik elementu listy

Lista kroków:

K01	Jeśli tail = nil, to zakończ	jeśli lista jest pusta, kończymy
K02:	p ← ( tail→next )	w p pierwszy element
K03:	Jeśli ( p→next ) = p, to idź do kroku K06	kolejka zawiera tylko jeden element?
K04:	( tail→next ) ← ( p→next )	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

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.

Podstawowe pojęcia dotyczące kolejek

Kolejka jako tablica

Kolejka w tablicy – algorytm sprawdzania, czy kolejka jest pusta

Wejście:

Wyjście:

Kolejka w tablicy – algorytm odczytu kolejki

Wejście:

Wyjście:

Kolejka w tablicy – algorytm zapisu do kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Kolejka w tablicy – algorytm usuwania z kolejki

Wejście:

Wyjście:

Przykładowe programy

Kolejka jako lista

Typ elementu listy

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

Wejście:

Wyjście:

Kolejka na liście – algorytm odczytu kolejki

Wejście:

Wyjście:

Kolejka na liście – algorytm zapisu do kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Kolejka na liście – algorytm usuwania z kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy

Kolejka cykliczna

Kolejka cykliczna – algorytm sprawdzania, czy kolejka jest pusta

Wejście:

Wyjście:

Kolejka cykliczna – algorytm odczytu kolejki

Wejście:

Wyjście:

Kolejka cykliczna – algorytm zapisu do kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Kolejka cykliczna – algorytm usuwania z kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy