Kolejka

Kolejka jest strukturą danych, która działa na zasadzie „First-In, First-Out” (FIFO), co oznacza, że element, który został dodany jako pierwszy, jest także pierwszy do wyjęcia. W języku C można zaimplementować kolejkę na wiele sposobów, np. za pomocą tablic, list dwukierunkowych lub stosu.

Różnice Stos vs Kolejka :

Stos (ang. stack) i kolejka (ang. queue) są to dwa typy struktur danych, które opierają się na zasadzie LIFO (Last In First Out) i FIFO (First In First Out) odpowiednio.

W stosie, ostatni element dodany jest pierwszy do usunięcia (LIFO), co oznacza, że elementy dodawane na górę stosu są usuwane z góry stosu. To jest jak kładzenie kart na stos i zdejmowanie ich z góry.

W kolejce, pierwszy element dodany jest pierwszy do usunięcia (FIFO), co oznacza, że elementy dodawane na koniec kolejki są usuwane z początku kolejki.

To jest jak kolejka w sklepie, gdzie pierwszy klient w kolejce jest obsługiwany jako pierwszy.

Implementacja kolejki za pomocą tablicy

---

#include <stdio.h>
#include <stdbool.h>

#define FIFO_SIZE 20 // określa liczę elementów tablicy na której będzie oparta kolejka.

struct queue
{
    int elements[FIFO_SIZE], first, last;
} fifo;

int add_one(int index)
{
    return (index + 1) % FIFO_SIZE; /*Funkcja add_one() służy do zwiększania wartości indeksów kolejki o jeden*/
}

void make_empty(struct queue *fifo) /*Funkcja make_empty() dokonuje inicjacji kolejki, czy nadania jej indeksom wartości „neutralnych”.Indeks first będzie po jej wykonaniu określał pierwszy element tablicy, a indeks last ostatni.*/
{
    fifo->first = 0;
    fifo->last = FIFO_SIZE - 1;
}

bool is_empty(struct queue fifo) /*Funkcja is_empty() zwraca wartość true jeśli nie ma elementów w kolejce lub false jeśli jest choć jeden.*/
{
    return add_one(fifo.last) == fifo.first;
}

int first_one(struct queue fifo) /*Funkcja first_one() zwraca wartość pierwszego elementu kolejki.*/
{
    if (is_empty(fifo) == true)
        return -1;
    else
        return fifo.elements[fifo.first];
}

void enqueue(struct queue *fifo, int data) /*Funkcja enqueue() dodaje do kolejki nowy element, zapisując w nim wartość przekazaną jej przez parametr data*/
{

    if (add_one(add_one(fifo->last)) != fifo->first)
    {
        fifo->last = add_one(fifo->last);
        fifo->elements[fifo->last] = data;
    }
    else
        fprintf(stderr, "Kolejka jest pełna!\n");
}

void dequeue(struct queue *fifo) /*Funkcja dequeue() w tej implementacji kolejki nie zwraca żadnej wartości, po prostu likwiduje początkowy element*/
{
    if (is_empty(*fifo))
        fprintf(stderr, "Kolejka jest pusta!\n");
    else
        fifo->first = add_one(fifo->first);
}

int main(void)
{
    int i;
    make_empty(&fifo);
    for (i = 0; i < FIFO_SIZE - 1; i++)
        enqueue(&fifo, i);
    while (!is_empty(fifo))
    {
        printf("%d ", first_one(fifo));
        dequeue(&fifo);
    }
    return 0;
}

Opis Kodu w źródle: https://achilles.tu.kielce.pl/portal/Members/84df831b59534bdc88bef09b15e73c99/archive/semestr-ii-2018-2019/pdf/pp2/lecture/pp2_lecture_4.pdf

---

---

Źródła ; https://pl.linuxteaching.com/article/how_to_use_c_queue