Stosy to jedna z kluczowych struktur danych w informatyce, często używana w programowaniu do rozwiązywania różnych problemów, takich jak zarządzanie pamięcią, przetwarzanie wyrażeń arytmetycznych i nawigacja w strukturach danych. Stos działa na zasadzie LIFO (Last In, First Out), co oznacza, że ostatnio dodany element jest przetwarzany jako pierwszy. Dzięki tej unikalnej właściwości stosy są niezwykle przydatne w sytuacjach, gdy musimy odwrócić kolejność przetwarzania danych lub przechowywać tymczasowe informacje, które są potrzebne później. W tej lekcji omówimy szczegółowo, jak działają stosy, jakie są podstawowe operacje, jak je implementować w różnych językach programowania oraz jakie mają zastosowania w praktyce.

Podstawowe pojęcia i zasada działania

Stos to abstrakcyjna struktura danych, która pozwala na dodawanie i usuwanie elementów tylko z jednego końca, zwanego wierzchołkiem (ang. top). Operacje, które można wykonywać na stosie, to:

• push: Dodanie elementu na wierzchołek stosu.
• pop: Usunięcie elementu z wierzchołka stosu.
• top/peek: Zwrócenie elementu na wierzchołku stosu bez jego usuwania.
• isEmpty: Sprawdzenie, czy stos jest pusty.

Ważne jest, aby zrozumieć, że stos nie pozwala na losowy dostęp do elementów; jedynym sposobem na dostęp do danych jest użycie operacji push, pop i top.

Implementacja stosów w C++

W języku C++ stosy można implementować na kilka sposobów, korzystając ze standardowych kontenerów STL, takich jak std::stack, lub tworząc własne implementacje przy użyciu list lub tablic.

1. Implementacja std::stack

std::stack to kontener STL, który zapewnia wszystkie podstawowe operacje stosu. Oto przykład implementacji:

#include <iostream>
#include <stack>

int main() {
    std::stack<int> stack;
    stack.push(10);  // Dodanie elementu
    stack.push(20);
    stack.push(30);

    while (!stack.empty()) {
        std::cout << "Top element: " << stack.top() << std::endl;
        stack.pop();  // Usunięcie elementu
    }

    return 0;
}

W powyższym przykładzie tworzymy stos liczb całkowitych, dodajemy kilka elementów za pomocą push() i przetwarzamy je w kolejności LIFO za pomocą top() i pop(). std::stack jest implementowany na bazie kontenera std::deque lub std::vector, co zapewnia wydajność O(1) dla operacji push i pop.

Implementacja własnego stosu

Chociaż std::stack jest wygodnym narzędziem, czasami przydatne jest stworzenie własnej implementacji stosu, aby lepiej zrozumieć, jak działa ta struktura danych. Oto przykład implementacji stosu za pomocą tablicy:

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    Stack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    ~Stack() {
        delete[] arr;
    }

    void push(int value) {
        if (top == capacity - 1) {
            std::cout << "Stack overflow" << std::endl;
            return;
        }
        arr[++top] = value;
    }

    void pop() {
        if (top == -1) {
            std::cout << "Stack underflow" << std::endl;
            return;
        }
        --top;
    }

    int peek() {
        if (top == -1) {
            std::cout << "Stack is empty" << std::endl;
            return -1;
        }
        return arr[top];
    }

    bool isEmpty() {
        return top == -1;
    }
};

W tej implementacji używamy dynamicznej tablicy do przechowywania elementów stosu. Metoda push() dodaje element na wierzchołek stosu, a metoda pop() usuwa element z wierzchołka. Sprawdzamy również warunki przepełnienia (stack overflow) i opróżnienia stosu (stack underflow), aby zapewnić bezpieczne działanie.

Zastosowania stosów

Stosy mają wiele praktycznych zastosowań w różnych dziedzinach informatyki:

1. Zarządzanie pamięcią

Stosy są używane do zarządzania pamięcią w programach rekurencyjnych. Każde wywołanie funkcji jest dodawane na stos wywołań, a gdy funkcja się kończy, jej dane są usuwane ze stosu. Dzięki temu stosy odgrywają kluczową rolę w alokacji pamięci dla zmiennych lokalnych i zarządzaniu wywołaniami funkcji.

2. Przetwarzanie wyrażeń

Stosy są szeroko stosowane w przetwarzaniu wyrażeń arytmetycznych i logicznych. Na przykład, w analizie wyrażeń w notacji odwrotnej polskiej (ang. Reverse Polish Notation, RPN) stos jest używany do obliczania wartości wyrażenia. Podobnie, stosy są wykorzystywane w kompilatorach do analizy nawiasów i operatorów w wyrażeniach matematycznych.

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

bool areParenthesesBalanced(const std::string& expression) {
    std::stack<char> stack;
    for (char ch : expression) {
        if (ch == '(') {
            stack.push(ch);
        } else if (ch == ')') {
            if (stack.empty()) return false;
            stack.pop();
        }
    }
    return stack.empty();
}

int main() {
    std::string expression = "(1 + (2 * 3))";
    if (areParenthesesBalanced(expression)) {
        std::cout << "Parentheses are balanced" << std::endl;
    } else {
        std::cout << "Parentheses are not balanced" << std::endl;
    }
    return 0;
}

W tym przykładzie stos jest używany do sprawdzania, czy nawiasy w wyrażeniu są poprawnie zbalansowane. Każdy otwierający nawias jest dodawany na stos, a każdy zamykający nawias usuwa element ze stosu. Jeśli stos jest pusty po przetworzeniu całego wyrażenia, nawiasy są zbalansowane.

3. Nawigacja w strukturach danych

Stosy są używane w algorytmach przeszukiwania drzew i grafów, takich jak DFS (Depth-First Search). Algorytm DFS wykorzystuje stos do nawigacji po strukturach danych, aby odwiedzać węzły w określonej kolejności.

4. Cofanie operacji

Stosy są wykorzystywane w funkcjonalności cofania (undo) w edytorach tekstu i innych aplikacjach. Każda wykonana operacja jest dodawana na stos, a gdy użytkownik chce cofnąć operację, jest ona zdejmowana ze stosu i odwracana.

Analiza wydajności

Stosy oferują bardzo wydajną obsługę operacji push i pop, które mają złożoność O(1). Dzięki temu stosy są idealnym wyborem do zarządzania danymi tymczasowymi, które muszą być przetwarzane w kolejności LIFO. Jednak stosy mają ograniczenia, takie jak brak losowego dostępu do elementów i ograniczona pojemność w przypadku implementacji na bazie tablicy.

Porównanie stosów i innych struktur danych

Stosy mają swoje unikalne właściwości w porównaniu z innymi strukturami danych, takimi jak listy i kolejki:

• Zalety: Stosy są proste w implementacji i bardzo wydajne, gdy potrzebujemy przetwarzać dane w kolejności LIFO. Są idealne do zarządzania wywołaniami funkcji, przetwarzania wyrażeń i implementacji funkcji cofania.
• Wady: Stosy nie pozwalają na losowy dostęp do elementów, co może być ograniczeniem w niektórych aplikacjach. W przypadku implementacji na bazie tablicy istnieje również ryzyko przepełnienia stosu.

Podsumowanie

Stosy to fundamentalna struktura danych, która znajduje zastosowanie w zarządzaniu pamięcią, przetwarzaniu wyrażeń, nawigacji w strukturach danych oraz implementacji funkcji cofania. Zrozumienie, jak działają stosy i jak efektywnie je implementować, jest kluczowe dla każdego programisty. Dzięki operacjom push, pop i top stosy oferują prosty, ale potężny sposób przechowywania i przetwarzania danych w kolejności LIFO. Bez względu na to, czy tworzysz aplikacje desktopowe, systemy operacyjne czy algorytmy grafowe, stosy są nieocenionym narzędziem w rozwiązywaniu problemów programistycznych.

Następna lekcja ==> Algorytmy z nawrotami