{{indexmenu_n>10}}
======== HW 10 - Kruhová fronta v poli ========

^ Termín odevzdání | <wrap important>07.01.2022 22:00 PT</wrap>|
^ Bodový zisk | 4b |
^ Počet uploadů |  10 | 
^ Typ zadání | <del>povinné</del> nepovinné |

==== Fronta==== 
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  [[https://en.wikipedia.org/wiki/Queue_(abstract_data_type)|Wikipedia - Queue]].

/* {{courses:A0B36PR1:tutorials:08:fronta.jpg|}} */

==== Naivní implementace fronty v poli ==== 

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í.**
==== Kruhová fronta v poli ==== 

/*{{:courses:a0b36pr1:tutorials:08:cyklickafronta.png?200 |}}*/

{{:courses:b0b36prp:hw:clipboard03.png?250 |}}

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.


===== Povinné zadání ===== 

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()''. 

<note important>Odevzdávají se pouze dva soubory - ''queue.h'' a ''queue.c''. Tyto soubory odevzdejte v jednom .zip souboru pojmenovaném ''main.zip'' nebo ''queue.zip'' </note> 

Abychom mohli správnost řešení vašeho programu otestovat, je nutné implementovat definované rozhraní, tj. zachovat názvy a argumenty zadaných funkcí.

<code c>
#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__ */
</code>

Poznámky:
  * Ve funkci ''delete_queue()'' uvažujeme, že při mazání je fronta již prázdná a není potřeba dealokovat jednotlivé elementy.
  * Funkce ''get_from_queue()'' vrací element, který je ve frontě na indexu idx. Nijak to nesouvisí s vnitřní reprezentací. Neboli na indexu 0 je vždy element na začáteku fronty, který by byl jako první odstraněn funkcí ''pop_from_queue()''.


===== Testování =====

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 se zadáním. 

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:
  * a value - (push) - Alokuje pamět pro jedno číslo typu ''int'', uloží do něj hodnotu ''value'' a ukazatel na toto číslo vloží na konec fronty zavoláním funkce ''push_to_queue()''.
  * r - (pop) - Zavolá funkci ''pop_from_queue()'' a získá tak ukazatel na první element ve frontě, ze které byl zároveň odstraněn. Vypíše hodnotu čísla, na který odkazuje získaný ukazatel a uvolní jeho paměť.
  * g idx - (get) - Zavolá funkci ''get_from_queue()'' a získá tak ukazatel na element ve frontě na indexu ''idx''. Element nebyl z fronty odstraněn. Následně vypíše hodnotu čísla, na který odkazuje získaný ukazatel.

Na standardním výstupu tento simulátor vypisuje hodnoty pro operace r(pop), g(get). Pokud je dotaz neplatný, vypíše NULL.

<note tip>Podobný způsob testování je použit i v odevzdávacím systému.</note>
/*, kde se navíc kontroluje i správná návratová hodnota funkce ''int get_queue_size(queue_t *queue)'', která vrací aktuální počet prvků ve frontě.*/

=== Příklad 1 - pub01 ====

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

^  Standardní vstup  ^  Očekávaný výstup  ^  Očekávaný chybový výstup  ^  Návratová hodnota  ^
| <code java>
3
a 1
a 2
a 3
r
r
r
r
</code> | <code java>
1
2
3
NULL
</code> |  žádný  |  0  |


=== Příklad 2 - pub02 ===

^  Standardní vstup  ^  Očekávaný výstup  ^  Očekávaný chybový výstup  ^  Návratová hodnota  ^
| <code java>
3
a 1
g -1
g 0
g 1
r
</code> | <code java>
NULL
1
NULL
1
</code> |  žádný  |  0  |

(Další příklady jsou v poskytnutém archivu.)

===== Odevzdání =====

Veřejné příklady + Makefile: {{ :courses:b0b99prpa:hw:hw10_-_fronta.zip |}}

^  ^  Nepovinné zadání  ^ 
^ Název v BRUTE |  HW10  |
^ Odevzdávané soubory |  <wrap important> queue.h, queue.c </wrap>  |
^ Kompilace pomocí |  clang -pedantic -Wall -Werror -std=c99 |
^ Očekávaná amortizovaná časová složitost ((pro jednu operaci push, pop a get.)) |  $\mathcal{O}(1)$  |