HW 10 - Kruhová fronta v poli

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

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.

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

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

#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:

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

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.

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

Veřejné příklady + Makefile: hw10_-_fronta.zip