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
- A mindennapi élet példái a várólistára
- Sor adatstruktúra létrehozása
- Sorban
- Leáll
- A várólista alkalmazásai
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.
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?
- def fun (n):
- aqueue = várólista (100)
- tartományon belüli számokra (1, n + 1):
- sor (szám)
- eredmény = 1
- míg (nem (aqueue.is_empty ())):
- szám = AQUUE.DEQUEUE ()
- eredmény * = szám
- 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.