Kolejka - implementacja tablicowa

Kolejka to struktura danych działająca w oparciu o zasadę FIFO (ang. First In First Out), pierwszy wchodzi, pierwszy wychodzi. Dostęp do kolejki jest możliwy z dwóch stron (początek i koniec). Podstawowe metody związane z kolejką to dodanie elementu do kolejki, na jej koniec (ang. enqueue), usunięcie elementu z kolejki, z jej początku (ang. dequeue), podgląd elementu znajdujacego się na początku (ang. peek). Dodatkowo w większości implementacji istnieje możliwość wyświetlenia zawartości kolejki jak i sprawdzenia czy kolejka jest pusta. Chcemy napisać w oparciu o tablicę prostą klasę Kolejka przechowującą liczby całkowite (dane typu int). Efektywne wykorzystanie tablicy jest możliwe poprzez zawijanie kolejki (dane trafiają na odpowiednie miejsce) . Uzyskanie odpowiednich indeksów w kolejce zawijanej osiągnięmy wykonując operacje modulo rozmiar tablicy dla zmiennych poczatek oraz koniec. Poniżej klasa wraz z przykładowym jej wykorzystaniem.

/**
 * Kolejka liczb całkowitych - implementacja tablicowa
 * @author kodatnik.blogspot.com
 */
public class Kolejka {
 // tablica przechowująca elementy kolejki
 private int[] wektor;
 // początek kolejki (indeks elementu znajdującego się na początku)
 private int poczatek;
 // koniec kolejki (indeks elementu znajdującego się na końcu)
 private int koniec;
 // liczba elementów kolejki (pole pomocnicze)
 private int rozmiarKolejki;
 
 // konstruktor domyślny (tworzy kolejkę 10 elementową)
 public Kolejka() {
  // wywołujemy konstruktor z parametrem int (czyli ten poniżej)
  this(10);
 }
                 
 // konstruktor jednoparametrowy
 public Kolejka(int rozmiar) {
  // tworzymy tablicę o rozmiarze przekazanym jako parametr wywołania
  wektor = new int[rozmiar];
  // ustawiamy początkowe wartości pól (można to pominąć, domyślnie pola będą miały wartość zero)
  poczatek = 0;
  koniec = 0;
  rozmiarKolejki = 0;
 }
 
 // metoda dodaje element do kolejki
 public void dodaj(int liczba) {
  // wpisujemy na koniec kolejki element 
  // (operacja modulo da nam odpowiedni indeks tablicy)
  wektor[koniec % wektor.length] = liczba;
  // zwiększamy indeks końca oraz rozmiar kolejki
  koniec++;
  rozmiarKolejki++;
 }
 
 // metoda usuwa element z kolejki
 public int usun() {
  // pobieramy element z początku kolejki
  // (operacja modulo da nam odpowiedni indeks tablicy)  
  int temp  = wektor[ poczatek % wektor.length];
  // zwiększamy indeks początku kolejki
  poczatek++;
  // zmniejszamy rozmiar kolejki
  rozmiarKolejki--;
  // zwracamy usunięty element
  return temp;
 } 

 // metoda sprawdza czy kolejka jest pusta
 public boolean czyPusta() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == 0);
 }

 // metoda sprawdza czy kolejka jest pełna
 public boolean czyPelna() {
  // zwracamy prawdę lub fałsz
  return (rozmiarKolejki == wektor.length);
 } 

 // metoda "podgląda" co jest na początku kolejki
 public int zobacz() {
  // zwracamy element z początku (nie modyfikujemy pozostałych zmiennych)
  return wektor[poczatek % wektor.length];
 } 

 // metoda zwraca rozmiar kolejki (liczbę elementów w kolejce) 
 public int rozmiar() {
  return rozmiarKolejki;
 } 
 
 // metoda wyświetla wszystkie elementy w kolejce 
 public void wyswietl(){
  // w pętli od początku do rozmiaru kolejki
  // (również wykorzystujemy modulo)
  for (int i = poczatek % wektor.length; i < poczatek % wektor.length + rozmiarKolejki; i++) 
   // wyświetlamy poszczególne elementy
   System.out.print (wektor[ i % wektor.length] + " ");
  System.out.println ();
 }
}

/**
 * Test kolejki liczb całkowitych
 * @author kodatnik.blogspot.com
 */
public class TestKolejki {

 public static void main(String args[]) {
    
  // zakładamy nową kolejkę o rozmiarze 20
  Kolejka k = new Kolejka(20);
     
  // dodajemy elementy do kolejki
  k.dodaj(12);
  k.dodaj(8);
  k.dodaj(39);
     
  // wyświetlamy zawartość kolejki
  k.wyswietl();
 
  // wyświetlamy element znajdujący się na początku (bez jego usuwania)
  System.out.println(k.zobacz());
     
  // usuwamy element z kolejki
  k.usun();     
      
  // wyświetlamy zawartość kolejki
  k.wyswietl();     
 }
}

Uruchomiona aplikacja:

12 8 39 
12
8 39

Przedstawiona kolejka jest statyczna, jej rozmiar ustalamy podczas tworzenia obiektu (nie mamy możliwości jego zmiany w trakcie działania). Przechowujemy dane tylko jednego typu (int), co w większości zastosowań może okazać się niewystarczające. Lepszym rozwiązaniem jest zastosowanie do implementacji kolejki list powiązanych (struktura dynamiczna) oraz wykorzystanie typów generycznych (możliwość tworzenia kolejek przechowujących dowolny typ danych).