Implementacja własnej kolejki (Queue) w C#

W świecie programowania struktury danych pełnią kluczową rolę w organizacji i przetwarzaniu informacji. Jedną z fundamentalnych struktur danych jest kolejka, która odznacza się prostotą i efektywnością w zarządzaniu kolejnością elementów.

Wyobraź sobie kolejkę do sklepu. Klienci ustawiają się jeden za drugim, a obsługiwani są według kolejności przybycia. Ta sama zasada działa w przypadku kolejek w programowaniu. Nowe elementy są dodawane do “końca kolejki”, a usuwane z jej “początku”, zapewniając uporządkowane przetwarzanie.

Kolejki znajdują szerokie zastosowanie w różnych dziedzinach informatyki. W systemach przetwarzania transakcji, takich jak bankomaty, kolejki gwarantują sprawiedliwą i uporządkowaną obsługę operacji. W buforach danych kolejki usprawniają przepływ informacji, zapobiegając przepełnieniu i utracie danych. W algorytmach sortowania kolejki służą do tymczasowego przechowywania danych podczas sortowania, optymalizując proces.

Prostota implementacji i efektywność działania sprawiają, że kolejki są niezwykle wszechstronną strukturą danych. Ich zastosowania obejmują między innymi:

• Systemy przetwarzania transakcji: Kolejki zapewniają uporządkowane przetwarzanie transakcji, gwarantując sprawiedliwą obsługę klientów.
• Buforowanie danych: Kolejki umożliwiają tymczasowe przechowywanie danych w celu zrównoważenia przepływu informacji i zapobiegania przepełnieniu buforów.
• Algorytmy sortowania: Kolejki służą do tymczasowego przechowywania danych podczas sortowania, optymalizując proces.
• Symulacje: Kolejki są wykorzystywane do modelowania rzeczywistych scenariuszy, takich jak kolejki do obsługi klienta lub ruch na drodze.
• Komunikacja między wątkami: Kolejki ułatwiają bezpieczną wymianę danych między wątkami w aplikacji.

Zrozumienie zasad działania kolejek jest fundamentalne dla każdego programisty. Ich prostota i efektywność czynią je cennym narzędziem w budowaniu różnorodnych aplikacji.

Implementacja Kolejki

Podstawowe operacje wykonywane na kolejce to Enqueue i Dequeue.
Dane są dodawane do kolejki za pomocą metody Enqueue.
Dane są usuwane z kolejki za pomocą metody Dequeue.
Można zajrzeć do elementu, który wyjdzie z kolejki i służy do tego metoda Peek.

Utworzymy teraz naszą własną kolejkę.

Rozpoczniemy od zdefiniowania interface.

namespace MyQueue
{
    interface IQueue
    {
        void Enqueue(object element); 
        object Dequeue(); 
        object Peek();
        bool isEmpty();
        bool isFull();
        void Display();
    }
}

Teraz zaimplementujemy naszą kolejkę.

W części prywatnej klasy muszą się znaleźć:
tablica do zapisu danych, indeksy początku i końca kolejki oraz rozmiar kolejki.

using System;

namespace MyQueue 
{
    public class MyQueue : IQueue
    {
        public object[] elements;
        private int startOfQueue;
        private int endOfQueue;
        private int queueSize;

        public MyQueue()
        {
            startOfQueue = 0;
            endOfQueue = 0;
            queueSize = 20;
            elements = new object[queueSize];
        }
        public MyQueue(int capacity)
        {
            startOfQueue = 0;
            endOfQueue = 0;
            queueSize = capacity;
            elements = new object[capacity];
        }
        private int Increase(int a)
        {
            return (a + 1) % queueSize;
        }
        public bool isEmpty()
        {
            if (startOfQueue == endOfQueue) return true;

            return false;
        }
        public bool isFull()
        {
            if (Increase(endOfQueue) == startOfQueue) return true;

            return false;
        }
        public void Enqueue(object element) 
        {
            if (isFull())
            {
                Console.WriteLine("Kolejka jest pełny!");
            }
            else
            {
                elements[endOfQueue] = element;
                endOfQueue = Increase(endOfQueue);
                Console.WriteLine("Element został pomyślnie dodany!");
            }
        }
        public object Dequeue()
        {
            if (isEmpty())
            {
                Console.WriteLine("Kolejka jest pusta!");
                return "Bez elementów";
            }
            else
            {
                object wynik = elements[startOfQueue];
                startOfQueue = Increase(startOfQueue);
                return wynik;
            }
        }
        public object Peek()
        {
            if (isEmpty())
            {
                Console.WriteLine("Kolejka jest pusty!");
                return "Bez elementów";
            }
            else
                return elements[startOfQueue];
        }
        public void Display()
        {
            if (isEmpty())
                Console.WriteLine("Brak elementów do wyświetlenia");

            for (int i = startOfQueue; i < endOfQueue; i++)
                Console.WriteLine("Element{0}: {1}", (i + 1), elements[i]);
        }
    }
}

Omówienie struktury klasy:

Klasa MyQueue implementuje interfejs IQueue, definiując metody do zarządzania kolejką typu FIFO (First In, First Out). Posiada ona trzy prywatne pola:

• elements: Tablica przechowująca elementy kolejki.
• startOfQueue: Wskaźnik na pierwszy element w kolejce.
• endOfQueue: Wskaźnik na pozycję po ostatnim elemencie w kolejce.
• queueSize: Rozmiar tablicy elements.

Konstruktory:

Klasa posiada dwa konstruktory:

• MyQueue(): Domyślny konstruktor tworzy kolejkę o rozmiarze 20 elementów.
• MyQueue(int capacity): Tworzy kolejkę o podanej pojemności capacity.

Metody pomocnicze:

• Increase(int a): Metoda pomocnicza zwraca indeks następny po a, uwzględniając owijanie się wokół tablicy.

Metody interfejsu IQueue:

1. isEmpty():

Sprawdza, czy kolejka jest pusta. Zwraca true, jeśli startOfQueue jest równe endOfQueue, co oznacza brak elementów.

2. isFull():

Sprawdza, czy kolejka jest pełna. Zwraca true, jeśli Increase(endOfQueue) jest równe startOfQueue, co oznacza, że następna pozycja jest już zajęta przez pierwszy element.

3. Enqueue(object element):

Dodaje nowy element element do kolejki. Jeśli kolejka jest pełna, wyświetla komunikat o błędzie. W przeciwnym razie:

• Dodaje element do tablicy elements na pozycji endOfQueue.
• Zwiększa endOfQueue za pomocą metody Increase.
• Wyświetla komunikat o pomyślnym dodaniu elementu.

4. Dequeue():

Usuwa pierwszy element z kolejki. Jeśli kolejka jest pusta, wyświetla komunikat o błędzie i zwraca wartość “Bez elementów”. W przeciwnym razie:

• Pobiera pierwszy element (na pozycji startOfQueue).
• Zmniejsza startOfQueue za pomocą metody Increase.
• Zwraca usunięty element.

5. Peek():

Zwraca pierwszy element w kolejce bez usuwania go. Jeśli kolejka jest pusta, wyświetla komunikat o błędzie i zwraca wartość “Bez elementów”. W przeciwnym razie zwraca pierwszy element (na pozycji startOfQueue).

6. Display():

Wyświetla wszystkie elementy w kolejce. Jeśli kolejka jest pusta, wyświetla komunikat o braku elementów. W przeciwnym razie iteruje po elementach w kolejności od startOfQueue do endOfQueue i wyświetla je wraz z ich numerami.

Gotowa klasa Stack<T> (stos, odwrotna zasada niż kolejka) opisana jest w Stack w C# — stos LIFO na przykładach.

I teraz skorzystamy z naszej kolejki w aplikacji.

using System;

namespace MyQueue
{
    class Program
    {
        static void Main(string[] args)
        {
            MyQueue queue = new MyQueue();

            while (true)
            {
                int choice = DisplayMenu();

                WorkWithAChoice(queue, choice);

                BackToMenu();
            }
        }

        private static int DisplayMenu()
        {
            Console.Clear();
            Console.WriteLine("nKolejka MENU (rozmiar -- 20)");
            Console.WriteLine();
            Console.WriteLine("1. Dodaj element.");
            Console.WriteLine("2. Usuń element.");
            Console.WriteLine("3. Zobacz element.");
            Console.WriteLine("4. Wyświetl elementy kolejki.");
            Console.WriteLine("5. Koniec programu");
            Console.WriteLine();
            Console.Write("Dokonaj wyboru co chcesz zrobić: ");
            int.TryParse(Console.ReadLine(), out int result);

            return result;
        }

        private static void WorkWithAChoice(MyQueue queue, int choice)
        {
            switch (choice)
            {
                case 1:
                    Console.WriteLine("Wpisz element: ");
                    queue.Enqueue(Console.ReadLine());
                    break;
                case 2:
                    Console.WriteLine("Element usunięty: {0}", queue.Dequeue());
                    break;
                case 3:
                    Console.WriteLine("Pierwszy element w kolejce to: {0}", queue.Peek());
                    break;
                case 4:
                    queue.Display();
                    break;
                case 5:
                    Environment.Exit(1);
                    break;
                default:
                    Console.WriteLine("Dokonałeś niewłaściwego wyboru!");
                    break;
            }
        }
        private static void BackToMenu()
        {
            Console.WriteLine("Nacisnij Enter aby przejsc do Menu");
            Console.ReadKey();
        }
    }
}

Wyjaśnienie implementacji w klasie Program

Program MyQueue.Program demonstruje działanie kolejki zaimplementowanej w klasie MyQueue. Program działa w pętli while, prezentując menu użytkownikowi i wykonując wybraną operację na kolejce.

1. Metoda Main:

• Tworzy instancję kolejki MyQueue.
• Wchodzi w pętlę while, która trwa do czasu zakończenia programu przez użytkownika.
• Wewnątrz pętli:
  • Wyświetla menu z dostępnymi opcjami.
  • Pobiera wybór użytkownika z konsoli.
  • Wywołuje metodę WorkWithAChoice do wykonania wybranej operacji.
  • Wyświetla komunikat “Nacisnij Enter…” i czeka na naciśnięcie klawisza Enter, aby powrócić do menu.

2. Metoda DisplayMenu:

• Wyświetla czyste okno konsoli.
• Wyświetla nagłówek “Kolejka MENU” i informację o domyślnym rozmiarze kolejki (20).
• Wyświetla listę dostępnych opcji (dodanie elementu, usunięcie elementu, itp.) wraz z ich numerami.
• Podaje instrukcje dotyczące wprowadzania wyboru.
• Pobiera wybór użytkownika z konsoli i próbuje przekonwertować go na liczbę całkowitą (int).
• Zwraca wprowadzoną liczbę całkowitą (wybór użytkownika).

3. Metoda WorkWithAChoice:

• Przyjmuje instancję kolejki (queue) i wybraną opcję (choice) jako argumenty.
• Używa instrukcji switch do wykonania odpowiedniej operacji na podstawie wyboru użytkownika:
  • Przypadek 1: Dodanie elementu.
    • Pobiera element od użytkownika z konsoli.
    • Wywołuje metodę Enqueue kolejki, aby dodać element do kolejki.
    • Wyświetla komunikat potwierdzający dodanie elementu.
  • Przypadek 2: Usunięcie elementu.
    • Wywołuje metodę Dequeue kolejki, aby usunąć pierwszy element.
    • Sprawdza, czy operacja się udała.
      • Jeśli tak, wyświetla usunięty element.
      • Jeśli nie, wyświetla komunikat o pustej kolejce.
  • Przypadek 3: Podgląd pierwszego elementu.
    • Wywołuje metodę Peek kolejki, aby uzyskać pierwszy element.
    • Sprawdza, czy operacja się udała.
      • Jeśli tak, wyświetla pierwszy element.
      • Jeśli nie, wyświetla komunikat o pustej kolejce.
  • Przypadek 4: Wyświetlenie wszystkich elementów.
    • Wywołuje metodę Display kolejki, aby wyświetlić wszystkie elementy w kolejce.
  • Przypadek 5: Zakończenie programu.
    • Wywołuje metodę Environment.Exit(1), aby zakończyć program z kodem błędu 1.
  • Domyślny:
    • Wyświetla komunikat o błędnym wyborze.

4. Metoda BackToMenu:

• Wyświetla komunikat “Nacisnij Enter, aby przejść do menu”.
• Czeka na naciśnięcie klawisza Enter, aby powrócić do menu głównego.

Ilustracja przepływu danych:

Użytkownik wybiera opcję z menu:

1. Wybór trafia do metody WorkWithAChoice.
2. Metoda WorkWithAChoice wykonuje odpowiednią operację na kolejce:
   • Dodanie elementu: pobiera element od użytkownika i dodaje go do kolejki.
   • Usunięcie elementu: usuwa pierwszy element z kolejki (jeśli istnieje).
   • Podgląd elementu: wyświetla pierwszy element w kolejce (jeśli istnieje).
   • Wyświetlenie elementów: wyświetla wszystkie elementy w kolejce.
   • Zakończenie programu: kończy działanie programu.
3. Wynik operacji (np. usunięty element, lista elementów) jest wyświetlany użytkownikowi.
4. Program wraca do menu głównego, czekając na kolejny wybór użytkownika.

Jeśli wolisz najpierw poznać gotową klasę Queue<T>, zanim zbudujesz własną, zobacz Queue w C# — kolejka FIFO na przykładach. Analogiczna implementacja dla stosu jest w Implementowanie stosu (Stack) w C#.

Podsumowanie i wnioski: Kolejki – proste, ale potężne narzędzie

W tym wpisie zaprezentowaliśmy implementację kolejki typu FIFO w języku C# oraz przykładowy program demonstrujący jej działanie. Zrozumienie zasad działania kolejek jest fundamentalne dla każdego programisty ze względu na ich wszechstronność i przydatność w wielu aplikacjach.

Kluczowe punkty dotyczące implementacji kolejki:

• Kolejka to struktura danych przechowująca elementy w kolejności dodawania (FIFO).
• Implementacja wykorzystuje tablicę do przechowywania elementów i dwa wskaźniki (startOfQueue i endOfQueue) do zarządzania kolejnością.
• Metody Enqueue i Dequeue umożliwiają dodawanie i usuwanie elementów z kolejki.
• Metody Peek, isEmpty i isFull pozwalają na sprawdzenie zawartości i stanu kolejki.
• Metoda Display wyświetla wszystkie elementy w kolejce.

Zastosowania kolejek:

• Systemy przetwarzania transakcji (np. bankomaty) – uporządkowane przetwarzanie operacji.
• Buforowanie danych – tymczasowe przechowywanie danych w celu zrównoważenia przepływu.
• Algorytmy sortowania – tymczasowe przechowywanie danych podczas sortowania.
• Symulacje – modelowanie rzeczywistych scenariuszy z kolejkami (np. kolejki do sklepu).
• Komunikacja między wątkami – bezpieczna wymiana danych między wątkami w aplikacji.

Wnioski:

Kolejki to proste, ale potężne struktury danych, które odznaczają się efektywnością w zarządzaniu kolejnością elementów. Ich wszechstronność czyni je cennym narzędziem w budowaniu różnorodnych aplikacji. Zrozumienie zasad działania kolejek jest kluczowe dla każdego programisty, który chce tworzyć wydajne i skalowalne oprogramowanie.

Świat struktur danych i algorytmów jest fascynujący i oferuje wiele możliwości pogłębiania wiedzy. Zachęcamy do dalszego odkrywania i zgłębiania tych tematów, aby rozwijać swoje umiejętności programistyczne i tworzyć jeszcze bardziej wartościowe rozwiązania.

Dodatkowe wskazówki:

• Eksperymentuj z różnymi implementacjami kolejek, aby poznać różne podejścia do zarządzania kolejnością elementów.
• Zastosuj kolejki w swoich projektach programistycznych, aby sprawdzić ich działanie w praktyce.
• Poznaj inne struktury danych, takie jak stosy i listy, aby zrozumieć ich zalety i wady w różnych sytuacjach.
• Ucz się algorytmów wykorzystujących struktury danych, aby poszerzyć swoje umiejętności rozwiązywania problemów.

Pamiętaj, że programowanie to ciągły proces nauki i doskonalenia. Im więcej wiesz o strukturach danych i algorytmach, tym bardziej efektywnym i kreatywnym programistą możesz stać się.