V informatice je fronta lineární datová struktura, kde jsou komponenty umístěny na jeden konec a odstraněny z druhého konce podle principu „first-in, first-out“ (FIFO). Tato datová struktura může být využita pro řízení posloupnosti akcí nebo ukládání dat. C je počítačový jazyk se schopností fronty začleněnou ve formě polí nebo propojených seznamů.
Vlastnosti:
- Fronta je typ lineární datové struktury, kterou lze sestavit pomocí pole nebo propojeného seznamu.
- Prvky jsou přemístěny do zadní části fronty, zatímco jsou odstraněny zepředu.
- Zařadit do fronty (přidat prvek dozadu) a vyřadit z fronty (odstranit prvek zepředu) jsou dvě operace fronty.
- Když jsou prvky přidávány a odebírány často, může být fronta vytvořena jako kruhová, aby se zabránilo plýtvání pamětí.
Použití pole:
Chcete-li implementovat frontu v C pomocí pole, nejprve definujte maximální velikost fronty a deklarujte pole této velikosti. Přední a zadní celá čísla byla nastavena na 1. Proměnná front představuje přední prvek fronty a proměnná zadní představuje zadní prvek.
Před zatlačením nového prvku na konečnou pozici fronty musíme zvýšit proměnnou back o 1. Fronta je nyní plná a nelze přidat žádné další další prvky, když zadní pozice dosáhne maximální kapacity fronty. Přidáme prvek na začátek fronty a zvětšíme přední proměnnou o jednu pouze za účelem odstranění prvku z fronty. Pokud jsou přední a zadní pozice stejné a nelze smazat žádné další komponenty, můžeme říci, že fronta je prázdná.
str na int
Níže je uvedena instance fronty napsané v C, která využívá pole:
Programovací jazyk C:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Výstup kódu bude:
Výstup:
linux make
10 20 30 Queue is empty-1
Vysvětlení:
- Nejprve do fronty zařadíme tři prvky 10, 20 a 30.
- Poté vyřadíme z fronty a vytiskneme přední prvek fronty, což je 10.
- Dále vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 20.
- Poté vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 30.
- Nakonec vytvoříme dequeue z prázdné fronty, která vypíše 'Queue is empty' a vrátí -1.
Použití propojeného seznamu:
Dalším alternativním přístupem ke konstrukci fronty v programovacím jazyce C je použití propojeného seznamu. Každý z uzlů ve frontě je touto metodou vyjádřen uzlem, který obsahuje hodnotu prvku a ukazatel na následující uzel ve frontě. Aby bylo možné sledovat první a poslední uzel ve frontě, používají se přední a zadní ukazatele.
Vytvoříme nový uzel s hodnotou prvku a nastavíme jeho další ukazatel na NULL, abychom přidali prvek do fronty. Na nový uzel nastavíme přední a zadní ukazatele, pokud je fronta prázdná. Pokud ne, aktualizujeme zadní ukazatel a nastavíme další ukazatel starého zadního uzlu tak, aby ukazoval na nový uzel.
Při odstraňování uzlu z fronty se nejprve odstraní předchozí uzel, poté se přední ukazatel aktualizuje na následující uzel ve frontě a nakonec se uvolní paměť, kterou odstraněný uzel zabíral. Pokud má přední ukazatel po odebrání hodnotu NULL, je fronta prázdná.
řazení vkládání java
Zde je příklad fronty implementované v C pomocí propojeného seznamu:
Programovací jazyk C:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Výstup kódu bude:
Výstup:
10 20 30 Queue is empty-1
Vysvětlení:
- Nejprve do fronty zařadíme tři prvky 10, 20 a 30.
- Poté vyřadíme z fronty a vytiskneme přední prvek fronty, což je 10.
- Dále vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 20.
- Poté vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 30.
- Nakonec se pokusíme vyřadit z fronty z prázdné fronty, což vypíše zprávu 'Fronta je prázdná' a vrátí -1.
výhody:
- Fronty jsou užitečné zejména pro implementaci algoritmů, které vyžadují zpracování prvků v přesném pořadí, jako je prohledávání do šířky a plánování úloh.
- Protože operace s frontami mají časovou složitost O(1), lze je provádět rychle i na obrovských frontách.
- Fronty jsou obzvláště flexibilní, protože je lze jednoduše implementovat pomocí pole nebo propojeného seznamu.
Nevýhody:
- Frontu, na rozdíl od zásobníku, nelze sestavit pomocí jediného ukazatele, takže implementace fronty je o něco složitější.
- Pokud je fronta konstruována jako pole, může se brzy zaplnit, pokud je přidáno příliš mnoho prvků, což může mít za následek problémy s výkonem nebo možná selhání.
- Při použití propojeného seznamu k implementaci fronty může být režie paměti každého uzlu významná, zejména u malých prvků.
Závěr:
Aplikace, které používají fronty, klíčovou datovou strukturu, zahrnují operační systémy, sítě a hry, abychom jmenovali jen některé. Jsou ideální pro algoritmy, které musí zpracovávat prvky v určitém pořadí, protože se snadno vytvářejí pomocí pole nebo propojeného seznamu. Fronty však mají nevýhody, které je třeba vzít v úvahu při výběru datové struktury pro konkrétní aplikaci, jako je spotřeba paměti a složitost implementace.