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 struktury zawierającej cztery pola:

q : tablica, w której będzie tworzona kolejka. Tablica ma n elementów, indeksy rozpoczynają się od 0.
n : liczba komórek tablicy q, co jednocześnie określa maksymalną długość kolejki.
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. Nowy element dopisywany jest w elemencie o indeksie qptr+qcnt. 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 – empty( ) : 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

Kolejka w tablicy – front( ) : odczyt początku kolejki

Wejście:

q : tablica, w której przechowywana jest kolejka.
qcnt : liczba elementów 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, ; kolejka pusta?
     to zakończ z wynikiem wartość specjalna
K02: Zakończ z wynikiem q[qptr]

Kolejka w tablicy – push(v) : zapis na koniec 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ść v. Inaczej kolejka nie jest zmieniana.

Elementy pomocnicze:

i : indeks.

Lista kroków:

K01: Jeśli qcnt = n, ; sprawdzamy, czy w tablicy jest
     to zakończ      ; miejsce na nowy element
K02: i ← qptr+qcnt ; wyznaczamy położenie końca kolejki
K03: Jeśli i ≥ n,  ; korygujemy w razie potrzeby
     to i ← i-n
K04: q[i] ← v ; umieszczamy element na końcu kolejki
K05: qcnt ← qcnt+1 ; zwiększamy długość kolejki
K06: Zakończ

Kolejka w tablicy – pop( ) : usuwanie z początku 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. Jeśli kolejka jest pusta, to nic nie zostaje usunięte.

Lista kroków:

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

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;

  // Typ elementów tablicy
  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 q_empty : boolean;
      function q_front : integer;
      procedure push(v : integer);
      procedure q_pop;
  end;

//----------------------
// Metody obiektu Queue
//----------------------

// Konstruktor - tworzy tablicę dla kolejki
//-----------------------------------------
constructor Queue.init(x : integer);
begin
  n := x;    // Rozmiar tablicy dynamicznej
  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);
  n = 0;
  qptr = 0;
  qcnt = 0;
end;

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

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function Queue.q_front : integer;
begin
  if qcnt = 0 then
    q_front := -MAXINT
  else
    q_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.q_pop;
begin
  if qcnt > 0 then
  begin
    dec(qcnt);
    inc(qptr);
    if qptr = n then
      qptr := 0;
  end;
end;

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

var
  K : Queue;
  i : integer;

begin
  K.init(10);
  for i := 1 to 10 do K.push(i);
  while not K.q_empty do
  begin
    writeln(K.q_front);
    K.q_pop;
  end;
  K.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]; // Tablica dynamiczna
  qptr = qcnt = 0;
}

// Destruktor - zwalnia tablicę dynamiczną
//----------------------------------------
Queue::~Queue()
{
  delete [] q;
  n = qptr = qcnt = 0;
}

// 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 K(10); // tworzymy kolejkę na 10 elementów
  int i;

  for(i = 1; i <= 10; i++) K.push(i);
  while(!K.empty())
  {
    cout << K.front() << endl;
    K.pop();
  }
  return 0;
}

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 q_front As Integer
    Declare Sub push(ByVal v As Integer)
    Declare Sub pop()
End Type

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

Dim K As Queue = 10 // Obiekt kolejki
Dim i As Integer

For i = 1 To 10
  K.push(i) // Wstawiamy do kolejki
Next

While K.empty() = 0
  Print K.front() // Wyświetlamy kolejkę
  K.pop()
Wend
End

'----------------------
' Metody obiektu Queue
'----------------------

' Konstruktor - tworzy tablicę dla kolejki
'-----------------------------------------
Constructor Queue(ByVal x As Integer)
  n = x
  q = New Integer [x] // Tablica dynamiczna
  qptr = 0
  qcnt = 0
End Constructor

' Destruktor - zwalnia tablicę dynamiczną
'----------------------------------------
Destructor Queue()
  Delete [] q
  n = 0
  qptr = 0
  qcnt = 0
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
    q_front = -MAXINT
  Else
    q_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

Python (dodatek)

# Kolejka w tablicy
# Data: 28.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

MAXINT = 2147483647


# Definicja typu obiektowego Queue
#-----------------------------------
class Queue:


    # Konstruktor
    def __init__(self, x):
        self.n = x
        self.q = [0]*x
        self.qptr = 0
        self.qcnt = 0


    # destruktor
    def __del__(self):
        self.q = None
        self.n = 0
        self.qptr = 0
        self.qcnt = 0


    # sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.qcnt


    # zwraca początek kolejki
    # wartość specjalna to -MAXINT
    def front(self):
        if self.qcnt:
            return self.q[self.qptr]
        return -MAXINT


    # zapisuje do kolejki
    def push(self, v):
        if self.qcnt < self.n:
            i = self.qptr+self.qcnt
            self.qcnt += 1
            if i >= self.n:
                i -= self.n
            self.q[i] = v


    # usuwa z kolejki
    def pop(self):
        if self.qcnt:
            self.qcnt -= 1
            self.qptr += 1
            if self.qptr == self.n:
                self.qptr = 0


#---------------
# Program główny
#---------------

q = Queue(10) # Obiekt kolejki
for i in range(1, 11):
    push(i)
while not q.empty():
    print(q.front())
    q.pop()

Wynik:

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 kolejki

Pascal

// Typ elementu
type
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    data  : typ_danych;
  end;

// Typ obiektu kolejki
Queue = object
  private
    head : PSLel;
    tail : PSLel;
  public
    ...
end;

C++

// Typ elementu
struct SLel
{
  SLel * next;
  typ_danych data;
};
// Klasa kolejki
class Queue
{
  private:
    SLel * head;
    SLel * tail;
  public:
    ...
};

Basic

' Typ elementu
Type SLel
  next As SLel Ptr
  data As typ_danych
End Type
' Typ kolejki
Type Queue
  Private:
    head as SLel Ptr
    tail as SLel Ptr
  Public:
    ...
End Type

Python (dodatek)

# klasa elementu listy
# jednokierunkowej
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa kolejki
class Queue:


    def __init__(self)
        self.head = None
        self.tail = None
    ...

Kolejka na liście – empty( ) : sprawdza, 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

Kolejka na liście – front( ) : odczyt początku kolejki

Wejście:

head : wskaźnik 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 head = 0, ; kolejka pusta?
     to zakończ z wynikiem wartość specjalna
K02: Zakończ z wynikiem head→data

Kolejka na liście – push(v) : zapis na koniec kolejki

Wejście:

head : wskaźnik pierwszego elementu listy.
tail : wskaźnik ostatniego elementu listy.
v : zapisywana w kolejce wartość

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: p→next ← nil ; inicjujemy pola
K04: p→data ← v ; nowego elementu
K05: Jeśli tail ≠ nil, ; sprawdzamy, 
     to idź do K08 ; czy kolejka jest pusta
K06: head ← p ; jeśli tak, to wprowadzamy do niej
     ; element p jako pierwszy i ostatni
K07: Idź do K09
K08: tail→next ← p ;inaczej element
K09: tail ← p ; dołączamy na koniec listy
K10: Zakończ

Kolejka na liście – pop( ) : usuwa z początku 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, ; jeśli lista jest pusta, 
     to zakończ ; 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, ; jeśli lista stała się pusta, 
     to tail ← nil ; to nie posiada ostatniego elementu
K05: Usuń z pamięci element
     wskazywany przez p
K06: Zakończ

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
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    data  : integer;
  end;

// Definicja typu obiektowego Queue
//---------------------------------
  Queue = object
    private
      head : PSLel;
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function q_empty : boolean;
      function q_front : integer;
      procedure q_push (v : integer);
      procedure q_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 q_empty do q_pop;
end;

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

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

// Zapisuje do kolejki
//--------------------
procedure Queue.push(v : integer);
var
  p : PSLel;
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.q_pop;
var
  p : PSLel;
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
  K : Queue;   // kolejka
  i : integer;

begin
  K.init;

  for i := 1 to 10 do
    K.push(i);
  while not K.q_empty do
  begin
    writeln(K.q_front);
    K.q_pop;
  end;

  K.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 SLel
{
  SLel * next;
  int data;
};

// Definicja typu obiektowego Queue
//----------------------------------
class Queue
{
  private:
    SLel * head;
    SLel * 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)
{
  SLel * p = new SLel;
  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)
  {
    SLel * p = head;
    head = head->next;
    if(!head) tail = NULL;
    delete p;
  }
}

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

int main()
{
  Queue K; // kolejka
  int i;

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

  while(!K.empty())
  {
    cout << K.front() << endl;
    K.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 SLel
  next As SLel Ptr
  data As Integer
End Type

' Definicja typu obiektowego Queue
'----------------------------------
Type Queue
  Private:
    head As SLel Ptr
    tail As SLel Ptr

  Public:
    Declare Constructor()
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function q_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 q_empty = 0
    q_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
    q_front = -MAXINT
  Else
    q_front = head->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  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 SLel 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 K As Queue
Dim i As Integer

For i = 1 To 10
  K.push(i)
Next

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

End

Python (dodatek)

# Kolejka na liście
# Data: 29.06.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

MAXINT = 2147483647


# klasa elementu listy
# jednokierunkowej
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa kolejki
class Queue:


    # Konstruktor - tworzy pustą listę
    def __init__(self):
        self.head = None
        self.tail = None


    # Destruktor - usuwa listę z pamięci
    def __del__(self):
        while not self.empty():
            self.pop()


    # Sprawdza, czy kolejka jest pusta
    def empty(self):
        if self.head:
            return False
        else:
            return True


    # Zwraca początek kolejki.
    # Wartość specjalna to -MAXINT
    def front(self):
        if self.head:
            return self.head.data
        else:
            return -MAXINT


    # Zapisuje do kolejki
    def push(self, v):
        p = SLel(v)
        if self.tail:
            self.tail.next = p
        else:
            self.head = p
        self.tail = p


    # Usuwa z kolejki
    def pop(self):
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None


# ---------------
# Program główny
# ---------------

q = Queue()
for i in range(1, 11):
    push(i)
while not q.empty():
    print(q.front())
    q.pop()

Wynik:

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.

Kolejka cykliczna – empty( ) : sprawdza, 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

Kolejka cykliczna – front( ) : odczyt kolejki

Wejście:

tail : wskaźnik końca kolejki.

Wyjście:

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

Lista kroków:

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

Kolejka cykliczna – push(v) : zapis 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: p→data ← v ; inicjujemy pola nowego elementu
K04: Jeśli tail = nil, ; sprawdzamy, czy kolejka jest pusta
     to idź do kroku K08
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

Kolejka cykliczna – pop( ) : usuwanie z kolejki

Wejście:

tail : wskaźnik końca kolejki.

Wyjście:

Kolejka pomniejszona o pierwszy element.

Zmienne pomocnicze:

p : wskaźnik elementu listy.

Lista kroków:

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

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
  PSLel = ^SLel;
  SLel = record
    next  : PSLel;
    data  : integer;
  end;

// Definicja typu obiektowego Queue
//----------------------------------
  Queue = object
    private
      tail : PSLel;

    public
      constructor init;
      destructor destroy;
      function q_empty : boolean;
      function q_front : integer;
      procedure push(v : integer);
      procedure q_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 q_empty do q_pop;
end;

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

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

// Zapisuje do kolejki
//--------------------
procedure Queue.push(v : integer);
var
  p : PSLel;
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.q_pop;
var
  p : PSLel;
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
  K : Queue; // kolejka
  i : integer;

begin
  K.init;

  for i := 1 to 10 do
    K.q_push (i);

  while not K.q_empty do
  begin
    writeln(K.q_front);
    K.q_pop;
  end;

  K.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 SLel
{
  SLel * next;
  int data;
};

// Definicja typu obiektowego Queue
//----------------------------------
class Queue
{
  private:
    SLel * 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)
{
  SLel * p = new SLel;
  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)
  {
    SLel * p = tail->next;
    if(p->next != p)
      tail->next = p->next;
    else
      tail = NULL;
    delete p;
  }
}

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

int main()
{
  Queue K; // kolejka
  int i;

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

  while(!K.empty())
  {
    cout << K.front() << endl;
    K.pop();
  }
}

Basic

' Kolejka cykliczna
' Data: 29.10.2012
' (C)2020 mgr Jerzy Wałaszek
'------------------------------

Const MAXINT = 2147483647

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

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

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

Dim K As Queue
Dim i As Integer

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

While K.empty() = 0
  Print K.front()
  K.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 q_empty: q_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
    q_front = -MAXINT
  Else
    q_front = tail->next->data
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub Queue.push(ByVal v As Integer)
  Dim p As SLel Ptr
  p = new SLel
  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 SLel 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

Python (dodatek)

# Kolejka cykliczna
# Data: 29.06.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

MAXINT = -2147483647


# obiekt elementów listy
#-----------------------
class SLel:


    # Konstruktor
    def __init__(self, v):
        self.next = None
        self.data = v


# obiekt kolejki cyklicznej Queue
#---------------------------------
class Queue:


    # Konstruktor
    def __init__(self):
        self.tail = None


    # destruktor
    def __del__(self):
        while self.tail:
            self.pop()


    # sprawdza, czy kolejka jest pusta
    def empty(self):
        return not self.tail


    # zwraca początek kolejki
    # wartość specjalna to -MAXINT
    def front(self):
        if self.tail:
            return self.tail.next.data
        else:
            return -MAXINT


    # zapisuje do kolejki
    def push(self, v):
        p = SLel(v)
        if self.tail:
            p.next = self.tail.next
            self.tail.next = p
        else:
            p.next = p
        self.tail = p


    # usuwa z kolejki
    def pop(self):
        if self.tail:
            p = self.tail.next
            if p.next is not p:
                self.tail.next = p.next
            else:
                self.tail = None


#---------------
# Program główny
#---------------

q = Queue() # kolejka
for i in range(1, 11):
    push(i)
while not q.empty():
    print(q.front())
    q.pop()

Wynik:

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 – empty( ) : sprawdzania, czy kolejka jest pusta

Wejście:

Wyjście:

Kolejka w tablicy – front( ) : odczyt początku kolejki

Wejście:

Wyjście:

Kolejka w tablicy – push(v) : zapis na koniec kolejki

Wejście:

Wyjście:

Elementy pomocnicze:

Kolejka w tablicy – pop( ) : usuwanie z początku kolejki

Wejście:

Wyjście:

Przykładowe programy

Kolejka jako lista

Typ kolejki

Kolejka na liście – empty( ) : sprawdza, czy kolejka jest pusta

Wejście:

Wyjście:

Kolejka na liście – front( ) : odczyt początku kolejki

Wejście:

Wyjście:

Kolejka na liście – push(v) : zapis na koniec kolejki

Wejście:

Wyjście:

Elementy pomocnicze:

Kolejka na liście – pop( ) : usuwa z początku kolejki

Wejście:

Wyjście:

Elementy pomocnicze:

Przykładowe programy

Kolejka cykliczna

Kolejka cykliczna – empty( ) : sprawdza, czy kolejka jest pusta

Wejście:

Wyjście:

Kolejka cykliczna – front( ) : odczyt kolejki

Wejście:

Wyjście:

Kolejka cykliczna – push(v) : zapis do kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Kolejka cykliczna – pop( ) : usuwanie z kolejki

Wejście:

Wyjście:

Zmienne pomocnicze:

Przykładowe programy