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.

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.

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ę.