Lekce 4 - Fronta a zásobník

V minulé lekci, Spojový seznam, jsme si ukázali, jak vypadá spojový seznam, jak se liší od pole, a jaké jsou časové složitosti jednotlivých operací.

V dnešním tutoriálu datových struktur nás čekají 2 struktury, podobné spojovému seznamu. Jedná se o frontu a zásobník.

Fronta (Queue)

Fronta (anglicky Queue) označuje kolekci, která má 2 základní metody. Jedná se o analogii metod přidat a vymazat, které jsou např. u listů. Metoda pro přidání prvku prvek přidá na konec fronty. Metoda pro vymazání prvku odebere vždy 1. prvek ve frontě, tedy ten, který je "na řadě", ne ten na konci. Prvek je kromě toho, že je z fronty vymazán, také metodou navrácen.

Představte si, že jste u doktora a pacienti utvoří datovou strukturu fronta. Kdo přijde první, odejde první. Kdo přijde poslední, odejde poslední. Někdy se frontě říká FIFO (First In, First Out).

Kolekce nám tedy umožňuje evidovat nějaké prvky (např. požadavky) a vyřizovat je v pořadí, ve kterém přišly. Nezávisle na tom můžeme do fronty samozřejmě dále přidávat další prvky.

Graficky si frontu můžeme představit takto:

Datová struktura fronta

Prioritní fronta

Nyní si představme, že do čekárny přijde pacient, který má kuchyňský nůž zabodnutý ve stehně (protože mu uklouzl při krájení melounu, samozřejmě...) a nebo pacient s COVID-19. Chtěli bychom, aby ho naše struktura nějak pustila před ostatní.


 

...konec náhledu článku...
Pokračuj dál

Znalosti v hodnotě stovek tisíc získáš za pár korun

Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.

Koupit pouze tuto lekci

Koupit jen lekci 25 Kč
Na svém účtu máš aktuálně 0 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • Neomezený a trvalý přístup k jednotlivým lekcím.
  • Kvalitní znalosti v oblasti IT.
  • Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.

Popis článku

Požadovaný článek má následující obsah:

Jak fungují datové struktury fronta a zásobník, k čemu se v praxi používají, a jaké časové složitosti mají jejich operace.

Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.

Článek pro vás napsal Ondřej Michálek
Avatar
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Aktivity