Stos, kolejka i iterator

Nie każda kolekcja ma być przeszukiwana po indeksie. Czasem liczy się tylko kolejność obsługi: ostatni na wierzchu albo pierwszy w szeregu. Przy okazji zajrzysz do środka pętli foreach.

C# Stack Queue IEnumerable 50 min

CEL LEKCJI

Czego się dziś nauczysz

Zbudujesz stos i kolejkę oraz dobierzesz właściwy typ do zadania
Użyjesz Push, Pop, Enqueue, Dequeue i Peek bez ryzyka wyjątku
Wyjaśnisz, jak foreach korzysta z iteratora kolekcji
Powiesz, dlaczego nie wolno zmieniać kolekcji w trakcie pętli foreach
Napiszesz własną metodę oddającą elementy przez yield return

Przygotowanie: lekcje 01–32. Przewidywany czas: 45–90 minut z zadaniami. Przykłady wymagają .NET 8 lub nowszego, z włączonymi ImplicitUsings i Nullable.

TEORIA

Stos — ostatni wchodzi, pierwszy wychodzi

Stos to kupka talerzy: dokładasz na wierzch i z wierzchu zdejmujesz. Kto przyszedł ostatni, wychodzi pierwszy — stąd skrót LIFO (last in, first out).

Program.cs

using System.Collections.Generic;

Stack<string> cofnij = new Stack<string>();

cofnij.Push("wpisz tekst");     // dokladamy na wierzch
cofnij.Push("zmien kolor");
cofnij.Push("usun akapit");

Console.WriteLine(cofnij.Peek());   // usun akapit  - podglad BEZ zdejmowania
Console.WriteLine(cofnij.Pop());    // usun akapit  - zdjecie z wierzchu
Console.WriteLine(cofnij.Pop());    // zmien kolor
Console.WriteLine(cofnij.Count);    // 1

Stos spotkałeś już wcześniej, choć pod inną nazwą: stos wywołań z lekcji 21 działa dokładnie tak samo. Metoda wywołana jako ostatnia kończy się jako pierwsza.

Typowe zastosowania: cofanie zmian w edytorze, sprawdzanie poprawności nawiasów, odwracanie kolejności, przechodzenie labiryntu w głąb.

definicja metody

// czy nawiasy sa poprawnie domkniete
static bool Poprawne(string tekst)
{
    Stack<char> otwarte = new Stack<char>();

    foreach (char z in tekst)
    {
        if (z == '(' || z == '[' || z == '{')
        {
            otwarte.Push(z);
        }
        else if (z == ')' || z == ']' || z == '}')
        {
            if (otwarte.Count == 0) return false;

            char para = otwarte.Pop();
            if (z == ')' && para != '(') return false;
            if (z == ']' && para != '[') return false;
            if (z == '}' && para != '{') return false;
        }
    }

    return otwarte.Count == 0;
}

Pop i Peek na pustym stosie

Obie metody zgłaszają InvalidOperationException, gdy stos jest pusty. Zawsze sprawdzaj Count przed zdjęciem albo użyj TryPop(out var x) i TryPeek(out var x), które zwracają false zamiast wyjątku.

TEORIA

Kolejka — pierwszy wchodzi, pierwszy wychodzi

Kolejka to kolejka w sklepie: dołączasz na koniec, obsługiwany jest początek. Skrót to FIFO (first in, first out).

Program.cs

Queue<string> zgloszenia = new Queue<string>();

zgloszenia.Enqueue("drukarka nie drukuje");   // na koniec
zgloszenia.Enqueue("brak internetu");
zgloszenia.Enqueue("zapomnialem hasla");

Console.WriteLine(zgloszenia.Peek());     // drukarka... - podglad pierwszego
Console.WriteLine(zgloszenia.Dequeue());  // drukarka... - pobranie pierwszego
Console.WriteLine(zgloszenia.Count);      // 2

while (zgloszenia.Count > 0)
{
    Console.WriteLine($"obsluguje: {zgloszenia.Dequeue()}");
}

	`Stack<T>`	`Queue<T>`
Zasada	LIFO — ostatni wychodzi pierwszy	FIFO — pierwszy wychodzi pierwszy
Dodanie	`Push(x)`	`Enqueue(x)`
Pobranie	`Pop()`	`Dequeue()`
Podgląd	`Peek()`	`Peek()`
Bez wyjątku	`TryPop`, `TryPeek`	`TryDequeue`, `TryPeek`
Typowe użycie	cofanie, nawiasy, wywołania metod	zadania do wykonania, bufor, symulacja obsługi

A po co, skoro jest lista?

List<T> zrobi to samo — ale nazwa typu jest częścią dokumentacji. Gdy widzisz Queue<Zgloszenie>, od razu wiesz, że zgłoszenia obsługiwane są po kolei i nikt nie sięga do środka. Dodatkowo Dequeue działa w stałym czasie, a lista.RemoveAt(0) przesuwa wszystkie pozostałe elementy.

TEORIA

Co naprawdę robi foreach

Wszystkie poznane kolekcje — tablica, List<T>, Dictionary, Stack, Queue — da się przejść pętlą foreach. To nie przypadek: wszystkie udostępniają iterator.

Iterator to obiekt, który pamięta, gdzie skończył, i potrafi podać następny element. Kolekcja, która umie go dostarczyć, implementuje interfejs IEnumerable<T> z jedną metodą GetEnumerator().

Program.cs

int[] liczby = { 3, 7, 9 };

// to, co piszesz:
foreach (int x in liczby)
{
    Console.WriteLine(x);
}

// to, co z tego powstaje (w uproszczeniu):
var it = liczby.GetEnumerator();
while (it.MoveNext())
{
    int x = it.Current;
    Console.WriteLine(x);
}

Stąd biorą się dwie reguły, które wcześniej trzeba było przyjąć na wiarę:

Nie znasz indeksu. Iterator podaje kolejny element, nie jego numer. Gdy indeks jest potrzebny — użyj for.
Nie wolno zmieniać kolekcji w trakcie. Dodanie albo usunięcie elementu unieważnia iterator i kolejny MoveNext() zgłasza InvalidOperationException.

Program.cs

List<int> dane = new List<int> { -1, 2, -3, 4 };

foreach (int x in dane)
{
    if (x < 0) dane.Remove(x);   // WYJATEK przy nastepnym obiegu
}

// poprawnie: petla od konca po indeksach
for (int i = dane.Count - 1; i >= 0; i--)
{
    if (dane[i] < 0) dane.RemoveAt(i);
}

Własny iterator: `yield return`

Metoda zwracająca IEnumerable<T> może oddawać elementy po jednym, słowem yield return. Wykonanie zatrzymuje się w tym miejscu i wznawia przy kolejnym pobraniu.

Program.cs

static IEnumerable<int> Parzyste(int od, int doo)
{
    for (int i = od; i <= doo; i++)
    {
        if (i % 2 == 0)
        {
            yield return i;      // oddaj element i poczekaj
        }
    }
}

foreach (int x in Parzyste(1, 10))
{
    Console.WriteLine(x);        // 2 4 6 8 10
}

Elementy powstają dopiero przy przechodzeniu

Parzyste(1, 1000000) nie tworzy miliona liczb w pamięci — kolejne wartości powstają w chwili pobrania. Ta sama zasada rządzi zapytaniami LINQ z lekcji 54, gdzie nazywa się ją odroczonym wykonaniem.

PRZYKŁAD

Przykład: kolejka zgłoszeń i historia zmian

Program.cs

using System.Collections.Generic;

class Program
{
    static IEnumerable<string> Numerowane(IEnumerable<string> zrodlo)
    {
        int nr = 1;
        foreach (string s in zrodlo)
        {
            yield return $"{nr++}. {s}";
        }
    }

    static void Main()
    {
        Queue<string> doObslugi = new Queue<string>();
        doObslugi.Enqueue("stanowisko 3 - brak sieci");
        doObslugi.Enqueue("stanowisko 7 - nie startuje");
        doObslugi.Enqueue("drukarka - zacina papier");

        Stack<string> zrobione = new Stack<string>();

        while (doObslugi.Count > 0)
        {
            string zadanie = doObslugi.Dequeue();
            Console.WriteLine($"obsluguje: {zadanie}");
            zrobione.Push(zadanie);
        }

        Console.WriteLine();
        Console.WriteLine("Historia od najnowszej:");
        foreach (string s in Numerowane(zrobione))
        {
            Console.WriteLine(s);
        }

        Console.WriteLine();
        Console.WriteLine($"Ostatnio zrobione: {zrobione.Peek()}");
        Console.WriteLine($"W kolejce zostalo: {doObslugi.Count}");
    }
}

wynik w konsoli

obsluguje: stanowisko 3 - brak sieci
obsluguje: stanowisko 7 - nie startuje
obsluguje: drukarka - zacina papier

Historia od najnowszej:
1. drukarka - zacina papier
2. stanowisko 7 - nie startuje
3. stanowisko 3 - brak sieci

Ostatnio zrobione: drukarka - zacina papier
W kolejce zostalo: 0

Co dzieje się po kolei

Kolejka oddaje zgłoszenia w kolejności przyjęcia — pierwsze zgłoszone jest obsłużone pierwsze.
Stos oddaje je w kolejności odwrotnej, dlatego historia zaczyna się od ostatniej czynności.
Numerowane przyjmuje IEnumerable<string>, więc zadziała tak samo dla stosu, kolejki, listy i tablicy. To pierwsza metoda w kursie napisana pod dowolną kolekcję.
Peek po pętli działa, bo stos nie jest pusty; doObslugi.Peek() w tym miejscu zgłosiłby wyjątek.

ELEMENTY WBUDOWANE

Zestawienie metod

Metoda	Zwraca	Działanie i ograniczenia
`Push(x)` / `Enqueue(x)`	—	Dodaje element na wierzch stosu / na koniec kolejki. Rozmiar rośnie sam.
`Pop()` / `Dequeue()`	`T`	Zdejmuje i zwraca element. Na pustej kolekcji `InvalidOperationException`.
`Peek()`	`T`	Podgląda następny element bez usuwania. Ten sam wyjątek na pustej kolekcji.
`TryPop(out x)` / `TryDequeue(out x)`	`bool`	Bezpieczna wersja: `false` zamiast wyjątku, gdy nie ma czego pobrać.
`Count`	`int`	Liczba elementów. Właściwość — bez nawiasów.
`Contains(x)`	`bool`	Sprawdza obecność elementu, przechodząc kolekcję. Nie zmienia kolejności.
`ToArray()`	`T[]`	Kopia zawartości. Dla stosu pierwszym elementem jest wierzchołek.
`GetEnumerator()`	iterator	Obiekt, po którym chodzi `foreach`. Ma `MoveNext()` i `Current`.
`yield return x`	—	Oddaje kolejny element metody zwracającej `IEnumerable<T>` i wstrzymuje jej wykonanie. `yield break` kończy sekwencję.
`IEnumerable<T>`	typ	Interfejs „da się przejść pętlą”. Parametr tego typu przyjmie tablicę, listę, stos, kolejkę i wynik LINQ.

CZĘSTE BŁĘDY

Na co uważać

Zapis	Problem
`stos.Pop()` bez sprawdzenia `Count`	Wyjątek na pustym stosie. Użyj warunku albo `TryPop`.
Dodawanie lub usuwanie w trakcie `foreach`	`InvalidOperationException`. Przechodź pętlą `for` od końca albo zbieraj zmiany na osobnej liście.
`Peek` zamiast `Pop` w pętli	Element nie znika, więc pętla nigdy się nie kończy.
`Queue` tam, gdzie potrzebny jest dostęp po indeksie	Kolejka nie ma indeksatora. Jeśli sięgasz do środka, właściwym typem jest `List<T>`.
Metoda `yield` bez wywołania `foreach`	Nic się nie wykona — kod metody rusza dopiero przy pobieraniu elementów.

ZADANIA

Zadania

ZAD 1Odwracanie stosem★☆☆

Wczytaj kilka słów, wrzuć je na stos i wypisz w odwrotnej kolejności. Sprawdź zachowanie dla zera słów.

ZAD 2Kolejka do bufetu★☆☆

Zasymuluj obsługę pięciu osób: dodaj je do kolejki, a potem obsługuj po jednej, wypisując, kto jest obsługiwany i ile osób jeszcze czeka.

ZAD 3Nawiasy★★☆

Napisz metodę bool Poprawne(string tekst, out int pozycjaBledu), która sprawdza, czy nawiasy okrągłe, kwadratowe i klamrowe są poprawnie domknięte, a przy błędzie oddaje przez out pozycję znaku, na którym wykryto problem (przy poprawnym tekście −1). Sprawdź ([]{}), ([)], ((( i napis pusty.

ZAD 4Historia z cofaniem★★☆

Zbuduj dwie kolekcje: stos wykonanych czynności i stos cofniętych. Obsłuż polecenia zrob, cofnij i powtorz, przekładając elementy między stosami.

ZAD 5Własny iterator★★☆

Napisz metodę IEnumerable<int> CoTrzeci(int[] dane), oddającą co trzeci element tablicy. Przejdź wynik pętlą foreach i porównaj z wersją zwracającą gotową tablicę.

ZAD 6Symulacja pracowni★★★

Zgłoszenia mają priorytet zwykły albo pilny. Trzymaj dwie kolejki i obsługuj: dopóki jest coś pilnego, bierz stamtąd. Policz średni czas oczekiwania mierzony liczbą obsłużonych wcześniej zgłoszeń i pokaż, jak wpływa na niego priorytet.

PODSUMOWANIE

Co trzeba zapamiętać

Stos działa według zasady LIFO, kolejka według FIFO — nazwa typu opisuje zamiar programisty.
Pop, Dequeue i Peek na pustej kolekcji zgłaszają wyjątek; wersje Try… zwracają false.
foreach korzysta z iteratora: GetEnumerator, MoveNext i Current.
Kolekcji nie wolno zmieniać w trakcie foreach — usuwaj pętlą for od końca.
Metoda z yield return oddaje elementy po jednym, w chwili pobrania.
Parametr typu IEnumerable<T> przyjmie każdą kolekcję z tego kursu.

Dokumentacja: Microsoft Learn — temat tej lekcji.

Stos, kolejka i iterator

Czego się dziś nauczysz

Stos — ostatni wchodzi, pierwszy wychodzi

Kolejka — pierwszy wchodzi, pierwszy wychodzi

Co naprawdę robi foreach

Własny iterator: yield return

Przykład: kolejka zgłoszeń i historia zmian

Co dzieje się po kolei

Zestawienie metod

Na co uważać

Zadania

Co trzeba zapamiętać

Własny iterator: `yield return`