Kolejki i stosy to fundamentalne struktury danych, które są szeroko stosowane w programowaniu do zarządzania danymi w sposób uporządkowany i efektywny. Obie struktury mają różne podejścia do przechowywania i przetwarzania danych, ale są nieocenione w wielu zastosowaniach, od zarządzania zadaniami w systemach operacyjnych po implementacje algorytmów w przetwarzaniu danych. W tej lekcji omówimy szczegółowo, czym są kolejki i stosy, jak działają, jakie są ich zastosowania, oraz jak można je zaimplementować w języku C++.

Stosy (Stacks)

Stos to struktura danych typu LIFO (Last In, First Out), co oznacza, że ostatni element dodany do stosu jest pierwszym, który zostanie usunięty. Możemy to porównać do stosu talerzy w kuchni: jeśli chcesz wziąć talerz, musisz najpierw zdjąć ten, który został położony jako ostatni. Stos jest używany w wielu aplikacjach, takich jak wywołania funkcji, odwracanie ciągów znaków, nawigacja w przeglądarkach internetowych i wiele innych.

Podstawowe operacje na stosie

• Push: Dodanie elementu na szczyt stosu.
• Pop: Usunięcie elementu ze szczytu stosu.
• Peek/Top: Sprawdzenie elementu na szczycie stosu bez jego usuwania.
• IsEmpty: Sprawdzenie, czy stos jest pusty.

Implementacja stosu w C++

Oto przykład prostej 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::cerr << "Stos jest pełny!" << std::endl;
            return;
        }
        arr[++top] = value;
    }

    void pop() {
        if (top == -1) {
            std::cerr << "Stos jest pusty!" << std::endl;
            return;
        }
        --top;
    }

    int peek() const {
        if (top == -1) {
            std::cerr << "Stos jest pusty!" << std::endl;
            return -1;
        }
        return arr[top];
    }

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

W tej implementacji używamy tablicy do przechowywania elementów stosu. Operacja push dodaje element na szczyt stosu, pop usuwa element ze szczytu, a peek zwraca wartość elementu na szczycie. Sprawdzamy również, czy stos jest pełny lub pusty, aby uniknąć przepełnienia stosu lub usuwania elementów z pustego stosu.

Zastosowania stosów

Stosy znajdują zastosowanie w wielu dziedzinach programowania, w tym:

• Wywołania funkcji: Stos wywołań jest używany do zarządzania wywołaniami funkcji w programach.
• Odwracanie ciągów: Stos może być użyty do odwracania ciągu znaków poprzez dodawanie znaków do stosu i usuwanie ich w odwrotnej kolejności.
• Nawigacja w przeglądarkach: Historia odwiedzanych stron jest przechowywana na stosie, co umożliwia cofanie się do poprzednich stron.
• Algorytmy DFS: Stos jest używany w algorytmach przeszukiwania w głąb (Depth-First Search) w grafach.

Kolejki (Queues)

Kolejka to struktura danych typu FIFO (First In, First Out), co oznacza, że pierwszy element dodany do kolejki jest pierwszym, który zostanie usunięty. Możemy to porównać do kolejki w sklepie: osoba, która ustawiła się jako pierwsza, jest obsługiwana jako pierwsza. Kolejki są używane w systemach kolejkowania zadań, buforach drukarek, algorytmach BFS i wielu innych aplikacjach.

Podstawowe operacje na kolejce

• Enqueue: Dodanie elementu na koniec kolejki.
• Dequeue: Usunięcie elementu z początku kolejki.
• Front: Sprawdzenie elementu na początku kolejki bez jego usuwania.
• IsEmpty: Sprawdzenie, czy kolejka jest pusta.

Implementacja kolejki w C++

Oto przykład prostej implementacji kolejki za pomocą tablicy:

class Queue {
private:
    int* arr;
    int front;
    int rear;
    int capacity;
    int count;

public:
    Queue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
        count = 0;
    }

    ~Queue() {
        delete[] arr;
    }

    void enqueue(int value) {
        if (count == capacity) {
            std::cerr << "Kolejka jest pełna!" << std::endl;
            return;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = value;
        ++count;
    }

    void dequeue() {
        if (count == 0) {
            std::cerr << "Kolejka jest pusta!" << std::endl;
            return;
        }
        front = (front + 1) % capacity;
        --count;
    }

    int frontElement() const {
        if (count == 0) {
            std::cerr << "Kolejka jest pusta!" << std::endl;
            return -1;
        }
        return arr[front];
    }

    bool isEmpty() const {
        return count == 0;
    }
};

W tej implementacji używamy tablicy do przechowywania elementów kolejki. Operacja enqueue dodaje element na koniec kolejki, dequeue usuwa element z początku, a frontElement zwraca wartość elementu na początku. Sprawdzamy również, czy kolejka jest pełna lub pusta, aby uniknąć przepełnienia kolejki lub usuwania elementów z pustej kolejki.

Zastosowania kolejek

Kolejki są szeroko stosowane w różnych aplikacjach, takich jak:

• Kolejkowanie zadań: Kolejki są używane do zarządzania zadaniami w systemach operacyjnych i aplikacjach sieciowych.
• Bufory drukarek: Zadania drukowania są przechowywane w kolejce, aby były obsługiwane w kolejności przybycia.
• Algorytmy BFS: Kolejka jest używana w algorytmach przeszukiwania wszerz (Breadth-First Search) w grafach.
• Przetwarzanie danych: Kolejki są używane w buforach do przetwarzania danych w czasie rzeczywistym.

Porównanie stosów i kolejek

• Stos: Struktura LIFO, używana głównie do zarządzania wywołaniami funkcji, odwracania ciągów i nawigacji w aplikacjach.
• Kolejka: Struktura FIFO, używana do kolejkowania zadań, przetwarzania danych i algorytmów BFS.

Podsumowanie

Kolejki i stosy to podstawowe struktury danych, które są niezbędne w wielu różnych aplikacjach. W tej lekcji omówiliśmy ich podstawowe operacje, implementacje i zastosowania. Zrozumienie, jak działają te struktury, pozwala na efektywne zarządzanie danymi i rozwiązywanie problemów w programowaniu. Zarówno kolejki, jak i stosy mają swoje unikalne cechy, które czynią je nieocenionymi narzędziami w arsenale każdego programisty.

Następny temat ==> Użycie atrap i strażników