[C++] Stos

Zanim przejdziesz do dalszej części wpisu o stosie w C++, zapoznaj się z metodą organizacji i zarządzania danymi LIFO. LIFO czyli Last In, First Out (ostatni wchodzi, pierwszy wychodzi) to metoda organizacji danych, która jest stosowana w niektórych strukturach danych, np. stos.

Stos (ang. stack) to struktura danych, która działa właśnie na zasadzie modelu LIFO, co oznacza, że ostatni dodany element jest pierwszym, który zostanie usunięty.

Podstawowymi operacjami na stosie są:

• Push (Dodanie elementu na szczyt stosu);
• Pop (Usunięcie elementu z góry stosu i zwrócenie go);
• Top (Zwrócenie elementu z góry stosu bez jego usuwania);
• Size (Zwraca liczbę elementów w stosie);
• IsEmpty (Sprawdzenie, czy stos jest pusty);

Przykład 1

Prosty przykład programu do zarządzania kolekcją książek:

#include <iostream>
#include <stack>
#include <string>

class Book {

public:

    std::string title;

    Book(const std::string& title) : title(title) {}
    
};

int main() {

    std::stack<Book> bookStack;

    // Dodawanie książek na stos
    bookStack.push(Book("Przeminęło z wiatrem"));
    bookStack.push(Book("Buszujący w zbożu"));
    bookStack.push(Book("Złodziejka książek"));
    bookStack.push(Book("Cudowna podróż"));
    bookStack.push(Book("Podróż do wnętrza Ziemi"));
    bookStack.push(Book("O zmierzchu"));

    // Sprawdzenie, która książka jest na szczycie stosu
    std::cout << "Książka na górze: " << bookStack.top().title << std::endl;

    // Usunięcie książek ze stosu
    while(!bookStack.empty()) {
    
        std::cout << "Usuwanie książki: " << bookStack.top().title << std::endl;
        bookStack.pop();
        
    }

    // Sprawdzenie, czy stos jest pusty
    if(bookStack.empty()) {
    
        std::cout << "Brak książek." << std::endl;
        
    }

    return 0;
    
}

Przykład 2

Kolejny przykład to system dziedziczenia w programowaniu obiektowym. Program ten będzie zawierał klasę bazową Shape i dwie klasy dziedziczące: Circle i Rectangle. Klasa Shape będzie zawierała w sobie stos, do którego będą dodawane obiekty swoich potomków, a metody Circle i Rectangle będą wykorzystywały ten stos.

#include <iostream>
#include <stack>
#include <string>

class Shape {

private:

    std::stack<class Shape*> shapesStack;  // Stos do przechowywania obiektów potomnych

public:

    virtual void addShape(Shape* shape) {
    
        shapesStack.push(shape);
        
    }

    virtual void removeShape() {
    
        if(!shapesStack.empty()) {
        
            delete shapesStack.top();
            shapesStack.pop();
            
        }
        
    }

    virtual void displayShapes() {
    
        while(!shapesStack.empty()) {
        
            std::cout << shapesStack.top()->getName() << " ";
            shapesStack.pop();
            
        }
        
    }

    virtual std::string getName() = 0;  // Pusta metoda wirtualna, która musi być zdefiniowana przez potomnych
    
};

class Circle : public Shape {

private:

    int radius;

public:

    Circle(int radius) : radius(radius) {}

    std::string getName() override {
    
        return "Circle";
        
    }
    
};

class Rectangle : public Shape {

private:

    int width;
    int height;

public:

    Rectangle(int width, int height) : width(width), height(height) {}

    std::string getName() override {
    
        return "Rectangle";
        
    }
    
};

int main() {

    Circle circle(5);
    Rectangle rectangle(3, 4);

    Shape& shape = circle;
    shape.addShape(&circle);
    shape.addShape(&rectangle);

    shape.displayShapes();

    shape.removeShape();

    shape.displayShapes();

    return 0;
    
}

Jakie typy danych można przechowywać w stosie?

Stos pozwala na przechowywanie każdego rodzaju danych, a więc można układać na nim: obiekty, wskaźniki, liczby, tekst i inne.

Przykład 3

Kiedy tworzymy obiekt klasy na stosie, jego pamięć jest przydzielana na stosie. Obiekt istnieje do momentu zakończenia bloku, w którym został zadeklarowany. Oznacza to, że po wyjściu z tego bloku pamięć jest automatycznie zwalniana:

class MyClass {

public:

    MyClass() {
    
        std::cout << "Konstruktor wywołany" << std::endl;
        
    }
    
    ~MyClass() {
    
        std::cout << "Destruktor wywołany" << std::endl;
        
    }
    
};

int main() {

    MyClass obj;  // Obiekt o nazwie 'obj' przechowywany jest na stosie
    
    // Możesz korzystać z obiektu 'obj'
    
    return 0;     // Gdy 'obj' wychodzi z zakresu, destruktor jest wywoływany
    
}