Mi a várólista adatstruktúrája a Pythonban?

Ez a cikk részletes és átfogó ismereteket nyújt a Python Queue Data Structure-jéről, sok példával.

Amint az előző cikkben már tanulmányozta az adatstruktúrák fontosságát, a cikk témájában, azaz a várólista adatstruktúrájában merülhetünk el. A következő témákat fogom megvitatni:



A várólista adatstruktúrájának szükségessége

Tegyük fel, hogy egyszer egy filmre vágysz. A multiplexben a jegyeket az Először jöjjön-szolgálják alapon állították ki, és az emberek egymás mögött állva várták a sorukat. Szóval mit fogsz csinálni?? Biztosan hátul ment, és az utolsó, a jegyre váró ember mögé állt.



queue-data-structure

Itt az emberek egymás mögött állnak, és a First-in-first-out (FIFO) gépezet. Egy ilyen elrendezés a Sor.



A mindennapi élet példái a várólistára

Vegyünk néhány példát, ahol a mindennapi életben várakozási sor típusát látjuk:

  • Telefonos üzenetrögzítő rendszer- Az a személy vesz részt először, aki először hívja a modult.
  • Poggyászellenőrző gép - Ellenőrizze az első szállítószalagon tartott poggyászt.
  • Járművek az útdíj-hídon - A korán érkező járművek indulnak először.
  • Telefonközpont - a telefonrendszerek a várólistákat fogják használni, hogy rendben tartsák az őket hívó embereket, amíg a szervizképviselet szabad lesz.

Mindezek a példák következnek First-In-Last-Out stratégia.

Sor adatstruktúra létrehozása

A kiegészítő műveleteken kívül mondhatom, hogy a sorban lehetséges fő műveletek a következők:



egy. Sorban vagy adjon hozzá egy elemet a sor végéhez.

2. Leáll vagy távolítson el egy elemet a sor elejéről

Kezdjük a Class Queue létrehozásával a Pythonban:

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ rear = -1 self .__ front = 0
  • max_size a sorban várható elemek maximális száma.
  • A sor elemei a python listában vannak tárolva
  • hátul a sor utolsó elemének indexpozícióját jelzi.
  • A hátulról kezdetben -1-et vesznek, mert a sor üres
  • Az első jelzi a sor első elemének helyzetét.
  • Az elejét kezdetben 0-nak vesszük, mert mindig a sor első elemére mutat

Enqueue

Most, amikor elemeket próbál felvenni a sorba, emlékeznie kell a következő pontokra:

  • Akár van hely a sorban, akár nincs, azaz ha a hátsó megegyezik a max_méret -1 értékkel
  • A hátlap a sorba utoljára beillesztett elemre mutat.

Szóval, mi lesz az algoritmus ??

#returns max_size of que def def get_max_size (self): return self .__ max_size #return bool value függetlenül attól, hogy a sor tele van-e vagy sem, Igaz, ha teljes és Hamis egyébként def is_full (self): return self .__ rear == self .__ max_size-1 # beszúrja / beágyazza az adatokat a sorba, ha azok nem teljesek def enqueue (én, adatok): if (self.is_full ()): print ('A várólista megtelt. Nem lehetséges enqueue') egyéb: self .__ rear + = 1 self. __elements [self .__ rear] = data # a sor teljes tartalmának megjelenítése (saját): az i tartományban (0, self .__ hátsó + 1): print (self .__ elemek [i]) # Használhatja a __str __ () alatt a DS objektum elemeinek kinyomtatásához a def __str __ (self) hibakeresés közben: 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

Most, amikor a következőket hajtja végre:

1. sor = Sor (5)

# Adja meg az összes szükséges elemet.

queue1.enqueue („A”)

queue1.enqueue („B”)

r programozási nyelvet használó vállalatok

queue1.enqueue („C”)

queue1.enqueue („D”)

queue1.enqueue („E”)

queue1.display ()

queue1.enqueue („F”)

nyomtatás (1. sor)

Kimenet:

NAK NEK

B

C

D

IS

A várólista megtelt. Enqueue nem lehetséges

Várakozási adatok (elöl és hátul): A B C D E

De-Queue

Most, amikor beillesztette / beillesztette az elemeket a sorba, elölről szeretné törölni / törölni őket, ezért ügyelnie kell a következőkre:

  • Vannak elemek a sorban, vagyis a hátsó nem lehet egyenlő -1-vel.
  • Másodszor, emlékeznie kell arra, hogy mivel az elemeket elölről törlik, az elülső rész törlése után a következő előlapra kell növelni.
  • Az elülső rész ne mutasson a sor végére, vagyis ne legyen egyenlő a max_size értékkel.

Szóval, mi lesz az algoritmus ??

# function annak ellenőrzésére, hogy a sor üres-e vagy sem, def is_empty (self): if (self .__ rear == - 1 vagy self .__ front == self .__ max_size): return True else: return False # function egy elem visszavonásához és visszatéréshez def definiálja (önmagát): if (self.is_empty ()): print ('a sor már üres') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data # function to display elemek elölről hátra, ha a sor nem üres def kijelzés (self): if (nem self.is_empty ()): az i tartományban (self .__ front, self .__ rear + 1): print (self .__ elemek [i]) else : nyomtatás ('üres sor')

Most, amikor végrehajtja a következőket:

1. sor = Sor (5)

# Minden szükséges elem (ek) beírása

queue1.enqueue („A”)

queue1.enqueue („B”)

queue1.enqueue („C”)

queue1.enqueue („D”)

queue1.enqueue („E”)

nyomtatás (1. sor)

#Dequeue az összes szükséges elem (ek)

nyomtatás („Dequeued:“, queue1.dequeue ())

nyomtatás („Dequeued:“, queue1.dequeue ())

nyomtatás („Dequeued:“, queue1.dequeue ())

nyomtatás („Dequeued:“, queue1.dequeue ())

nyomtatás („Dequeued:“, queue1.dequeue ())

nyomtatás („Dequeued:“, queue1.dequeue ())

# Jelenítse meg a várólista összes elemét.

queue1.display ()

Kimenet:

Várakozási adatok (elöl és hátul): A B C D E

Dequeued: A

Dequeued: B

Dequeued: C

Dequeued: D

Dequeued: E

a sor már üres

Dequeued: Nincs

üres sor

A várólista alkalmazásai

Mostantól már megértette a várakozás alapjait. A mélyebb merüléshez megvizsgáljuk néhány alkalmazását.

  • 1. példa:

Nyomtatási sor a Windows rendszerben várólistát használ az összes aktív és függőben lévő nyomtatási feladat tárolásához. Amikor dokumentumokat akarunk kinyomtatni, egymás után adunk ki nyomtatási parancsokat. A nyomtatási parancsok alapján a dokumentumok sorba kerülnek a nyomtatási sorban. Amikor a nyomtató készen áll, a dokumentumot először az első kimenetben küldi be, hogy kinyomtassa.

Tegyük fel, hogy a doc1 sorrendben 3 dokumentumra adott ki nyomtatási parancsot, amelyet a doc2 és a doc3 követ.
A nyomtatási sor az alábbiak szerint kerül feltöltésre:

doc-n, ahol a doc a nyomtatásra elküldött dokumentum, és n, a dokumentum oldalainak száma. Például a doc2-10 azt jelenti, hogy a doc2-t ki kell nyomtatni, és 10 oldala van. Itt van egy kód, amely a nyomtatási sor működését szimulálja. Keresse meg a kódot, és figyelje meg, hogyan használják a várólistát ebben a megvalósításban.

class Queue: 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 (én, adatok): if (self.is_full ()): print ('A várólista megtelt !!!') else: self .__ rear + = 1 self .__ elements [self .__ rear] = data def dequeue (self): if (self.is_empty ()): print ('A sor üres! !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return data def display (self): index tartományban (self .__ front, self .__ rear + 1): print (self .__ elements [index]) def get_max_size (self): return self .__ max_size #Az alábbi __str __ () segítségével nyomtathatja ki a DS objektum elemeit, míg a #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()

Kimenet:

doc1-5 nyomtatásra elküldve

nyomtatásra elküldte a doc2-3-at

a doc3-6 nyomtatásra elküldve

doc1-5 nyomtatva

Fennmaradó sz. oldalak nyomtatón: 7

doc2-3 nyomtatva

Fennmaradó sz. oldalak nyomtatón: 4

Nem sikerült kinyomtatni a doc3 fájlt. Nincs elég oldal a nyomtatóban

  • 2. példa:

Próbáljunk megérteni egy másik példát, amely a Queue adatszerkezetét használja. Megpróbálhatja megérteni a kódot, és elmondani, hogy a következő függvény mit csinál?

  1. def fun (n):
  2. aqueue = várólista (100)
  3. tartományon belüli számokra (1, n + 1):
  4. sor (szám)
  5. eredmény = 1
  6. míg (nem (aqueue.is_empty ())):
  7. szám = AQUUE.DEQUEUE ()
  8. eredmény * = szám
  9. nyomtatás (eredmény)

Ha a fun () függvényt n elhalasztásával hívjuk meg,

  • a 2–4. sor sorba állítja az elemeket 1-től n-ig
  • az 5–8. sor úgy találja meg az elemek szorzatát, hogy egyesével sorba állítja

Ezzel véget értünk a várólista adatszerkezetről szóló cikknek. Ha sikeresen megértetted és futtattad magad a kódokat, akkor már nem vagy kezdő a várólista adatstruktúrájában.

Van egy kérdésünk? Kérjük, említse meg a cikk megjegyzés rovatában, és a lehető leghamarabb kapcsolatba lépünk Önnel.

Ha részletes ismereteket szeretne szerezni a Pythonról és annak különböző alkalmazásokról, regisztrálhat élőben 24/7 támogatással és élethosszig tartó hozzáféréssel.