Stejně jako zásobník je fronta lineární datovou strukturou, která ukládá položky do položky First In First Out ( FIFO ) způsobem. U fronty je jako první odstraněna nejméně nedávno přidaná položka. Dobrým příkladem fronty je jakákoli fronta spotřebitelů pro zdroj, kde je jako první obsluhován spotřebitel, který přišel jako první.

Operace spojené s frontou jsou:

• Zařadit do fronty: Přidá položku do fronty. Pokud je fronta plná, jedná se o podmínku přetečení – časová složitost: O(1)
• Podle toho: Odebere položku z fronty. Položky jsou vyskakovány ve stejném pořadí, v jakém byly vytlačovány. Pokud je fronta prázdná, jedná se o podmínku podtečení – časová složitost: O(1)
• Přední: Získejte přední položku z fronty – Časová složitost: O(1)
• Zadní: Získejte poslední položku z fronty – Časová složitost: O(1)

Implementujte frontu v Pythonu

Existují různé způsoby, jak implementovat frontu Krajta. Tento článek popisuje implementaci fronty pomocí datových struktur a modulů z knihovny Python. Python Queue lze implementovat následujícími způsoby:

• seznam
• sbírky.deque
• ocas.ocas

Implementace pomocí seznamu

Seznam je vestavěná datová struktura Pythonu, kterou lze použít jako frontu. Místo enqueue() a podle toho () , připojit() a pop() funkce se používá. Seznamy jsou však pro tento účel poměrně pomalé, protože vložení nebo odstranění prvku na začátku vyžaduje posunutí všech ostatních prvků o jeden, což vyžaduje čas O(n).
Kód simuluje frontu pomocí seznamu Python. Přidává prvky 'A' , 'b' , a 'C' do fronty a poté je vyřadí, což má za následek prázdnou frontu na konci. Výstup zobrazuje počáteční frontu, prvky vyřazené z fronty ( 'A' , 'b' , 'C' ) a stav fronty je prázdný.

Python3

Výstup:

Initial queue ['a', 'b', 'c'] Elements dequeued from queue a b c Queue after removing elements [] 

Traceback (most recent call last):  File '/home/ef51acf025182ccd69d906e58f17b6de.py', line 25, in   print(queue.pop(0)) IndexError: pop from empty list 

Implementace pomocí collections.deque

Frontu v Pythonu lze implementovat pomocí třídy deque z modulu collections. Deque je upřednostňován před seznamem v případech, kdy potřebujeme rychlejší operace připojení a pop z obou konců kontejneru, protože deque poskytuje časovou složitost O(1) pro operace připojení a pop ve srovnání se seznamem, který poskytuje časovou složitost O(n). . Místo enqueue a deque se používají funkce append() a popleft().
Kód používá a deque> z collections> modul reprezentující frontu. Připojuje se 'A' , 'b' , a 'C' do fronty a vyřadí je z fronty q.popleft()> výsledkem je prázdná fronta. Odebírání komentářů q.popleft()> poté, co je fronta prázdná, by vyvolalo an IndexError> . Kód demonstruje operace fronty a zpracovává scénář prázdné fronty.

Python3

Výstup:

Initial queue deque(['a', 'b', 'c']) Elements dequeued from the queue a b c Queue after removing elements deque([])  

Traceback (most recent call last):  File '/home/b2fa8ce438c2a9f82d6c3e5da587490f.py', line 23, in   q.popleft() IndexError: pop from an empty deque 

Implementace pomocí queue.Queue

Queue je vestavěný modul Pythonu, který se používá k implementaci fronty. queue.Queue(maxsize) inicializuje proměnnou na maximální velikost maxsize. Maximální velikost nula „0“ znamená nekonečnou frontu. Tato fronta se řídí pravidlem FIFO.
V tomto modulu jsou k dispozici různé funkce:

• maximální velikost – Počet povolených položek ve frontě.
• prázdný() – Vraťte True, pokud je fronta prázdná, False v opačném případě.
• plný() – Vraťte True, pokud jsou ve frontě položky maxsize. Pokud byla fronta inicializována s maxsize=0 (výchozí), pak full() nikdy nevrátí True.
• dostat() – Odebrat a vrátit položku z fronty. Pokud je fronta prázdná, počkejte, až bude položka k dispozici.
• get_nowait() – Vraťte položku, pokud je okamžitě k dispozici, v opačném případě zvyšte QueueEmpty.
• dát (položka) – Zařaďte položku do fronty. Pokud je fronta plná, před přidáním položky počkejte, dokud nebude k dispozici volné místo.
• put_nowait(položka) – Vložte položku do fronty bez blokování. Pokud není okamžitě k dispozici žádný volný slot, zvyšte QueueFull.
• qsize() – Vraťte počet položek ve frontě.

Příklad: Tento kód využívá Queue> třídy z queue> modul. Začíná prázdnou frontou a naplňuje ji „ A', 'b' , a 'C' . Po vyřazení z fronty se fronta vyprázdní a přidá se „1“. Přestože byl dříve prázdný, zůstává plný, protože maximální velikost je nastavena na 3. Kód demonstruje operace fronty, včetně kontroly plnosti a prázdnoty.

Python3

Výstup:

0 Full: True Elements dequeued from the queue a b c Empty: True Empty: False Full: False