Twoje Centrum Szkoleniowe

C++: Stos i kolejka

Stos

Stos jest strukturą danych, która umożliwia efektywne zarządzanie kolejnością elementów według zasady "ostatni wchodzi, pierwszy wychodzi" (LIFO). Ta unikalna właściwość sprawia, że stos jest idealny do zastosowań, gdzie potrzebna jest szybka i łatwa dostępność do ostatnio dodanego elementu, a kolejność elementów ma znaczenie. Służy on przede wszystkim do przechowywania danych w sposób umożliwiający łatwe i szybkie dodawanie nowych elementów na szczyt oraz usuwanie ich z tego samego miejsca.

Wizualnie stos można sobie wyobrazić jako stos talerzy, gdzie każdy nowy talerz kładziemy na wierzchu, a zdejmujemy również z góry. W informatyce stos jest często reprezentowany jako dynamicznie zarządzana lista elementów, gdzie każdy element przechowuje wartość oraz wskazanie na poprzedni element w stosie.

 

Przykładowa implementacja stosu

#include <stack>
#include <iostream>

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

    std::cout << stos.top(); // Wyświetla 20, element na szczycie
    stos.pop(); // Usuwa element ze szczytu
    std::cout << stos.top(); // Wyświetla 10, nowy element na szczycie

    if (stos.empty()) {
        std::cout << "Stos jest pusty.";
    } else {
        std::cout << "Na stosie są elementy.";
    }
    return 0;
}

 

Analiza kodu

1. Tworzenie Stosu: Używamy std::stack z biblioteki STL do utworzenia stosu typu int.
2. Dodawanie Elementów (Push): stos.push(10) umieszcza liczbę 10 na stosie, a następnie stos.push(20) umieszcza 20 na wierzchu stosu.
3. Sprawdzanie Szczytu (Top): stos.top() zwraca wartość elementu znajdującego się na szczycie stosu, nie usuwając go.
4. Usuwanie Elementów (Pop): stos.pop() usuwa element ze szczytu stosu.
5. Sprawdzanie Pustego Stosu: stos.empty() zwraca true jeśli stos jest pusty, w przeciwnym razie false.

 

 

Kolejka

Kolejka w programowaniu to struktura danych działająca według zasady FIFO (First In, First Out), co oznacza, że pierwszy element dodany do kolejki jest pierwszym elementem do usunięcia. Kolejki są powszechnie stosowane w sytuacjach, gdzie dane muszą być przetwarzane w kolejności ich przybycia, na przykład w zarządzaniu procesami, operacjach wejścia/wyjścia czy w algorytmach przeszukujących grafy.

W języku C++ kolejki można implementować przy użyciu standardowej biblioteki szablonów (STL) i jej klasy std::queue. Ta klasa udostępnia serię funkcji ułatwiających zarządzanie kolejką w kontekście FIFO.

 

Operacje na kolejce

 

Enqueue (Dodawanie do kolejki): Operacja enqueue dodaje element na koniec kolejki. W std::queue wykorzystujemy do tego metodę push().

std::queue<int> kolejka;
kolejka.push(5);  // Dodanie elementu 5 do kolejki

 

Dequeue (Usuwanie z kolejki): Operacja dequeue usuwa element z początku kolejki. Używamy do tego metody pop() w std::queue.

kolejka.pop();  // Usunięcie pierwszego elementu z kolejki

 

Front (Pierwszy element): Aby uzyskać dostęp do pierwszego elementu w kolejce (bez usuwania go), używamy metody front().

int pierwszy = kolejka.front();  // Odczytanie pierwszego elementu

 

Sprawdzanie pustego kolejki: Możemy sprawdzić, czy kolejka jest pusta, korzystając z metody empty().

if (kolejka.empty()) {
    std::cout << "Kolejka jest pusta." << std::endl;
}

 

Przykładowa implementacja kolejki

#include <iostream>
#include <queue>

int main() {
    std::queue<std::string> kolejkaKlientow;
    kolejkaKlientow.push("Klient 1");
    kolejkaKlientow.push("Klient 2");
    kolejkaKlientow.push("Klient 3");

    while (!kolejkaKlientow.empty()) {
        std::cout << "Obsługa: " << kolejkaKlientow.front() << std::endl;
        kolejkaKlientow.pop();
    }

    return 0;
}

 

Analiza kodu

Deklaracja kolejki: 

std::queue<std::string> kolejkaKlientow;

Tworzy kolejkę typu std::string do przechowywania nazw klientów.

 

Dodawanie klientów do kolejki:

kolejkaKlientow.push("Klient 1");
kolejkaKlientow.push("Klient 2");
kolejkaKlientow.push("Klient 3");

Dodaje trzech klientów do kolejki. Kolejka przechowuje te wartości w kolejności ich dodania.

 

Pętla obsługi kolejki:

 

while (!kolejkaKlientow.empty()) {
    std::cout << "Obsługa: " << kolejkaKlientow.front() << std::endl;
    kolejkaKlientow.pop();
}

Pętla while kontynuuje działanie dopóki kolejka nie jest pusta. W każdej iteracji pętli:

• kolejkaKlientow.front() zwraca nazwę pierwszego klienta w kolejce (bez jego usuwania).
• std::cout wyświetla nazwę klienta, który jest aktualnie obsługiwany.
• kolejkaKlientow.pop() usuwa pierwszego klienta z kolejki po jego obsłużeniu.

 

Analiza działania programu

Program symuluje proces obsługi klientów w kolejce. Klienci są dodawani do kolejki w określonej kolejności i następnie obsługiwani jeden po drugim zgodnie z zasadą FIFO (pierwszy przybył, pierwszy obsłużony). Po obsłużeniu każdego klienta, jest on usuwany z kolejki. Kiedy wszystkie elementy zostaną usunięte, pętla while kończy swoje działanie, a w konsekwencji program się zamyka.

 

Przykładowe wyjście programu

Obsługa: Klient 1
Obsługa: Klient 2
Obsługa: Klient 3