Rekurencyjne struktura danych - lista jednokierunkowa

Przegląd zagadnień

Omawiając pojęcie rekurencji, stwierdziliśmy, że jest to definicja, która odwołuje się do definiowanego przedmiotu. Powstaje pytanie, czy istnieje możliwość definicji struktury danych, która odwoływałaby się do siebie samej. Przeczytawszy tytuł tego rozdziału można się domyślić, że odpowiedź brzmi tak.

W rozdziale tym studenci poznają i nauczą się:

• Definiować własny typ referencyjny.

• Definicję listy jednokierunkowej.

• Dodawać elementy do listy.

• Usuwać elementy z listy.

• Listy dwukierunkowe i cykliczne.

Klasa jako rekord

Przy pomocy słowa struct definiowaliśmy nowy typ wartości (bezpośredni). W języku C# programista może również zdefiniować własny typ referencyjny. Realizuje to przez zastąpienie słowa struct słowem class. W celu uniknięcia pomyłek przyjmijmy, że w dalszej części kursu struktury (rekordy) definiowane przy pomocy słowa struct będziemy nazywali krótko strukturami, natomiast struktury definiowane za pomocą słowa class klasami. Jest to ogólnie przyjęta nomenklatura stosowana w odniesieniu do języka C#.

Do klas możemy stosować wszystko to, co zostało do tej pory powiedziane na temat struktur.

Główna różnica między klasami a strukturami jest taka, że pola (składowe) przedstawiciela klasy, czyli obiektu, są zawsze "przechowywane" na zarządzanej stercie, nawet wtedy, gdy pole jest typu bezpośredniego. Przydział pamięci dla obiektu jest pokazany na rysunku na slajdzie.

Deklaracja zmiennej typu zdefiniowanego przy pomocy słowa class, tworzy zmienną typu referencyjnego, więc jak już wspominano wcześniej, deklaracja zmiennej nie tworzy obiektu. Obiekt tworzymy zawsze przy pomocy słowa kluczowego new:

nazwaZmiennej = new NazwaKlasy();

Po utworzeniu obiektu wszystkie jego pola są zainicjalizowane. Pola liczbowe mają nadaną wartość zero, logiczne false, pola typów referencyjnych wartość null. Polu możemy nadać swoją domyślną wartość, podając ją w definicji pola:

class Osoba
{
public string Nazwisko = "Kowalski";
public string Imie = "Jaś";
public int RokUrodzenia = 1979;
}

Uwaga:
Więcej na temat typu referencyjnego można znaleźć w rozdziale drugim tego kursu.

Struktury stosujemy zazwyczaj do reprezentacji prostych struktur danych typu punkt, rozmiar, prostokąt, data. W przypadku struktur danych bardziej złożonych powinniśmy stosować klasy (np. stos, kolejka (:).

Definiując rekurencyjne struktury danych musimy użyć klasy. Zmienne typów referencyjnych zawierają odwołanie. Odwołanie to niekoniecznie musi pokazywać na obiekt danej klasy, może być puste, czyli zmienna ma wartość null. Dzięki temu definicja ma swój koniec, nie jest nieskończona.

Lista jednokierunkowa

Tablice są bardzo przydatnymi strukturami danych, lecz mają również pewne wady:

1. Rozmiar tablicy musi być podany w trakcie jej tworzenie.

2. Wstawienie nowego elementu, jak również usunięcie istniejącego elementu tablicy, wymaga przesunięcia wszystkich elementów znajdujących się za wstawianym (usuwanym) elementem.

Ograniczenia powyższe rozwiązuje struktura zwana listą jednokierunkową. Lista jednokierunkowa jest kolekcją elementów zwanych węzłami. Każdy węzeł zawiera dane oraz połączenie (odwołanie) do następnego węzła. Pierwszy węzeł listy nazywamy głową (head). Przy pomocy zmiennej głowa (head) możemy odwołać się do pozostałych elementów listy, korzystając z tego, że węzły są połączone. Ostatni element listy zawiera odwołanie puste. Nazywamy go ogonem (tail).

Dodawanie elementu do listy (1)

Procedura dodawania pierwszego elementu do listy (pierwszych danych), czyli utworzenie listy, wygląda następująco:

1. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.

2. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na null.

3. Zmienne ogon i głowa (obie typu Węzeł) ustaw tak, aby odwoływały się do nowo utworzonego obiektu węzeł.

Dodawanie elementu do listy (2)

Procedura dodawania elementu do głowy listy wygląda następująco:

1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę dodawania pierwszego elementu.

2. Utworz nowy obiekt węzeł. Węzeł zawiera dodawane dane.

3. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na obiekt wskazywany przez zmienną głowa.

4. Zmienną głowa ustaw tak, aby odwoływała się do nowo utworzonego obiektu węzeł.

Dodawanie elementu do listy (3)

Procedura dodawania elementu do ogona listy wygląda następująco:

1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę dodawania pierwszego elementu.

2. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.

3. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na null.

4. Odwołanie do następnego węzła obiektu wskazywanego przez zmienną ogon ustaw tak, aby odwoływała się do nowo utworzonego obiektu węzeł.

5. Zmienną ogon ustaw tak, aby odwoływała się do nowo utworzonego obiektu węzeł.

Wstawianie elementu do listy

Procedura wstawiania elementu do listy wygląda następująco:

1. Sprawdź czy lista jest pusta. Jeżeli lista jest pusta wykonaj procedurę dodawania pierwszego elementu.

2. Utwórz nowy obiekt węzeł. Węzeł zawiera dodawane dane.

3. Znajdź węzeł, za którym należy wstawić nowo utworzony węzeł. Nazwijmy ten węzeł poprzedni. Jeżeli węzeł poprzedni jest ostatnim węzłem listy wykonaj procedurę dodawania elementu do ogona. W przypadku, gdy nowy węzeł ma być pierwszym elementem listy, wykonaj procedurę dodawania elementu do głowy.

4. Odwołanie do następnego węzła nowo utworzonego obiektu ustaw na węzeł do którego odwołuje się .węzeł poprzedni.

5. Odwołanie do następnego węzła węzła poprzedni ustaw tak, aby pokazywało na nowo utworzony obiekt węzeł.

Usuwanie elementu z listy (1)

Procedura usuwania elementu z listy, gdy na liście jest jeden element, wygląda następująco:

1. Usuń węzeł z pamięci.

2. Wartość zmiennych ogon i głowa ustaw na null.

Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection (automatyczny odśmiecacz pamięci), wystarczy wykonać tylko krok dwa.

Usuwanie elementu z listy (2)

Procedura usuwania pierwszego elementu (głowy) z listy wygląda następująco:

1. Sprawdź czy lista ma jeden element, Jeżeli tak wykonaj procedurę usuwania elementu z listy, gdy na liście jest jeden element.

2. Wskaż zmienną pomocniczą na element do usunięcia.

3. Wskaż zmienną głowa na drugi element w liście.

4. Usuń węzeł .wskazywany przez zmienną pomocniczą z pamięci.

Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection (automatyczny odśmiecacz pamięci), kroki dwa i cztery mogą być pominięte..

Usuwanie elementu z listy (3)

Procedura usuwania ostatniego węzła (ogona) z listy wygląda następująco:

1. Sprawdź czy lista ma jeden element, Jeżeli tak wykonaj procedurę usuwania elementu z listy, gdy na liście jest jeden element.

2. Wskaż zmienną pomocniczą na element do usunięcia.

3. Wskaż zmienną ogon na przedostatni element w liście. Krok ten w listach jednokierunkowych jest operacją nieefektywną. Wymaga przejścia całej liście. Problem efektywności tego kroku rozwiązują listy dwukierunkowe, o których będzie mowa w dalszej części tego rozdziału.

4. Odwołanie do następnego węzła obiektu wskazywanego przez zmienną ogon (do tej pory przedostatni element listy) ustaw na null.

5. Usuń węzeł .wskazywany przez zmienną pomocniczą z pamięci.

Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection (automatyczny odśmiecacz pamięci), kroki dwa i pięć mogą być pominięte..

Usuwanie elementu z listy (4)

Procedura usuwania ostatniego (ogona) węzła z listy wygląda następująco:

1. Sprawdź czy lista ma jeden element, Jeżeli tak, wykonaj procedurę usuwania elementu z listy, gdy na liście jest jeden element.

2. Wskaż zmienną pomocniczą na element do usunięcia.

3. Jeżeli zmienna pomocnicza odwołuje się do pierwszego elementu listy (głowy) wykonaj procedurę usuwania pierwszego elementu (głowy) z listy. Jeżeli zmienna pomocnicza odwołuje się do ostatniego elementu listy (ogona), wykonaj procedurę usuwania ostatniego węzła (ogona) z listy.

4. Wskaż zmienną poprzedni na element poprzedzający element do usunięcia.

5. Ustaw odwołanie do następnego węzła obiektu wskazywanego przez zmienną poprzedni na węzeł występujący po węźle do skasowania.

6. Usuń węzeł wskazywany przez zmienną pomocniczą z pamięci.

Ponieważ w języku C# obiekty są usuwane z pamięci prze Garbage Collection (automatyczny odśmiecacz pamięci), krok sześć może być pominięty..

Inne rodzaje list

Usuwanie ostatniego elementu listy (ogona) z listy jednokierunkowej jest operacją nieefektywną. Problem ten można rozwiązać stosując tak zwane listy dwukierunkowe. W listach dwukierunkowych każdy węzeł oprócz wskazania na swojego następnika, zawiera również pole pokazujące poprzednika. Wartość poprzednika węzła głowa jest ustawiona na null.

Innym rodzajem listy, przydatnym w specyficznych sytuacjach są listy cykliczne Specyficzną sytuacją jest np. zarządzanie przydziałem pewnego zasobu dla kilku klientów - procesów, każdy proces ma dostęp do zasobu przez pewien określony czas, po czym zasób jest przejmowany przez następny proces.. W listach cyklicznych węzły tworzą pierścień. Każdy węzeł ma swój następnik.

Pytania sprawdzające

1. Zdefiniuj klasę Samochod, która będzie zawierać następujące pola: marka, model, rok produkcji, przebieg
   
   Odp.
   class Samochod
   {
   public string Marka;
   public string Model;
   public int RokProdukcji;
   public ulong Przebieg;
   }

2. Jaki popełniono błąd w poniższym programie?
   
   class Klasa{
   public int Pole;
   }
   ...
   static void Main(){
   Klasa a;
   a.Pole = 10;
   }
   
   Odp.
   W powyższym przykładzie używamy zmienną, która nie zawiera odwołania do żadnego obiektu.

Laboratorium

Ćwiczenie 1:
Napisz program, który będzie zawierał implementacje listy jednokierunkowej. Do listy będą dodawane obiekty klasy Osoba. Klasa Osoba jest zaimplementowana w projekcie Biblioteka. Projekt Biblioteka jest częścią rozwiązania Kurs\Modul12\Start\Modul12\Modul12.sln, gdzie Kurs jest katalogiem, gdzie skopiowano pliki kursu. Program będzie składał się z dwóch podzespołów:

• Biblioteki dll, o nazwie Listy, która będzie zawierała implementację listy jednokierunkowej. W klasie lista będą zaimplementowane następujące metody:

• IsEmpty - sprawdzenie czy lista jest pusta

• AddToHead - dodanie elementu na początek listy

• AddToTail - dodanie elementu na koniec listy

• DeleteFromHead - usunięcie elemntu z początku listy

• DeleteFromTail - usunięcie elementu z końca listy

• PrintAll - wypisanie na ekranie danych wszystkich elementów listy

• GetCount - zwraca ilość elementów w liście

• Programu głównego, w którym przetestujemy listę.

1. Skopiuj rozwiązanie Kurs\Modul12\Start\Modul12\Modul12.sln, gdzie Kurs jest katalogiem, gdzie skopiowano pliki kursu.

2. Otwórz skopiowane rozwiązanie Modul12.sln

3. Dodaj do bieżącego rozwiązania nowy projekt

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

3. typu projektu: Visual C#/Windows

1. szablon: Class Library

2. lokalizacja: Moje Dokumenty\Visual Studio 2005\Projects\

3. nazwa projektu: Listy.

4. Podłącz do programu Listy, podzespół Biblioteka.

1. W okienku Solution Explorer, z menu kontekstowego związanego z elementem reprezentującym projekt Listy wybierz Add Reference...

2. W okienku Add Reference przejdź do zakładki Projects, zaznacz projekt Biblioteka i naciśnij OK.

5. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka.
   
   using Biblioteka;

6. Zmień nazwę pliku Class1.cs na List.cs.

7. Zmień nazwę klasy z Class1 na List. Do klasy List dodaj pola: Wewnątrz klasy List zdefiniuj klasę Node (Węzeł). .Do klasy Node dodaj następujące pola: pole Data (Dane) typu Osoba, pole Next (Nastepny) typu Node. Do klasy List dodaj pole Head (Glowa) i Tail (Ogon) typu Node.
   
   public class List
   {
   public class Node
   {
   public Osoba Data;
   public Node Next;
   }
   public Node Head, Tail;
   }

8. Do klasy List dodaj metodę IsEmpty::
   
   public static bool IsEmpty (List lista)
   {
   return lista.Head == null;
   }

9. Do klasy List dodaj metodę AddToHead::
   
   public static void AddToHead(List lista,Osoba os)
   {
   Node tmp = new Node();
   tmp.Data = os;
   tmp.Next = lista.Head;
   lista.Head = tmp;
   if (lista.Tail == null)
   lista.Tail = tmp;
   }

10. Do klasy List dodaj metodę AddToTail::
    
    public static void AddToTail (List lista,Osoba os)
    {
    Node tmp = new Node();
    tmp.Data = os;
    if (lista.Tail == null)
    lista.Tail = lista.Head = tmp;
    else
    {
    lista.Tail.Next = tmp;
    lista.Tail = tmp;
    }
    }

11. Do klasy List dodaj metodę DeleteFromHead::
    
    public static Osoba DeleteFromHead (List lista)
    {
    if (lista.Head == null) //lista pusta
    throw new InvalidOperationException(
    "Lista jest pusta");
    Osoba x = lista.Head.Data;
    if (lista.Head == lista.Tail
    lista.Head = lista.Tail = null;
    else
    lista.Head = lista.Head.Next;
    return x;
    }

12. Do klasy List dodaj metodę DeleteFromTail::
    
    public static Osoba DeleteFromTail (List lista)
    {
    if (lista.Tail == null) //lista pusta
    throw new InvalidOperationException(
    "Lista jest pusta");
    Osoba x = lista.Tail.Data;
    if (lista.Head == lista.Tail)
    lista.Head = lista.Tail = null;
    else
    {
    Node tmp;
    for (tmp = lista.Head;
    tmp.Next != lista.Tail; tmp = tmp.Next);
    lista.Tail = tmp;
    lista.Tail.Next = null;
    }
    return x;
    }

13. Do klasy List dodaj metodę PrintAll::
    
    public static void PrintAll(List lista)
    {
    for (Node tmp = lista.Head; tmp != null;
    tmp = tmp.Next)
    {
    Osoba.WypiszOsobe(tmp.Data);
    Console.WriteLine();
    }
    }

14. Do klasy List dodaj metodę GetCount::
    
    public static int GetCount(List lista)
    {
    int i;
    Node tmp;
    for (i = 0, tmp = lista.Head; tmp != null;
    i++, tmp = tmp.Next) ;
    return i;
    }

15. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali listę.

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: TestListy.

3. Uczyń nowo utworzony projekt projektem startowym

4. Podłącz do programu TestListy, podzespóły Biblioteka oraz Listy.

5. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka oraz Listy.
   
   using Biblioteka;
   using Listy;

16. Napisz kod testujący listę
    
    static char Menu()
    {
    Console.Clear();
    Console.WriteLine("\n\t\tA - Dodaj osobę do
    ¬początku listy");
    Console.WriteLine("\n\t\tB - Usuń pierwszą
    ¬osobę z listy");
    Console.WriteLine("\n\t\tC - Dodaj osobę na
    ¬koniec listy");
    Console.WriteLine("\n\t\tD - Usuń ostatnią
    ¬osobę z listy");
    Console.WriteLine("\n\t\tE - Podaj liczbę osób
    ¬na liście");
    Console.WriteLine("\n\t\tF - Wypisz osoby z
    ¬listy");
    Console.WriteLine("\n\t\tK - Koniec");
    return Console.ReadKey(true).KeyChar;
    }
    
    static void Main(string[] args)
    {
    List mojaLista = new List();
    Osoba tmp;
    char c;
    
    do
    {
    c = Menu();
    switch (c)
    {
    case 'a':
    case 'A':
    Osoba.WprowadzOsobe(out tmp);
    List.AddToHead(mojaLista, tmp);
    break;
    case 'b':
    case 'B':
    Console.WriteLine("Usunięta osoba to:");
    Osoba.WypiszOsobe(
    List.DeleteFromHead(mojaLista));
    Console.ReadKey();
    break;
    case 'c':
    case 'C':
    Osoba.WprowadzOsobe(out tmp);
    List.AddToTail(mojaLista, tmp);
    break;
    case 'd':
    case 'D':
    Console.WriteLine("Usunięta osoba to:");
    Osoba.WypiszOsobe(
    List.DeleteFromHead(mojaLista));
    Console.ReadKey();
    break;
    case 'e':
    case 'E':
    Console.WriteLine("Liczba osób na liście
    ¬wynosi: {0}",
    List.GetCount(mojaLista));
    Console.ReadKey();
    break;
    case 'f':
    case 'F':
    List.PrintAll(mojaLista);
    Console.ReadKey();
    break;
    }
    }
    while (!(c == 'k' || c == 'K'));
    }

17. Skompiluj i uruchom program.

Ćwiczenie 2:
Wymagania:
Wymagane jest ukończenie poprzedniego ćwiczenia.

Napisz program, który będzie zawierał implementacje kolejki FIFO przy pomocy listy. Do kolejki będziemy dodawać zmienne typu Osoba. Klasa Lista była zaimplementowana w poprzednim ćwiczeniu w programie Listy. Program będzie składał się z dwóch podzespołów:

• Biblioteki dll, o nazwie Kolejka, która będzie zawierała implementację kolejki FIFO.

• Programu głównego, w którym przetestujemy kolejkę.

1. Dodaj do bieżącego rozwiązania nowy projekt

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Class Library

3. nazwa projektu: KolejkaFIFO.

2. Podłącz do programu KolejkaFIFO, podzespóły Biblioteka oraz Listy.

1. W okienku Solution Explorer, z menu kontekstowego związanego z elementem reprezentującym projekt KolejkaFIFO wybierz Add Reference...

2. W okienku Add Reference przejdź do zakładki Projects, zaznacz projekty Biblioteka oraz Listy i naciśnij OK.

3. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka i Listy.
   
   using Biblioteka;
   using Listy;

4. Zmień nazwę pliku Class1.cs na Queue.cs.

5. Zmień nazwę klasy z Class1 na Queue. Do klasy Queue dodaj pole: Kolejka typu List i :od razu je zainicjalizuj
   
   public class Queue
   {
   public List Kolejka = new List();;
   ...
   }

6. Do klasy Queue dodaj metodę Enqueue:
   
   public static void Enqueue(Queue q,Osoba os)
   {
   List.AddToTail(q.Kolejka, os);
   }

7. Do klasy Queue dodaj metodę IsEmpty:
   
   public static bool IsEmpty(Queue q)
   {
   return List.IsEmpty(q.Kolejka);
   }

8. Do klasy Queue dodaj metodę Dequeue:
   
   public static Osoba Dequeue(Queue q)
   {
   return List.DeleteFromHead(q.Kolejka);
   }

9. Do klasy Queue dodaj metodę GetLength:
   
   public static int GetLength(Queue q)
   {
   return List.GetCount(q.Kolejka);
   }

10. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali kolejkę.

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: KomitetKolejkowy.

3. Uczyń nowo utworzony projekt projektem startowym

4. Podłącz do programu KomitetKolejkowy, podzespół Biblioteka oraz KolejkaFIFO.

5. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka oraz KolejkaFIFO.
   
   using Biblioteka;
   using KolejkaFIFO;

6. Napisz kod testujący kolejkę
   
   static char Menu()
   {
   Console.Clear();
   Console.WriteLine("\n\t\tA - Dodaj osobę do
   ¬kolejki");
   Console.WriteLine("\n\t\tB - Usuń osobę z
   ¬kolejki");
   Console.WriteLine("\n\t\tC - Podaj liczbę
   ¬osób w kolejce");
   Console.WriteLine("\n\t\tK - Koniec");
   return Console.ReadKey(true).KeyChar;
   }
   
   static void Main(string[] args)
   {
   Queue mojaKolejka = new Queue();
   Osoba tmp;
   char c;
   
   do
   {
   c = Menu();
   switch (c)
   {
   case 'a':
   case 'A':
   Osoba.WprowadzOsobe(out tmp);
   Queue.Enqueue(mojaKolejka, tmp);
   break;
   case 'b':
   case 'B':
   Osoba.WypiszOsobe(
   Queue.Dequeue(mojaKolejka));
   Console.ReadKey();
   break;
   case 'c':
   case 'C':
   Console.WriteLine("Liczba osób w
   ¬kolejce wynosi: {0}",
   Queue.GetLength(mojaKolejka));
   Console.ReadKey();
   break;
   }
   }
   while (!(c == 'k' || c == 'K'));
   }

11. Skompiluj i uruchom program.

Ćwiczenie 3:
Wymagania:
Wymagane jest ukończenie ćwiczenia pierwszego.

Napisz program, który będzie zawierał implementacje kolejki LIFO. Na stos będziemy wkładać zmienne typu Osoba. Struktura Osoba była zaimplementowana w ćwiczeniu pierwszym w programie Biblioteka. Koleka LIFO będzie zaimplementowana przy pomocy listy jednokierunkowej, która była utworzona w programie pierwszym. Program będzie składał się z dwóch podzespołów:

• Biblioteki dll, o nazwie Stos, która będzie zawierała implementację kolejki LIFO.

• Programu głównego, w którym przetestujemy stos.

1. Dodaj do bieżącego rozwiązania nowy projekt

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

3. typu projektu: Visual C#/Windows

1. szablon: Class Library

2. nazwa projektu: Stos.

2. Podłącz do programu Stos, podzespoły Biblioteka i Listy.

1. W okienku Solution Explorer, z menu kontekstowego związanego z elementem reprezentującym projekt Stos wybierz Add Reference...

2. W okienku Add Reference przejdź do zakładki Projects, zaznacz projekt Biblioteka oraz Listy i naciśnij OK.

3. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka.i Listy
   
   using Biblioteka;
   using Listy;

4. Zmień nazwę pliku Class1.cs na Stack.cs.

5. Zmień nazwę klasy z Class1 na Stack. Do klasy Stack dodaj pole Czarownice typu List:i od razu je zainicjalizuj:
   
   public struct Stack
   {
   List Czarownice = new List();
   }

6. Do klasy Stack dodaj metodę Push:
   
   public static void Push(Stack s,Osoba os)
   {
   List.AddToHead(s, os);
   }

7. Do klasy Stack dodaj metodę IsEmpty:
   
   public static bool IsEmpty(Stack s)
   {
   return List.IsEmpty(s.Czarownice);
   }

8. Do klasy Stack dodaj metodę Pop:
   
   public static Osoba Pop(Stack s)
   {
   return List.DeleteFromHead(s.Czarownice);
   }

9. Do klasy Stack dodaj metodę GetLength:
   
   public static uint GetLength(Stack s)
   {
   return (uint)List.GetCount(s.Czarownice);
   }

10. Do rozwiązania dodaj nowy projekt, w którym będziemy testowali stos.

1. Z menu File wybierz Add/New Project...

2. W oknie dialogowym Add New Project określ następujące właściwości:

1. typu projektu: Visual C#/Windows

2. szablon: Console Application

3. nazwa projektu: Inkwizytor.

3. Uczyń nowo utworzony projekt projektem startowym.

4. Podłącz do programu Inkwizytor, podzespoły Biblioteka oraz Stos.

5. Zaznacz, że będziemy korzystać z przestrzeni nazw Biblioteka oraz Stos.
   
   using Biblioteka;
   using Stos;

6. Napisz kod testujący kolejkę
   
   static char Menu()
   {
   Console.Clear();
   Console.WriteLine("\n\t\tA - Dodaj
   ¬czarownicę do stosu");
   Console.WriteLine("\n\t\tB - Usuń czarownicę
   ¬ze stosu");
   Console.WriteLine("\n\t\tC - Podaj liczbę
   ¬czarownic na stosie");
   Console.WriteLine("\n\t\tK - Koniec");
   return Console.ReadKey(true).KeyChar;
   }
   
   static void Main(string[] args)
   {
   Stack mojaStos = new Stack();
   Osoba tmp;
   char c;
   
   do
   {
   c = Menu();
   switch (c)
   {
   case 'a':
   case 'A':
   Osoba.WprowadzOsobe(out tmp);
   Stack.Push(mojaStos, tmp);
   break;
   case 'b':
   case 'B':
   Osoba.WypiszOsobe(
   Stack.Pop(mojaStos));
   Console.ReadKey();
   break;
   case 'c':
   case 'C':
   Console.WriteLine("Liczba czarownic
   ¬na stosie wynosi: {0}",
   Stack.GetLength(mojaStos));
   Console.ReadKey();
   break;
   case 'd':
   case 'D':
   Stack.Clear(ref mojaStos);
   Console.WriteLine(
   "Stos oprózniony!!!");
   Console.ReadKey();
   break;
   }
   }
   while (!(c == 'k' || c == 'K'));
   }

11. Skompiluj i uruchom program.

L

L

---