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

1. Nejprve do fronty zařadíme tři prvky 10, 20 a 30.
2. Poté vyřadíme z fronty a vytiskneme přední prvek fronty, což je 10.
3. Dále vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 20.
4. Poté vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 30.
5. 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í:

1. Nejprve do fronty zařadíme tři prvky 10, 20 a 30.
2. Poté vyřadíme z fronty a vytiskneme přední prvek fronty, což je 10.
3. Dále vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 20.
4. Poté vyřadíme z fronty a znovu vytiskneme přední prvek fronty, což je 30.
5. 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.