Implementacja kolejki - I_R_W13A_M03_JAVA Zaawansowane struktury danych

R1KSK8bTfIKoK

Kolejka

Kolejka to liniowa struktura danych typu FIFO (ang. First‑In, First‑Out – pierwszy na wejściu, pierwszy na wyjściu), co oznacza, że jej elementy odczytywane są zgodnie z kolejnością dodawania, a zatem odwrotnie niż w przypadku stosu.

W implementacji kolejki również użyjemy listy jednokierunkowej oraz takiej samej jak w przypadku stosu definicji klasy Wezel. Natomiast klasa Kolejka będzie zawierała dwa pola:

glowa – referencję na pierwszy element kolejki;
ogon – referencję na ostatni element kolejki, który ułatwi dodawanie elementów na końcu listy.

Nazwy pozostałych metod dostosujemy do omawianej struktury.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }
}

class Kolejka {
Wezel glowa;
Wezel ogon;
    public Kolejka() {
        glowa = ogon = null;
    }
    
    // Miejsce na metody

}

Metoda czyPusta() działa tak samo, jak w przypadku stosu i każdej listy, tzn. jeżeli referencja na pierwszy element jest pusta, lista jest pusta.

public boolean czyPusta() {
	return (glowa == null);
}

Metoda dodaj() będzie dodawała nowe elementy na końcu listy przy użyciu pola ogon.

public void dodaj(int liczba) {
    Wezel nowy = new Wezel(liczba);
    nowy.nastepny = null;
    if (czyPusta()) {
        glowa = ogon = nowy;
        return;
    }
    
    ogon.nastepny = nowy;
    ogon = nowy;

}

Na początku metody tworzymy nowy węzeł, przypisujemy otrzymaną liczbę do jego pola liczba, a referencję nastepny ustawiamy na wartość pustą. Następnie, jeżeli lista jest pusta, referencje na pierwszy (glowa) i ostatni (ogon) element listy ustawiamy na nowy węzeł.

W przeciwnym razie referencję nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł i aktualizujemy referencję ogon, aby wskazywał nowo dodany element.

Metoda usun() będzie zwracała kolejne elementy z początku listy, czyli działać będzie tak samo, jak metoda zdejmij() w przypadku stosu. Ponieważ jednak elementy będą dodawane na końcu listy, zasada działania kolejki FIFO zostanie zachowana.

public int usun() {
    if (czyPusta()) return Integer.MIN_VALUE;
    Wezel pomocniczy = glowa;
    int liczba = pomocniczy.liczba;
    glowa = glowa.nastepny;
    System.out.println("Usuwam: " + Integer.toString(liczba));
    
    return liczba;

}

Ćwiczenie 1

Wykorzystaj omówiony kod i przygotuj program pozwalający sprawdzić działanie kolejki. Dodaj do kolejki trzy liczby, wypisz kolejkę, a następnie cztery raz wywołaj metodę usuwającą.

RJl1aILncO7Yk

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int liczba średnik. Linia 3. Wezel nastepny średnik. Linia 4. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny Wezel otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 5. this kropka liczba znak równości liczba średnik. Linia 6. this kropka nastepny znak równości null średnik. Linia 7. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 9. zamknij nawias klamrowy. Linia 11. class Kolejka otwórz nawias klamrowy. Linia 12. Wezel glowa średnik. Linia 13. Wezel ogon średnik. Linia 14. otwórz nawias ostrokątny code style znak równości cudzysłów white minus space dwukropek pre średnik cudzysłów data minus inline zamknij nawias ostrokątny public Kolejka otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. glowa znak równości ogon znak równości null średnik. Linia 16. zamknij nawias klamrowy. Linia 18. public boolean czyPusta otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. return otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły średnik. Linia 20. zamknij nawias klamrowy. Linia 22. public void dodaj otwórz nawias okrągły int liczba zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. System kropka out kropka println otwórz nawias okrągły cudzysłów Dodaje dwukropek cudzysłów plus String kropka valueOf otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 24. Wezel nowy znak równości new Wezel otwórz nawias okrągły liczba zamknij nawias okrągły średnik. Linia 25. nowy kropka nastepny znak równości null średnik. Linia 27. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. glowa znak równości ogon znak równości nowy średnik. Linia 29. return średnik. Linia 30. zamknij nawias klamrowy. Linia 32. ogon kropka nastepny znak równości nowy średnik. Linia 33. ogon znak równości nowy średnik. Linia 34. zamknij nawias klamrowy. Linia 36. public int usun otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. System kropka out kropka println otwórz nawias okrągły cudzysłów Kolejka jest pusta wykrzyknik cudzysłów zamknij nawias okrągły średnik. Linia 39. return Integer kropka MIN podkreślnik VALUE średnik. Linia 40. zamknij nawias klamrowy. Linia 41. Wezel pomocniczy znak równości glowa średnik. Linia 42. int liczba znak równości pomocniczy kropka liczba średnik. Linia 43. glowa znak równości glowa kropka nastepny średnik. Linia 44. System kropka out kropka println otwórz nawias okrągły cudzysłów Usuwam dwukropek cudzysłów plus Integer kropka toString otwórz nawias okrągły liczba zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 45. return liczba średnik. Linia 46. zamknij nawias klamrowy. Linia 48. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. if otwórz nawias okrągły czyPusta otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 50. System kropka out kropka println otwórz nawias okrągły cudzysłów Kolejka jest pusta wykrzyknik cudzysłów zamknij nawias okrągły średnik. Linia 51. return średnik. Linia 52. zamknij nawias klamrowy. Linia 54. System kropka out kropka print otwórz nawias okrągły cudzysłów Kolejka zawiera dwukropek cudzysłów zamknij nawias okrągły średnik. Linia 55. Wezel pomocniczy znak równości glowa średnik. Linia 56. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka liczba plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 58. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 59. zamknij nawias klamrowy. Linia 60. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 61. zamknij nawias klamrowy otwórz nawias ostrokątny prawy ukośnik code zamknij nawias ostrokątny. Linia 63. zamknij nawias klamrowy. Linia 65. public class KolejkaLista otwórz nawias klamrowy. Linia 66. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 67. Kolejka kolejka znak równości new Kolejka otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 68. kolejka kropka dodaj otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 69. kolejka kropka dodaj otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 70. kolejka kropka dodaj otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 71. kolejka kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 72. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 73. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 74. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 75. kolejka kropka usun otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 76. zamknij nawias klamrowy. Linia 77. zamknij nawias klamrowy.

class Wezel {
    int liczba;
    Wezel nastepny;
    Wezel(int liczba) {
        this.liczba = liczba;
        this.nastepny = null;
    }

}

class Kolejka {
Wezel glowa;
Wezel ogon;
    public Kolejka() {
        glowa = ogon = null;
    }
    
    public boolean czyPusta() {
        return (glowa == null);
    }
    
    public void dodaj(int liczba) {
        System.out.println("Dodaje: " + String.valueOf(liczba));
        Wezel nowy = new Wezel(liczba);
        nowy.nastepny = null;
    
        if (glowa == null) {
            glowa = ogon = nowy;
            return;
        }
    
        ogon.nastepny = nowy;
        ogon = nowy;
    }
    
    public int usun() {
        if (czyPusta()) {
            System.out.println("Kolejka jest pusta!");
            return Integer.MIN_VALUE;
        }
        Wezel pomocniczy = glowa;
        int liczba = pomocniczy.liczba;
        glowa = glowa.nastepny;
        System.out.println("Usuwam: " + Integer.toString(liczba));
        return liczba;
    }
    
    public void wypisz() {
        if (czyPusta()) {
            System.out.println("Kolejka jest pusta!");
            return;
        }
    
        System.out.print("Kolejka zawiera: ");
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.liczba + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }

}

public class KolejkaLista {
public static void main(String[] args) {
Kolejka kolejka = new Kolejka();
kolejka.dodaj(1);
kolejka.dodaj(2);
kolejka.dodaj(3);
kolejka.wypisz();
kolejka.usun();
kolejka.usun();
kolejka.usun();
kolejka.usun();
}
}

Wynik działania programu:

Dodaje: 1
Dodaje: 2
Dodaje: 3
Kolejka zawiera: 1 2 3 
Usuwam: 1
Usuwam: 2
Usuwam: 3
Kolejka jest pusta!

Implementacja stosu

Implementacja listy

Kolejka