Co je datová struktura fronty v Pythonu?

Tento článek vám poskytne podrobné a komplexní znalosti o datových strukturách fronty v Pythonu se spoustou příkladů.

Jak jste již v předchozím článku studovali o důležitosti datových struktur, pojďme se ponořit přímo do tématu článku, tj. Datové struktury fronty. Budu diskutovat o následujících tématech:

Potřeba datové struktury fronty

Předpokládejme, že jednoho dne chcete film. V multiplexu byly vstupenky vydávány na principu „první přijít - první sloužit“ a lidé stáli za sebou a čekali, až na ně přijde řada. Tak co budeš dělat?? Určitě jste šli dozadu a postavili se za poslední osobu čekající na lístek.





queue-data-structure

Tady lidé stojí jeden za druhým a jsou obsluhováni na základě První-první-první-ven (FIFO) mechanismus. Takové uspořádání je známé jako Fronta.



Příklady každodenního života ve frontě

Podívejme se na několik příkladů, kdy používáme typ fronty pracující v každodenním životě:

  • Telefonní záznamník - Osoba, která na vašem gadgetu zavolá jako první, se nejprve zúčastní.
  • Stroj na kontrolu zavazadel - Zkontroluje zavazadla, která byla na dopravním pásu ponechána jako první.
  • Vozidla na mostě pro výběr mýtného - Vozidla přijíždějící brzy odjíždějí první.
  • Call centrum - telefonní systémy budou používat fronty, aby udržovaly lidi, kteří jim volají, v pořádku, dokud servisní zástupce nebude volný.

Všechny tyto příklady následují První-poslední-poslední strategie.

Vytvoření datové struktury fronty

Kromě doplňkových operací mohu říci, že hlavní možné operace ve frontě jsou:



jeden. Zařadit do fronty nebo přidat prvek na konec fronty.

2. Zrušit frontu nebo odeberte prvek z přední části fronty

Začněme vytvořením fronty tříd v Pythonu:

fronta třídy: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0
  • max_size je maximální počet prvků očekávaných ve frontě.
  • Prvky fronty jsou uloženy v seznamu pythonů
  • zadní označuje pozici indexu posledního prvku ve frontě.
  • Zadní část je zpočátku považována za -1, protože fronta je prázdná
  • Přední označuje polohu prvního prvku ve frontě.
  • Přední strana je zpočátku považována za 0, protože bude vždy směřovat k prvnímu prvku fronty

Zařadit do fronty

Nyní, když se pokoušíte zařadit prvky do fronty, musíte si zapamatovat následující body:

  • Zda ve frontě zbývá místo, nebo ne, tj. Pokud se zadní rovná max_size -1
  • Zadní část bude ukazovat na poslední prvek vložený do fronty.

Jaký bude tedy algoritmus ??

#returns max_size of queue def get_max_size (self): return self .__ max_size #returns bool value whether queue is full or not, True if full and False otherwise def is_full (self): return self .__ rear == self .__ max_size-1 # vloží / zařadí data do fronty, pokud není plná def enqueue (self, data): if (self.is_full ()): print ('Queue is full. No enqueue possible') else: self .__ rear + = 1 self. __elements [self .__ rear] = data #display all the content of the queue def display (self): for i in range (0, self .__ rear + 1): print (self .__ elements [i]) #You can use the níže __str __ () pro tisk prvků objektu DS při ladění def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg

Nyní, když provedete následující:

queue1 = Fronta (5)

# Zařaďte všechny požadované prvky do fronty.

queue1.enqueue („A“)

queue1.enqueue („B“)

queue1.enqueue („C“)

queue1.enqueue („D“)

queue1.enqueue („E“)

queue1.display ()

queue1.enqueue („F“)

tisk (fronta1)

Výstup:

NA

B

C

D

JE

Fronta je plná. Žádné pořadí není možné

Data fronty (zepředu dozadu): A B C D E

Zrušit frontu

Nyní, když jste vložili / zařadili prvky do fronty, chcete je vyřadit / smazat zepředu, takže se musíte postarat o následující:

  • Ve frontě jsou prvky, tj. Zadní část by se neměla rovnat -1.
  • Zadruhé si musíte pamatovat, že když jsou prvky smazány zepředu, tak po smazání by měl být front zvýšen tak, aby ukazoval na další front.
  • Přední strana by neměla směřovat na konec fronty, tj. Rovna max_size.

Jaký bude tedy algoritmus ??

#function to check if queue is empty or not def is_empty (self): if (self .__ rear == - 1 or self .__ front == self .__ max_size): return True else: return False #function to deque an element and return to def dequeue (self): if (self.is_empty ()): print ('queue is already empty') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data #function to display elements from zepředu dozadu, pokud fronta není prázdná def display (self): if (not self.is_empty ()): for i in range (self .__ front, self .__ rear + 1): print (self .__ elements [i]) else : print ('prázdná fronta')

Nyní, když provedete následující:

queue1 = Fronta (5)

ansible vs loutka vs kuchař

# Zařadit všechny požadované prvky

queue1.enqueue („A“)

queue1.enqueue („B“)

queue1.enqueue („C“)

queue1.enqueue („D“)

queue1.enqueue („E“)

tisk (fronta1)

# Zrušit pořadí všech požadovaných prvků

print („Dequeued:“, queue1.dequeue ())

print („Dequeued:“, queue1.dequeue ())

print („Dequeued:“, queue1.dequeue ())

print („Dequeued:“, queue1.dequeue ())

print („Dequeued:“, queue1.dequeue ())

print („Dequeued:“, queue1.dequeue ())

# Zobrazte všechny prvky ve frontě.

queue1.display ()

Výstup:

Data fronty (zepředu dozadu): A B C D E

Dequeued: A

Dequeued: B

Vyřazeno: C

Dequeued: D

Dequeued: E

fronta je již prázdná

Dequeued: None

prázdná fronta

Aplikace fronty

Od této chvíle jste již pochopili základy fronty. Nyní, abychom se ponořili hlouběji, se podíváme na některé z jeho aplikací.

java rozdíl mezi implementuje a rozšiřuje
  • Příklad 1:

Tisková fronta v systému Windows používá frontu k uložení všech aktivních a čekajících tiskových úloh. Když chceme tisknout dokumenty, vydáváme tiskové příkazy jeden po druhém. Na základě tiskových příkazů se dokumenty seřadí v tiskové frontě. Když je tiskárna připravena, dokument bude odeslán jako první, první ven, aby byl vytištěn.

Předpokládejme, že jste vydali tiskové příkazy pro 3 dokumenty v pořadí doc1, následované doc2 a doc3.
Tisková fronta se naplní, jak je uvedeno níže:

doc-n, kde doc je dokument odeslaný k tisku an, je počet stránek v dokumentu. Například doc2-10 znamená, že má být vytištěn doc2 a má 10 stránek. Zde je kód, který simuluje operaci tiskové fronty. Projděte si kód a sledujte, jak se fronta používá v této implementaci.

Fronta třídy: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0 def is_full (self): if (self .__ rear = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ front> self .__ rear): return True return False def enqueue (self, data): if (self.is_full ()): print ('Queue is full !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('Queue is empty! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): for index in range (self .__ front, self .__ rear + 1): print (self .__ elements [index]) def get_max_size (self): návrat self .__ max_size # Můžete použít níže uvedený __str __ () k tisku prvků objektu DS, zatímco #debugging def __str __ (self): msg = [] index = self .__ front while (index<=self.__rear): msg.append((str)(self.__elements[index])) index+=1 msg=' '.join(msg) msg='Queue data(Front to Rear): '+msg return msg #function that enqueue are the documents to be printed in Queue named print_queue def send_for_print(doc): global print_queue if(print_queue.is_full()): print('Queue is full') else: print_queue.enqueue(doc) print(doc,'sent for printing') #function that prints the document if number of pages of document is less than #total number of pages in printer def start_printing(): global print_queue while(not print_queue.is_empty()): #here we dequeue the Queue and take the coument that was input first for printing. doc=print_queue.dequeue() global pages_in_printer #the aim of this for loop is to find number of pages of the of document which is doc name followed by “-“ for i in range(0,len(doc)): if(doc[i]=='-'): no_of_pages=int(doc[i+1:]) break if(no_of_pages<=pages_in_printer): print(doc,'printed') pages_in_printer-=no_of_pages print('Remaining no. of pages in printer:', pages_in_printer) else: print('Couldn't print',doc[:i],'. Not enough pages in the printer.') pages_in_printer=12 print_queue=Queue(10) send_for_print('doc1-5') send_for_print('doc2-3') send_for_print('doc3-6') start_printing()

Výstup:

doc1-5 odeslán k tisku

doc2-3 odeslán k tisku

doc3-6 odeslán k tisku

tištěný dokument 1-5

Zbývající č. stránek v tiskárně: 7

doc2-3 tištěný

Zbývající č. stránek v tiskárně: 4

Nelze tisknout dokument doc3. V tiskárně není dostatek stránek

  • Příklad 2:

Zkusme pochopit další příklad, který využívá datovou strukturu fronty. Můžete se pokusit porozumět kódu a říct, co dělá následující funkce?

  1. def fun (n):
  2. aqueue = Fronta (100)
  3. pro číslo v rozsahu (1, n + 1):
  4. zařazení do fronty (počet)
  5. výsledek = 1
  6. while (not (aqueue.is_empty ())):
  7. num = AQUUE.DEQUEUE ()
  8. výsledek * = počet
  9. tisk (výsledek)

Když je funkce fun () vyvolána předáním n,

  • řádky 2 až 4 zařazují prvky do fronty od 1 do n
  • řádky 5 až 8 naleznou součin těchto prvků postupným zařazením do fronty

S tímto se dostáváme na konec tohoto článku Queue Data Structure. Pokud jste úspěšně pochopili a spustili kódy sami, už nejste nováčkem v datové struktuře fronty.

Máte na nás dotaz? Uveďte to prosím v sekci komentářů tohoto článku a my se vám ozveme co nejdříve.

Chcete-li získat podrobné znalosti o Pythonu a jeho různých aplikacích, můžete se zaregistrovat naživo s nepřetržitou podporou a doživotním přístupem.