Search
Fronta je datová struktura, u které jsou definovány operace výběru a vložení prvku. Operace výběr z fronty vybere prvek, který jsme vložili do fronty jako první. Při vkládání prvků do fronty se vkládaná položka vloží na jeho konec. (anglicky enqueue/push a dequeue/pop) Tato struktura se také někdy označuje termínem FIFO (first-in first-out).
Fronta se dá implementovat polem a to buď polem statické délky s explicitním omezením na počet vložených prvků nebo polem dynamické délky. Alterantivně se dá také realizovat datovou strukturou nazývanou spojový seznam, ale to není v této úloze povolené. Doplňující informace můžete nalézt na Wikipedia - Queue.
Nejjednodušší implementací fronty v poli je ukládání i-tého prvku ve frontě na i-tou pozici v poli. Přidávání nového prvku je velmi snadné. Nicméně vyjímání prvků může tvrvat dlouho, protože (abychom zachovali pořadí) je nutné nejprve vyjmout 1. prvek (z čela) fronty a všechny následující prvky posunout o jednu pozici. Taková implementace je značně neefektivní pro větší fronty, proto se zpravidla nepoužívá a ani v tomto úkolu nevede na správné řešení.
i
Kruhová fronta je efektivní implementace fronty v poli, ve které nedochází k žádnému posouvání prvků při operaci odebírání - pop(). Ve kruhové frontě si můžeme představit, že je alokované pole zacyklené. Nyní již neměníme pozici jednotlivých prvků, ale pouze pohybujeme s ukazateli na začátek a konec oblasti s daty. Při implementaci je potřeba dát pozor speciálně na situaci, kdy je několik prvních prvků ve frontě na konci pole a zbytek je již opět na začátku pole.
pop
Implementujte kruhovou frontu v poli (queue.c) podle zadaného hlavičkového souboru (queue.h), ve kterém si vhodně definujte strukturu queue_t obsahující samotnou frontu. Pokud se vkládaný prvek nevejde do fronty, tak ho nevkládejte a vraťte false ve funkci push_to_queue(). Odevzdávají se pouze soubory - queue.h a queue.c. Abychom mohli správnost řešení vašeho programu otestovat, je nutné implementovat definované rozhraní, tj. zachovat názvy a argumenty zadaných funkcí.
queue_t
push_to_queue()
#ifndef __QUEUE_H__ #define __QUEUE_H__ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> /* Queue structure which holds all necessary data */ typedef struct { // TODO - Include your data structure here } queue_t; /* creates a new queue with a given size */ queue_t* create_queue(int capacity); /* deletes the queue and all allocated memory */ void delete_queue(queue_t *queue); /* * inserts a reference to the element into the queue * returns: true on success; false otherwise */ bool push_to_queue(queue_t *queue, void *data); /* * gets the first element from the queue and removes it from the queue * returns: the first element on success; NULL otherwise */ void* pop_from_queue(queue_t *queue); /* * gets idx-th element from the queue * returns the element that will be popped after idx calls of the pop_from_queue() * returns: the idx-th element on success; NULL otherwise */ void* get_from_queue(queue_t *queue, int idx); /* gets number of stored elements */ int get_queue_size(queue_t *queue); #endif /* __QUEUE_H__ */
Poznámky:
delete_queue()
get_from_queue()
pop_from_queue()
Dynamicky měňte velikost alokovaného pole tak, aby fronta využívala adekvátní množství paměti. Je potřeba pole zvětšovat i zmenšovat. Funkce push_to_queue() by se tak měla provést vždy úspěšně a vrátit true, pokud nejde k nějaké výjimečné události. Zvětšovat frontu doporučujeme vždy na dvojnásobek původní velikosti, pokud dojde k zaplnění celé fronty. Zmenšovat doporučujeme vždy na třetinu, když klesne pod tuto hranici. Vyhneme se tak časté změně velikosti.
Pro účely testování jsme pro vás připravili jednoduchý testovací program (main.c), který simuluje práci s kruhovou frontou obsahující odkazy (ukazatele) na čísla typu int. Obecně ale může fronta obsahovat ukazatele jakéhokoliv typu a úkolem je napsat obecnou kruhovou frontu. Tato část slouží pouze pro jednodušší testování. Všechny potřebné soubory jsou v archivu b3b36prg-hw06.zip.
int
Testovací program očekává na standardním vstupu velikost fronty N. Poté jsou na jednotlivých řádcích pokyny pro simulaci práce se frontou:
value
idx
Na standardním výstupu tento simulátor vypisuje hodnoty pro operace r(pop), g(get). Pokud je dotaz neplatný, vypíše NULL.
Vytvoří se kruhová fronta o velikosti 3 a vloží se tam ukazatele na tři celá čísla (1,2,3). Následně se prvky z fronty odstraní pomocí operace r-pop. Následně by fronta měla být prázdná.
3 a 1 a 2 a 3 r r r r
1 2 3 NULL
3 a 1 g -1 g 0 g 1 r
NULL 1 NULL 1
(Další příklady jsou v poskytnutém archivu.)
Pro některé testy v BRUTE nejsou použity vstupní soubory popsané v předchozí sekci, ale vámi implementované funkce jsou volány přímo ze zdrojového kódu. Je to proto, že by vstupní soubory byly příliš velké a hodnocení by trvalo zbytečně dlouho. Jednotilivé testy fungují následovně:1)