Najprostsze dynamiczne struktury danych, jakie poznaliśmy, to stos i kolejka. Obydwie implementować można za pomocą różnych mechanizmów. Jednym z najprostszych rozwiązań, które służy zazwyczaj do wyjaśnienia działania tych struktur, jest użycie statycznej lub dynamicznej tablicy. Jednak nie jest to rozwiązanie w pełni dynamiczne, ponieważ użycie tablic wymaga podania maksymalnej liczby przechowywanych w strukturze elementów. Aby uzyskać w pełni dynamiczne struktury stosu i kolejki, wykorzystuje się listy.

Stos

Przypomnijmy, że stos to liniowa struktura typu LIFO (ang. Last‑In, First‑Out – ostatni na wejściu, pierwszy na wyjściu), która obsługuje dwie podstawowe operacje, tj. dodawanie i usuwanie danych. Dodatkowe działania, jakie wykonuje się na stosie, to odczytywanie wierzchołka stosu, czyli ostatniego odłożonego elementu, bez usuwania go, oraz ewentualnie sprawdzanie rozmiaru stosu, czyli liczby odłożonych elementów.

Biorąc pod uwagę powyższe warunki, do implementacji stosu wystarczy jednokierunkowa lista niecykliczna. Elementami tej listy będą węzły zawierające dane, np. liczby, oraz – w przypadku listy jednokierunkowej – wskaźnikwskaźnikwskaźnik na element następny. Do zdefiniowania węzła możemy użyć strukturystrukturastruktury zawierającej dwa pola:

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
} Wezel;

Stworzenie nowego węzła i przypisanie wartości do jego składowych umożliwiają instrukcje:

Wezel *wezel = new Wezel;
wezel->liczba = 1;
wezel->nastepny = nullptr;

Stos zaimplementujemy jako klasę, której atrybutem będzie wskaźnik na wierzchołek stosu o nazwie wierzcholek. Klasa będzie zawierała również definicje konstruktora oraz metod wykonujących charakterystyczne dla stosu operacje.

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
} Wezel;

class Stos {
    Wezel *wierzcholek;
public:
    Stos(): wierzcholek(nullptr) {}
    bool czyPusty();
    void odloz(int);
    int zdejmij();
    int pobierzWierzcholek();
    void wypisz();
};

W konstruktorze Stos(): wierzcholek(nullptr) {} inicjalizujemy pole wierzcholek pustym wskaźnikiemwskaźnikpustym wskaźnikiem.

Metoda czyPusty() będzie zwracała wartość true (prawda), jeżeli stos będzie pusty, czyli w sytuacji, gdy pole wierzcholek będzie pustym wskaźnikiem. W przeciwnym razie metoda zwróci wartość false (fałsz).

bool Stos::czyPusty() {
    if (!wierzcholek) {
        cout << "Stos pusty!" << endl;
    }
    return !wierzcholek;
}

W celu zachowania poprawności działania struktury LIFO, funkcja odloz() będzie dodawała elementy na początku listy, a funkcja zdejmij() będzie usuwała elementy również z początku listy.

Zacznijmy od metody odloz():

void Stos::odloz(int liczba) {
    cout << "Odkładam: " << liczba << endl;
    Wezel *nowy = new Wezel;
    nowy->liczba = liczba;
    nowy->nastepny = wierzcholek;
    wierzcholek = nowy;
}

W funkcji odloz() tworzymy nowy węzeł i zapisujemy w nim wartość zmiennej liczba przekazaną jako argument. Kluczowymi operacjami są nadal przypisanie do wskaźnika nastepny nowego elementu wierzchołka oraz ustawienie wierzchołka na nowo dodany element.

Usuwanie pierwszego elementu jest możliwe dzięki wskaźnikowi wierzcholek:

int Stos::zdejmij() {
    if (czyPusty()) return INT_MIN;

    Wezel *pomocniczy = wierzcholek;
    int liczba = pomocniczy->liczba;
    wierzcholek = wierzcholek->nastepny;
    delete(pomocniczy);
    cout << "Zdejmuję: " << liczba << endl;
    return liczba;
}

Jeżeli stos jest pusty, tzn. zachodzi błąd niedopełnienia stosuniedopełnienie stosuniedopełnienia stosu, zwracamy minimalną wartość zdefiniowaną dla typu całkowitego w stałej INT_MIN.

W przeciwnym razie dotychczasowy pierwszy element oraz zapisaną w nim wartość zapamiętujemy w zmiennych pomocniczych. Następnie ustawiamy wierzchołek na drugi element listy, dotychczasowy pierwszy usuwamy, a zapamiętaną wartość zwracamy.

Metoda pobierzWierzcholek() ma tylko jedno zadanie: jeżeli stos nie jest pusty, zwraca wartość zapisaną w pierwszym (czyli ostatnim dodanym) elemencie listy:

int Stos::pobierzWierzcholek() {
    if (czyPusty()) return INT_MIN;
    return wierzcholek->liczba;
}

Metoda wypisz() posłuży do wypisania wartości odłożonych na stos, czyli zapisanych w kolejnych węzłach listy:

void Stos::wypisz() {
    if (czyPusty()) return;

    cout << "Stos zawiera: ";
    Wezel *pomocniczy = wierzcholek;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->liczba << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

Do wypisania wartości używamy pętli przechodzącej po wszystkich elementach stosu zapisywanych w zmiennej pomocniczy. Wskaźnik ten inicjalizujemy wierzchołkiem, a następnie wewnątrz pętli przesuwamy na kolejne węzły wskazywane przez pole nastepny. Pętla będzie działać, dopóki nie dojdziemy do ostatniego węzła, którego wskaźnik nastepny będzie pusty.

Do sprawdzenia działania stosu możemy użyć poniższego kodu:

int main() {
    Stos stos = Stos();
    stos.odloz(1);
    stos.odloz(2);
    stos.odloz(3);
    stos.wypisz();
    stos.zdejmij();
    stos.zdejmij();
    stos.zdejmij();
    stos.zdejmij();
    return 0;
}

#include <iostream>
#include <limits.h>

using namespace std;

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
} Wezel;

class Stos {
    Wezel* wierzcholek;
public:
    Stos(): wierzcholek(nullptr) {}
    bool czyPusty();
    void odloz(int);
    int zdejmij();
    int pobierzWierzcholek();
    void wypisz();
};

bool Stos::czyPusty() {
    if (!wierzcholek) {
        cout << "Stos pusty!" << endl;
    }
    return !wierzcholek;
}

void Stos::odloz(int liczba) {
    cout << "Odkładam: " << liczba << endl;
    Wezel *nowy = new Wezel;
    nowy->liczba = liczba;
    nowy->nastepny = wierzcholek;
    wierzcholek = nowy;
}

int Stos::zdejmij() {
    if (czyPusty()) return INT_MIN;

    Wezel *pomocniczy = wierzcholek;
    int liczba = pomocniczy->liczba;
    wierzcholek = wierzcholek->nastepny;
    delete(pomocniczy);
    cout << "Zdejmuję: " << liczba << endl;
    return liczba;
}

int Stos::pobierzWierzcholek() {
    if (czyPusty()) return INT_MIN;
    return wierzcholek->liczba;
}

void Stos::wypisz() {
    if (czyPusty()) return;

    cout << "Stos zawiera: ";
    Wezel *pomocniczy = wierzcholek;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->liczba << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
    Stos stos = Stos();
    stos.odloz(1);
    stos.odloz(2);
    stos.odloz(3);
    stos.wypisz();
    stos.zdejmij();
    stos.zdejmij();
    stos.zdejmij();
    stos.zdejmij();
    return 0;
}

Odkładam: 1
Odkładam: 2
Odkładam: 3
Stos zawiera: 3 2 1
Zdejmuję: 3
Zdejmuję: 2
Zdejmuję: 1
Stos pusty!

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 i takiej samej jak w przypadku stosu struktury węzłów. Natomiast klasa Kolejka będzie zawierała dwa pola:

• glowa – wskaźnik na pierwszy element kolejki;

• ogon – wskaźnik na ostatni element kolejki, który ułatwi dodawanie elementów na końcu listy.

Nazwy pozostałych metod dostosujemy do omawianej struktury.

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
} Wezel;

class Kolejka {
    Wezel *glowa;
    Wezel *ogon;
public:
    Kolejka(): glowa(nullptr), ogon(nullptr) {}
    bool czyPusta();
    void dodaj(int);
    int usun();
    void wypisz();
};

Metoda czyPusta() działa tak samo, jak w przypadku stosu i każdej listy, tzn. jeżeli wskaźnik na pierwszy element jest pusty, to znaczy, że lista jest pusta.

bool Kolejka::czyPusta() {
    return !glowa;
}

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

void Kolejka::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    Wezel *nowy = new Wezel;
    nowy->liczba = liczba;
    nowy->nastepny = nullptr;

    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 wskaźnik nastepny ustawiamy na wartość pustą. Następnie, jeżeli lista jest pusta, wskaźniki na pierwszy (glowa) i ostatni (ogon) element listy ustawiamy na nowy węzeł.

W przeciwnym razie wskaźnik nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł i aktualizujemy wskaźnik 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.

int Kolejka::usun() {
    if (czyPusta()) return INT_MIN;

    Wezel* pomocniczy = glowa;
    int liczba = pomocniczy->liczba;
    glowa = glowa->nastepny;
    delete(pomocniczy);
    cout << "Usuwam: " << liczba << endl;
    return liczba;
}

#include <iostream>
#include <limits.h>

using namespace std;

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
} Wezel;

class Kolejka {
    Wezel* glowa;
    Wezel* ogon;
public:
    Kolejka(): glowa(nullptr), ogon(nullptr) {}
    bool czyPusta();
    void dodaj(int);
    int usun();
    void wypisz();
};

bool Kolejka::czyPusta() {
    return !glowa;
}

void Kolejka::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    Wezel* nowy = new Wezel;
    nowy->liczba = liczba;
    nowy->nastepny = nullptr;

    if (czyPusta()) {
        glowa = ogon = nowy;
        return;
    }

    ogon->nastepny = nowy;
    ogon = nowy;
}

int Kolejka::usun() {
    if (czyPusta()) {
        cout << "Kolejka jest pusta!" << endl;
        return INT_MIN;
    }

    Wezel* pomocniczy = glowa;
    int liczba = pomocniczy->liczba;
    glowa = glowa->nastepny;
    delete pomocniczy;
    cout << "Usuwam: " << liczba << endl;
    return liczba;
}

void Kolejka::wypisz() {
    if (czyPusta()) {
        cout << "Kolejka jest pusta!" << endl;
        return;
    }

    cout << "Kolejka zawiera: ";
    Wezel* pomocniczy = glowa;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->liczba << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
    Kolejka kolejka = Kolejka();
    kolejka.dodaj(1);
    kolejka.dodaj(2);
    kolejka.dodaj(3);
    kolejka.wypisz();
    kolejka.usun();
    kolejka.usun();
    kolejka.usun();
    kolejka.usun();
    return 0;
}

Dodaję: 1
Dodaję: 2
Dodaję: 3
Kolejka zawiera: 1 2 3 
Usuwam: 1
Usuwam: 2
Usuwam: 3
Kolejka jest pusta!

Lista

Lista – podobnie jak stos i kolejka – jest liniową i dynamiczną strukturą danych. Elementami listy są węzły, z których każdy zawiera dane oraz wskaźnikwskaźnikwskaźnik na element następny (w przypadku listy jednokierunkowej) lub na następny i poprzedni (w przypadku listy dwukierunkowej).

Do implementacji stosu i kolejki użyliśmy listy jednokierunkowej. Jej węzły zdefiniowaliśmy przy użyciu strukturystrukturastruktury zawierającej dwa pola.

Definicja struktury może dodatkowo obejmować konstruktorkonstruktorkonstruktor inicjalizujący jej składowe, np.:

typedef struct Wezel {
    int liczba;
    Wezel *nastepny;
    Wezel(int liczba) {
        this->liczba = liczba;
        this->nastepny = nullptr;
    }
} Wezel;

Wtedy utworzenie nowego węzła jest możliwe dzięki zwięzłej instrukcji:

Wezel *nowy = new Wezel(1);

Podobne możliwości definiowania węzła daje użycie klasyklasaklasy:

class Wezel {
public:
    int liczba;
    Wezel *nastepny;

    // Konstruktor domyślny
    Wezel(): liczba(0), nastepny(nullptr) {}

    // Konstruktor argumentowy
    Wezel(int liczba) {
        this->liczba = liczba;
        this->nastepny = nullptr;
    }
};

Pierwszy konstruktor – domyślny – nie wymaga żadnych argumentów i służy do inicjalizowania składowych wartościami domyślnymi podawanymi po dwukropku. Drugi konstruktor wymaga argumentu i pozwala na zainicjowanie pola liczba wartością podaną podczas tworzenia węzła. Oto przykłady:

// Wykorzystanie konstruktora domyślnego
Wezel *wezel = new Wezel();

// Wykorzystanie konstruktora argumentowego
Wezel *wezel = new Wezel(1);

Lista jednokierunkowa

Listę jednokierunkową implementujemy jako klasęklasaklasę z jednym polem glowa – wskaźnikiem na pierwszy element listy. Oprócz tego w klasie definiujemy metody umożliwiające dodawanie, usuwanie i wypisywanie elementów listy. W konstruktorze Lista() inicjalizujemy pole glowa pustym wskaźnikiemwskaźnikpustym wskaźnikiem.

class Lista {
    Wezel *glowa;

public:
    Lista(): glowa(nullptr) {}
    bool czyPusta();
    void dodaj(int);
    void usun(int);
    void wypisz();
};

Metody czyPusta() oraz wypisz() działają tak samo jak w przypadku stosu i kolejki. Wyjaśnijmy teraz działanie metod: dodającej węzły na końcu listy oraz usuwającej węzły o podanej pozycji.

Dodawanie węzłów na końcu listy jednokierunkowej

Metoda dodaj() jako argument będzie przyjmowała liczbę całkowitą. Nowy węzeł – inaczej niż w przypadku stosu i kolejki – będzie dodawany na końcu listy.

void Lista::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    // Tworzymy nowy węzeł
    Wezel *nowy = new Wezel(liczba);

    // Jeżeli lista jest pusta
    if (czyPusta()) {
        glowa = nowy;
        return;
    }

    // W przeciwnym razie przejdź do ostatniego elementu
    Wezel *pomocniczy = glowa;
    while (pomocniczy->nastepny != nullptr) {
        pomocniczy = pomocniczy->nastepny;
    }

    // Dodajemy nowy węzeł na końcu listy
    pomocniczy->nastepny = nowy;
}

Na początku metody tworzymy nowy węzeł, przekazując do jego konstruktora otrzymaną liczbę.

Następnie, jeżeli lista jest pusta, nowy węzeł staje się pierwszym elementem listy przypisanym do pola glowa.

W przeciwnym razie za pomocą węzła pomocniczy w pętli przechodzimy listę do ostatniego elementu, którego wskaźnik nastepny będzie pusty. Po zakończeniu pętli wskaźnik nastepny dotychczasowego ostatniego elementu ustawiamy na nowy węzeł. W ten sposób dodajemy węzeł na końcu listy.

R1eSTXiWk4HIn

Ilustracja przedstawia schemat dodawania węzła do końca listy jednokierunkowej. Lista składa się z czterech elementów, gdzie element pierwszy jest głową, trzeci jest pomocniczy, a czwarty jest elementem nowym. Elementy połączone są strzałkami z podpisem następny. Przy czym element NULL znajdujący się po elemencie trzecim został skreślony, a nowy element NULL jest następny po nowym elemencie czwartym.

Usuwanie węzłów z listy jednokierunkowej

Metoda usuwająca węzły z listy otrzymywać będzie jako argument liczbę całkowitą wskazującą indeks czy też numer węzła, który chcemy usunąć. Przyjmijmy, że indeksy węzłów zaczynają się od 1.

void Lista::usun(int indeks) {
    if (czyPusta()) return;
    
    cout << "Usuwam pozycję: " << indeks << endl;

    Wezel *pomocniczy1 = glowa, *pomocniczy2 = nullptr;
    int rozmiar = 0;

    // Zliczamy elementy listy
    while (pomocniczy1 != nullptr) {
        pomocniczy1 = pomocniczy1->nastepny;
        rozmiar++;
    }

    // Jeżeli indeks jest większy od rozmiaru listy
    if (indeks > rozmiar) {
        cout << "Indeks poza zakresem" << endl;
        return;
    }

    // Poniżej dodamy kod usuwający elementy

}

Jeżeli lista nie jest pusta, definiujemy zmienne, których używamy w metodzie:

• wskaźnik pomocniczy1 ustawiamy na pierwszy element listy;

• wskaźnik pomocniczy2 wykorzystamy przy usuwaniu węzłów innych od pierwszego;

• zmienna rozmiar posłuży do ustalenia rozmiaru listy.

Następnie zliczamy elementy listy za pomocą pętli while przechodzącej po wszystkich węzłach listy, zaczynając od pierwszego. Po dojściu do ostatniego elementu w zmiennej pomocniczy1 zostanie zapisana wartość nullptr i pętla zakończy swoje działanie.

Następnie, jeżeli podany indeks nie jest większy od obliczonego rozmiaru listy, zaczynamy usuwanie węzła. Zadanie to realizuje kod, który umieszczamy na końcu omawianej metody:

    // Usuwanie pierwszego węzła
    pomocniczy1 = glowa;
    if (indeks == 1) {
        glowa = glowa->nastepny;
        delete pomocniczy1;
        return;
    }

    // Szukanie węzła do usunięcia (innego niż pierwszy)
    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1->nastepny;
    }

    // Zmiana wskaźnika nastepny węzła poprzedzającego usuwany
    pomocniczy2->nastepny = pomocniczy1->nastepny;

    // Usunięcie węzła o podanym indeksie
    delete pomocniczy1;

Jeżeli usuwanym elementem jest pierwszy węzeł (indeks 1), zapamiętujemy go w zmiennej pomocniczy1, wskaźnik glowa ustawiamy na następny węzeł i usuwamy zapamiętany węzeł.

W przeciwnym razie w pętli, która wykonuje się, dopóki indeks jest większy od 1, szukamy węzła do usunięcia. Po każdej iteracji indeks jest zmniejszany o 1 dzięki notacji postfiksowej. Wewnątrz pętli przechodzimy po indeks - 1 elementach listy od jej początku, więc po jej zakończeniu zmienna pomocniczy1 będzie wskazywała węzeł do usunięcia, a zmienna pomocniczy2 węzeł poprzedni.

Po zakończeniu pętli w węźle poprzedzającym węzeł usuwany ustawiamy wskaźnik nastepny na węzeł następny po węźle usuwanym (w przypadku usuwania ostatniego węzła będzie to wartość nullptr).

Na koniec usuwamy węzeł zapamiętany w zmiennej pomocniczy1.

R1DT71fUbiSfA

Ilustracja przedstawia schemat usuwania węzła z listy jednokierunkowej. Lista składa się z czterech elementów, gdzie element pierwszy jest głową, drugi jest elementem pomocniczym dwa a trzeci jest elementem pomocniczym jeden. Element trzeci został przekreślony, wraz ze strzałką pomiędzy elementami pomocniczymi. Z  elementu drugiego prowadzi nowa strzałka prosto do elementu czwartego.

#include <iostream>

using namespace std;

typedef struct Wezel {
    int liczba;
    Wezel* nastepny;
    Wezel(int liczba) {
        this->liczba = liczba;
        this->nastepny = nullptr;
    }
} Wezel;

class Lista {
    Wezel *glowa;

public:
    Lista(): glowa(nullptr) {}
    bool czyPusta();
    void dodaj(int);
    void usun(int);
    void wypisz();
};

bool Lista::czyPusta() {
    if (glowa == nullptr) {
        cout << "Lista jest pusta!" << endl;
        return true;
    }
    return false;
}

void Lista::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    Wezel *nowy = new Wezel(liczba);

    if (czyPusta()) {
        glowa = nowy;
        return;
    }

    Wezel *pomocniczy = glowa;
    while (pomocniczy->nastepny != nullptr) {
        pomocniczy = pomocniczy->nastepny;
    }

    pomocniczy->nastepny = nowy;
}

void Lista::usun(int indeks) {
    if (czyPusta()) return;
    
    cout << "Usuwam pozycję: " << indeks << endl;

    Wezel *pomocniczy1 = glowa, *pomocniczy2 = nullptr;
    int rozmiar = 0;

    while (pomocniczy1 != nullptr) {
        pomocniczy1 = pomocniczy1->nastepny;
        rozmiar++;
    }

    if (indeks > rozmiar) {
        cout << "Indeks poza zakresem" << endl;
        return;
    }

    pomocniczy1 = glowa;
    if (indeks == 1) {
        glowa = glowa->nastepny;
        delete pomocniczy1;
        return;
    }

    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1->nastepny;
    }

    pomocniczy2->nastepny = pomocniczy1->nastepny;
    delete pomocniczy1;

}

void Lista::wypisz() {
    if (czyPusta()) return;

    cout << "Lista zawiera: ";
    Wezel* pomocniczy = glowa;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->liczba << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main() {
    Lista lista;

    lista.dodaj(1);
    lista.dodaj(2);
    lista.dodaj(3);
    lista.wypisz();

    lista.usun(2);
    lista.wypisz();

    lista.usun(2);
    lista.dodaj(4);
    lista.wypisz();

    return 0;
}

Dodaję: 1
Lista jest pusta!
Dodaję: 2
Dodaję: 3
Lista zawiera: 1 2 3 
Usuwam pozycję: 2
Lista zawiera: 1 3 
Usuwam pozycję: 2
Dodaję: 4
Lista zawiera: 1 4

Lista dwukierunkowa

Lista dwukierunkowa od jednokierunkowej różni się tym, że jej węzły oprócz wskaźnika na element następny zawierają także wskaźnik na element poprzedni. Implementację przygotujemy, wykorzystując omówiony wyżej kod listy jednokierunkowej.

Na początku uzupełniamy strukturę Wezel o pole poprzedni oraz uzupełniamy konstruktor tak, aby inicjalizował je wartością pustą. Do klasy Lista dodajemy pole ogon, które będzie wskazywało na ostatni element listy. W konstruktorze klasy pola glowa i ogon ustawiamy na wartości puste.

typedef struct Wezel {
    int liczba;
    Wezel* nastepny;
    Wezel* poprzedni;
    Wezel(int liczba) {
        this->liczba = liczba;
        this->nastepny = nullptr;
        this->poprzedni = nullptr;
    }
} Wezel;

class Lista {
    Wezel *glowa;
    Wezel *ogon;

public:
    Lista(): glowa(nullptr), ogon(nullptr) {}
    ...
}

Dodawanie węzłów na końcu listy dwukierunkowej

Deklaracje metod obsługujących listę pozostają bez zmian. Modyfikacji wymagają tylko implementacje metod dodaj() i usun(). Zacznijmy od metody dodającej nowe węzły:

void Lista::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    Wezel *nowy = new Wezel(liczba);

    // Jeżeli lista jest pusta
    if (czyPusta()) {
        glowa = ogon = nowy;
        return;
    }

    // Dodanie nowego węzła na końcu listy
    ogon->nastepny = nowy;
    nowy->poprzedni = ogon;
    ogon = nowy;
}

W komentarzach zaznaczyliśmy różnice w porównaniu do implementacji tej metody użytej w przypadku listy jednokierunkowej. Obejmują one:

• ustawienia pola ogon na nowy węzeł w przypadku dodawania pierwszego elementu listy;

• wykorzystanie pola ogon – zamiast pętli przechodzącej wszystkie elementy listy – do wskazania ostatniego węzła listy;

• ustawienie wskaźników nastepny dotychczasowego ostatniego węzła na nowy oraz poprzedni nowego węzła na dotychczasowy ostatni;

• ustawienie pola ogon na nowo dodany element.

RlhFi1x6RJLwH

Ilustracja przedstawia schemat dodawania węzła do końca listy dwukierunkowej. Lista składa się z czterech elementów. Pomiędzy elementami są po dwie strzałki, gdyż każdy z nich jest jednocześnie elementem następnym oraz poprzednim. Pierwszy z elementów to głowa. Trzeci element początkowo był ogonem, jednak po dodaniu węzła to nowy element czwarty jest podpisany jako ogon.

Usuwanie węzłów z listy dwukierunkowej

Metoda usuwająca elementy z podanej pozycji nie wymaga zmian, lecz uzupełnienia. Jeżeli usuwamy element niebędący ani pierwszym, ani ostatnim, musimy odpowiednio ustawić wskaźnik poprzedni węzła występującego po węźle usuwanym. W przeciwnym razie, jeżeli usuwamy ostatni element, musimy zaktualizować pole ogon, aby wskazywało na dotychczasowy węzeł przedostatni. Poniżej znajduje się kod uzupełnionej metody usun(). W komentarzu zaznaczono instrukcję warunkową realizującą omówione operacje.

void Lista::usun(int indeks) {
    if (czyPusta()) return;

    cout << "Usuwam pozycję: " << indeks << endl;

    Wezel *pomocniczy1 = glowa, *pomocniczy2 = nullptr;;
    int rozmiar = 0;

    while (pomocniczy1 != nullptr) {
        pomocniczy1 = pomocniczy1->nastepny;
        rozmiar++;
    }

    if (indeks > rozmiar) {
        cout << "Indeks poza zakresem." << endl;
        return;
    }

    pomocniczy1 = glowa;
    if (indeks == 1) {
        glowa = glowa->nastepny;
        delete pomocniczy1;
        return;
    }

    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1->nastepny;
    }

    // Zmiana wskaźnika nastepny węzła poprzedzającego usuwany
    pomocniczy2->nastepny = pomocniczy1->nastepny;

    // Kod obsługujący listę dwukierunkową
    if (pomocniczy1->nastepny != nullptr) {
        // Jeżeli usuwany węzeł nie jest ostatni
        pomocniczy1->nastepny->poprzedni = pomocniczy2;
    } else {
        // Jeżeli usuwany element jest ostatni
        ogon = pomocniczy2;
    }

    // Usunięcie węzła o podanym indeksie
    delete pomocniczy1;
}

R50oTO05RitRz

Ilustracja przedstawia schemat usuwania węzła z listy dwukierunkowej. Lista składa się z czterech elementów. Pomiędzy elementami są po dwie strzałki, gdyż każdy z nich jest jednocześnie elementem następnym oraz poprzednim. Pierwszy z elementów to głowa. Element drugi to element pomocniczy dwa. Element trzeci to element pomocniczy jeden. Element czwarty to ogon. Element trzeci został przekreślony wraz ze strzałkami łączącymi go z drugim oraz czwartym elementem. Pomiędzy drugim i czwartym elementem dodane zostały nowe strzałki.

#include <iostream>

using namespace std;

typedef struct Wezel {
    int liczba;
    Wezel* nastepny;
    Wezel* poprzedni;
    Wezel(int liczba) {
        this->liczba = liczba;
        this->nastepny = nullptr;
        this->poprzedni = nullptr;
    }
} Wezel;

class Lista {
    Wezel *glowa;
    Wezel *ogon;

public:
    Lista(): glowa(nullptr), ogon(nullptr) {}
    bool czyPusta();
    void dodaj(int);
    void usun(int);
    void wypisz();
};

bool Lista::czyPusta() {
    if (glowa == nullptr) {
        cout << "Lista jest pusta!" << endl;
        return true;
    }
    return false;
}

void Lista::dodaj(int liczba) {
    cout << "Dodaję: " << liczba << endl;

    Wezel *nowy = new Wezel(liczba);

    if (czyPusta()) {
        glowa = ogon = nowy;
        return;
    }

    ogon->nastepny = nowy;
    nowy->poprzedni = ogon;
    ogon = nowy;
}

void Lista::usun(int indeks) {
    if (czyPusta()) return;

    cout << "Usuwam pozycję: " << indeks << endl;

    Wezel *pomocniczy1 = glowa, *pomocniczy2 = nullptr;;
    int rozmiar = 0;

    while (pomocniczy1 != nullptr) {
        pomocniczy1 = pomocniczy1->nastepny;
        rozmiar++;
    }

    if (indeks > rozmiar) {
        cout << "Indeks poza zakresem." << endl;
        return;
    }

    pomocniczy1 = glowa;
    if (indeks == 1) {
        glowa = glowa->nastepny;
        delete pomocniczy1;
        return;
    }

    while (indeks-- > 1) {
        pomocniczy2 = pomocniczy1;
        pomocniczy1 = pomocniczy1->nastepny;
    }

    pomocniczy2->nastepny = pomocniczy1->nastepny;

    if (pomocniczy1->nastepny != nullptr) {
        pomocniczy1->nastepny->poprzedni = pomocniczy2;
    } else {
        ogon = pomocniczy2;
    }

    delete pomocniczy1;
}

void Lista::wypisz() {

    if (czyPusta()) return;

    cout << "Lista zawiera: ";
    Wezel* pomocniczy = glowa;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->liczba << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main() {
    Lista lista;

    lista.dodaj(1);
    lista.dodaj(2);
    lista.dodaj(3);
    lista.wypisz();

    lista.usun(1);
    lista.usun(3);
    lista.usun(2);
    lista.dodaj(4);
    lista.wypisz();

    return 0;
}

Dodaję: 1
Lista jest pusta!
Dodaję: 2
Dodaję: 3
Lista zawiera: 1 2 3 
Usuwam pozycję: 1
Usuwam pozycję: 3
Indeks poza zakresem.
Usuwam pozycję: 2
Dodaję: 4
Lista zawiera: 2 4

Stos, kolejka i lista w bibliotece standardowej

Klasa stack

Klasa ta służy do tworzenia stosu. Udostępniane w niej metody to m.in.:

• push() – zadaniem metody jest odłożenie elementu na szczyt stosu;

• pop() – metoda zdejmuje element ze szczytu stosu;

• top() – metoda zwraca referencję do wierzchołka stosu bez usuwania go;

• empty() – metoda sprawdza, czy stos jest pusty;

• size() – metoda zwraca rozmiar stosu.

#include <iostream>
#include <stack>

using namespace std;

int main() {
    stack<int> stos;

    cout << "Odkładam liczby 5, 4, 6" << endl;
    stos.push(5);
    stos.push(4);
    stos.push(6);
    cout << "Rozmiar: " << stos.size() << endl;
    cout << "Wierzchołek: " << stos.top() << endl;

    cout << "Zdejmuję wierzchołek." << endl;
    stos.pop();
    cout << "Rozmiar: " << stos.size() << endl;
    cout << "Wierzchołek: " << stos.top() << endl;

    cout << "Stos zawiera: ";
    while (!stos.empty()) {
        cout << stos.top() <<" ";
        stos.pop();
    }
    cout << endl;

    cout << "Rozmiar: " << stos.size();

    return 0;
}

Odkładam liczby 5, 4, 6
Rozmiar: 3 Wierzchołek: 6
Zdejmuję wierzchołek.
Rozmiar: 2 Wierzchołek: 4
Stos zawiera: 4 5 
Rozmiar: 0

Klasa queue

Klasa ta służy do tworzenia kolejek. Udostępniane w niej metody to m.in.:

• push() – zadaniem metody jest dodanie elementu na końcu kolejki;

• pop() – metoda usuwa pierwszy element kolejki;

• back() – metoda zwraca referencję do ostatniego elementu kolejki bez usuwania go;

• front() – metoda zwraca referencję do pierwszego elementu kolejki bez usuwania go;

• empty() – metoda sprawdza, czy kolejka jest pusta;

• size() – metoda zwraca liczbę elementów kolejki.

#include <iostream>
#include <queue>

using namespace std;

int main() {
    queue<int> kolejka;

    cout << "Dodaję liczby 5, 4, 6" << endl;
    kolejka.push(5);
    kolejka.push(4);
    kolejka.push(6);
    cout << "Rozmiar: " << kolejka.size();
    cout << " Pierwszy: " << kolejka.front();
    cout << " Ostatni: " << kolejka.back() << endl;

    cout << "Usuwam pierwszy." << endl;
    kolejka.pop();
    cout << "Rozmiar: " << kolejka.size();
    cout << " Pierwszy: " << kolejka.front();
    cout << " Ostatni: " << kolejka.back() << endl;

    cout << "Kolejka zawiera: ";
    while (!kolejka.empty()) {
        cout << kolejka.front() <<" ";
        kolejka.pop();
    }
    cout << endl;

    cout << "Rozmiar: " << kolejka.size();

    return 0;
}

Dodaję liczby 5, 4, 6
Rozmiar: 3 Pierwszy: 5 Ostatni: 6
Usuwam pierwszy.
Rozmiar: 2 Pierwszy: 4 Ostatni: 6
Kolejka zawiera: 4 6 
Rozmiar: 0

Klasa list

Klasa ta służy do tworzenia list. Udostępnia następujące metody:

• push_back() – zadaniem metody jest dodanie elementu na końcu listy;

• push_front() – zadaniem metody jest dodanie elementu na początku listy;

• pop_back() – metoda usuwa ostatni element listy;

• pop_front() – metoda usuwa pierwszy element listy;

• back() – metoda zwraca referencję do ostatniego elementu listy bez usuwania go;

• front() – metoda zwraca referencję do pierwszego elementu listy bez usuwania go;

• empty() – metoda sprawdza, czy lista jest pusta;

• size() – metoda zwraca liczbę elementów listy.

#include <iostream>
#include <list>

using namespace std;

int main() {
    list<int> lista;

    cout << "Dodaję liczby 5, 4 na końcu" << endl;
    lista.push_back(5);
    lista.push_back(4);
    cout << "Dodaję liczbę 6 na początku" << endl;
    lista.push_front(6);
    cout << "Rozmiar: " << lista.size();
    cout << " Pierwszy: " << lista.front();
    cout << " Ostatni: " << lista.back() << endl;

    cout << "Usuwam ostatni." << endl;
    lista.pop_back();
    cout << "Rozmiar: " << lista.size();
    cout << " Pierwszy: " << lista.front();
    cout << " Ostatni: " << lista.back() << endl;

    cout << "Lista zawiera: ";
    while (!lista.empty()) {
        cout << lista.front() <<" ";
        lista.pop_front();
    }
    cout << endl;

    cout << "Rozmiar: " << lista.size();

    return 0;
}

Dodaję liczby 5, 4 na końcu
Dodaję liczbę 6 na początku
Rozmiar: 3 Pierwszy: 6 Ostatni: 4
Usuwam ostatni.
Rozmiar: 2 Pierwszy: 6 Ostatni: 5
Lista zawiera: 6 5 
Rozmiar: 0

Słownik