Programowanie i algorytmy

Kolejka fifo

powrót

Kolejka fifo to abstrakcyjna struktura danych, która jest wykorzystywana w wielu algorytmach, między innymi w algorytmie grafowym (BFS) - przeszukiwanie wszerz. Skrót fifo oznacza first in first out - pierwszy na wejściu jest pierwszym na wyjściu. Strukturę danych możemy porównać do zwykłej kolejki w sklepie. Osoba, która jako pierwsza ustała w kolejce, będzie obsłużona jako pierwsza. Każda następna, która dołączyła do kolejki, będzie obsługiwana jako następna. Nowa osoba zawsze staje na końcu kolejki i będzie obsłużona jako ostatnia.

kolejka fifo

W omawianej strukturze możemy wyróżnić następujące czynności:

  • push_back(element) - dodanie elementu na koniec kolejki
  • pop_back() - usunięcie "obsłużenie" elementu z początku kolejki
  • size() - liczba elementów w kolejce
  • first() - wartość pierwszego elementu w kolejce
  • last() - wartość ostatniego elementu w kolejce

Pierwsza implementacja tej struktury będzie najprostszą z możliwych. Napiszemy ją z wykorzystaniem tablicy statycznej. Ustawimy sobie dwa liczniki, {tex}p{/tex} i {tex}k{/tex} (początek i koniec kolejki). Dodając element do kolejki przesuniemy licznik {tex}k{/tex} o jeden w prawo, usuwając element przesuniemy licznik {tex}p{/tex} o jeden w prawo. W rezultacie elementy z komórki tablicy nie będą usuwane tylko licznik będzie przesuwany na następny index komórki.

Zalety:

  • prostota implementacji
  • szybkość działania

Wady:

  • ograniczenia co do wielkości kolejki - z góry musimy znać jej rozmiar
  • elementy nie są fizycznie usuwane z pamięci

Statyczna implementacja kolejki:

#include<iostream>
#include<cstdlib>
//maksymalna liczba wszystkich elementów w kolejce - usuniętych lub nie
#define MAX 1000 
#define ERROR 1000000000 //ustalamy taką wartość, która nie wystąpi jako element fifo
using namespace std;
 
int tab[MAX], p = 0, k = 0;
 
inline bool pop_back() //usunięcie elementu
{
  if(p==k) //jesli kolejka jest pusta
    return 0;
 
  ++p;
  return 1;
}
 
inline bool push_back(int element)
{
  if(k==MAX) //jesli nie ma już miejsca w tablicy
    return 0;
 
  tab[k++] = element;
  return 1;
}
 
inline unsigned int size()
{
  return k-p; //liczba elementów w kolejce
}
 
inline int first()
{
  if(p==k) //jesli kolejka jest pusta
    return ERROR;
 
  return tab[p];
}
 
inline int last()
{
  if(p==k) //jesli kolejka jest pusta
    return ERROR;
 
  return tab[k-1];
}
int main()
{
  if(!push_back(12))cout<<"Kolejka przepełniona\n";
  if(!push_back(22))cout<<"Kolejka przepełniona\n";
  if(!push_back(32))cout<<"Kolejka przepełniona\n";
 
  int pom = first();
  if(pom!=ERROR) cout<<"Pierwszy element w kolejce: "<<pom<<endl;
 
  pom = last();
  if(pom!=ERROR) cout<<"Ostatni element w kolejce: "<<pom<<endl;
 
  cout<<"Liczba elementów w kolejce: "<<size()<<endl;
 
  if(!pop_back()) cout<<"Kolejka jest już pusta\n";
  if(!pop_back()) cout<<"Kolejka jest już pusta\n";
 
  cout<<"Liczba elementów w kolejce: "<<size()<<endl;
 
  if(!pop_back()) cout<<"Kolejka jest już pusta\n";
  if(!pop_back()) cout<<"Kolejka jest już pusta\n";
 
  system("pause");
  return 0;
}

 

Out:

Pierwszy element w kolejce: 12
Ostatni element w kolejce: 32
Liczba elementów w kolejce: 3
Liczba elementów w kolejce: 1
Kolejka jest już pusta
Aby kontynuować, naciśnij dowolny klawisz . . . 

 

Dynamiczna implementacja kolejki fifo wykorzystuje listę jednokierunkową. Usunięcie elementu z kolejki powoduje fizyczne usunięcie elementu z pamięci. Pamięć na następny element jest przydzielana dynamicznie.

Zalety:

  • nie trzeba znać długości kolejki, jest ona tworzona w miarę potrzeb
  • niewykorzystane elementy są usuwane na bieżąco
  • prostota implementacji

Wady:

  • nieco wolniejsze działanie od statycznego odpowiednika

Program zaimplementowany obiektowo: 

//wwww.algorytm.edu.pl
#include<iostream>
#include<cstdlib>
using namespace std;
 
class kolejka{
  public:
    kolejka(){poczatek=koniec=0;f=1;}
    ~kolejka() //zwolnienie pamięci dla elementów kolejki
    {
      while(koniec-poczatek>0){
        el = p;
        p = p->nastepny;
        delete el;
        ++poczatek;  
      } 
      if(!f)
        delete p;
    }
    unsigned int size(){return koniec-poczatek;}//liczba elementów w kolejce
    void push_back(int x)//dodanie elementu na koniec kolejki
    {
      if(f)//jesli pierwszy element wrzucamy do kolejki
      {
        k = new wezel;    //utworzenie elementu ostatniego
        k -> element = x; //przypisanie do niego wartosci
        p = new wezel;     //utworzenei elemntu pierwszego
        p -> nastepny = k;  //element pierwszy wskazuje na ostatni
        f = 0;
      }
      else
      {
        el = new wezel;    //utworzenie nowego elementu kolejki
        el -> element = x;  //przypisanie do niego wartosci
        k -> nastepny = el;  //ostatni dotychczas element wskazuje na utworzony
        k = el;        //element utworzony staje się ostatnim
      }
      ++koniec;
    }
    int pop_back()// usunięcie pierwszego elementu z kolejki i zwrócenie 1 gdy ok, 0 - gdy nie ma nic do usunięcia
    {
      if(koniec-poczatek==0)return 0; //gdy nie ma nic w kolejce zwracamy 0
      el = p;
      p = p->nastepny; //przejscie na następny element kolejki
      delete el;    //usunięcie pierwszego elementu w kolejce
      ++poczatek;
      return 1;
    }
    int first() //zwrócenie pierwszego elementu w kolejce
    {
      return p->nastepny->element;
    }
    int last() //wyznaczenie ostatniego elementu w kolejce
    {
      return k->element;
    }
  private:
    bool f; //flaga okreslająca, czy w kolejce cos już się pojawiło
    struct wezel{
      int element;
      wezel *nastepny;
    };
    unsigned int poczatek, koniec; //początek i koniec kolejki - index
    wezel *p,*k,*el; //poczatek, koniec, 
};
 
int main()
{
  kolejka queue; //utworzenie kolejki
 
  queue.push_back(23); //dodaj do kolejki 23
  queue.push_back(43); //dodaj do kolejki 43
  queue.push_back(45); //dodaj do kolejki 45
  cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //mamy 3 elementy
  cout<<"Pierwszy element kolejce: "<<queue.first()<<endl; //wypisanie 23
  cout<<"Ostatni element kolejce: "<<queue.last()<<endl;   //wypisanie 45
  queue.pop_back(); //usunięcie 23
  queue.pop_back(); //usunięcie 43
  cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //mamy 1 element
  queue.pop_back(); //usunięcie 45
  cout<<"Liczba elementów w kolejce: "<<queue.size()<<endl; //0 elementów w kolejce
  if(!queue.pop_back())
    cout<<"Kolejka jest pusta, nie ma nic do usuwania"<<endl;
 
  system("pause");
  return 0;
}
 

 

Out:

Liczba elementów w kolejce: 3
Pierwszy element kolejce: 23
Ostatni element kolejce: 45
Liczba elementów w kolejce: 1
Liczba elementów w kolejce: 0
Kolejka jest pusta, nie ma nic do usuwania
Aby kontynuować, naciśnij dowolny klawisz . . .
 

 

Omawiając daną strukturę danych nie można pominąć kolejkę zaimplementowaną w STL-u. Użycie tej struktury jest bardzo przyjemne oraz wydajne. Kolejkę queue omówiono tutaj.