Search
libqueue.so
Makefile
lib
queue.c
b0b36prp-hw08-test
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é. Na druhou vyjímání prvků může tvrvat dlouho, protože abychom zachovali pořadí, tak 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 nedojde k nějaké výjimečné události. Zvětšovat frontu doporučujeme na dvojnásobek původní velikost a zmenšovat doporučujeme na třetinu, když klesne pod tuto hranici. Vyhnete 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 b0b36prp-hw08.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)
Veřejné příklady + Makefile: b0b36prp-hw08.zip