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).
Kolejki wykorzystywane są w algorytmice, w programach komputerowych (np. kolejka plików w Winampie), systemach operacyjnych (np. kolejka wydruku).


0 Komentarzy - Kolejka - implementacja tablicowa

Prześlij komentarz

Możesz użyć niektórych tagów HTML, takich jak <b>, <i>, <u>, <a> Nie spamuj :)

Popularne posty