Què és l'estructura de dades de la cua a Python?



Aquest article us proporcionarà un coneixement detallat i complet de les estructures de dades de la cua a Python amb molts exemples.

Com ja heu estudiat sobre la importància de les estructures de dades a l’article anterior, aprofundim en el tema de l’article, és a dir, Estructura de dades de cua. Parlaré dels temes següents:

Necessitat d’estructura de dades de cua

Suposem que voleu una pel·lícula un dia. Al múltiplex, els bitllets es van emetre per ordre d’arribada primer i la gent estava parada darrere l’altre esperant el seu torn. Llavors, què faràs ?? Deu haver anat al darrere i estar darrere de l’última persona que esperava el bitllet.





queue-data-structure

Aquí, la gent està parada una darrere de l 'altra i es fa un servei basat en Primer entrada primer sortida (FIFO) mecanisme. Aquesta disposició es coneix com a Cua.



Exemples de cua de la vida quotidiana

Vegem alguns exemples de tipus de cua treballant a la vida diària:

  • Sistema de resposta telefònica- La persona que fa una primera trucada al vostre gadget és atesa primer.
  • Màquina de comprovar l’equipatge - Revisa l’equipatge que s’ha conservat primer a la cinta transportadora.
  • Vehicles al pont de peatge - Els vehicles que arriben aviat surten primer.
  • Centre de trucades - els sistemes de telefonia faran servir cues per mantenir en ordre les persones que els truquen, fins que un representant del servei sigui gratuït.

Tots aquests exemples segueixen Primera entrada-última sortida estratègia.

Creació d’una estructura de dades de cua

A part de les operacions complementàries, puc dir que les principals operacions possibles a la cua són:



1. En-queue o afegiu un element al final de la cua.

2. De-queue o traieu un element de la part frontal de la cua

Ara, comencem creant la cua de classe a Python:

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [Cap] * self .__ max_size self .__ posterior = -1 self .__ front = 0
  • mida_màxima és el nombre màxim d'elements que s'espera a la cua.
  • Els elements de la cua s’emmagatzemen a la llista de pitons
  • posterior indica la posició de l'índex de l'últim element a la cua.
  • La part posterior es considera inicialment -1 perquè la cua està buida
  • Front indica la posició del primer element a la cua.
  • Es considera que la part frontal és inicialment 0 perquè sempre apuntarà al primer element de la cua

Feu una cua

Ara, quan proveu de posar elements a la cua, heu de recordar els punts següents:

  • Tant si queda espai a la cua com si no, és a dir, si la part posterior és igual a max_size -1
  • La part posterior assenyalarà l'últim element inserit a la cua.

Llavors, quin serà l'algorisme ??

#returns max_size de la cua def get_max_size (self): torna self .__ max_size #returns bool value whether queue is full or not, True if full and False def is_full (self): return self .__ rear == self .__ max_size-1 # insereix / fa cua de dades a la cua si no és completa def enqueue (self, data): if (self.is_full ()): print ('La cua està plena. No hi ha cap fila possible') else: self .__ posterior + = 1 self. __elements [self .__ posterior] = dades # mostra tot el contingut de la pantalla de def de la cua (auto): per a l’interval (0, auto .__ posterior + 1): imprimir (auto .__ elements [i]) # Podeu utilitzar el a sota de __str __ () per imprimir els elements de l'objecte DS mentre es depura 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

Ara, quan executeu el següent:

subcadena en exemples de servidor sql

cua1 = cua (5)

#Colliu tots els elements necessaris.

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

queue1.enqueue ('E')

cua1.display ()

queue1.enqueue ('F')

imprimir (cua1)

Sortida:

A

B

C

D

ÉS

La cua està plena. No hi ha cap cua possible

Dades de cua (frontal a posterior): A B C D E

De-Queue

Ara, a mesura que heu inserit / posat en cua els elements a la cua, voleu deixar-los a la cua / suprimir-los de la part frontal, de manera que us heu de preocupar de fer el següent:

  • Hi ha elements a la cua, és a dir, la part posterior no ha de ser igual a -1.
  • En segon lloc, heu de recordar que, a mesura que s’eliminen els elements de la part frontal, així, després d’eliminar la part frontal, s’ha d’incrementar fins al punt següent.
  • La part frontal no ha d’apuntar el final de la cua, és a dir, igual a max_size.

Llavors, quin serà l'algorisme ??

#function per comprovar si la cua està buida o no def is_empty (self): if (self .__ posterior == - 1 o self .__ frontal == self .__ max_size): return True else: return False #function to deque a element and return def dequeue (self): if (self.is_empty ()): print ('la cua ja està buida') else: data = self .__ elements [self .__ front] self .__ front + = 1 retorna dades #funció per mostrar elements de de davant a darrere si la cua no està buida def display (auto): if (no self.is_empty ()): per a l’interval (self .__ frontal, self .__ posterior + 1): imprimir (self .__ elements [i]) else : print ('cua buida')

Ara, quan executeu el següent:

cua1 = cua (5)

#Colliu tots els elements necessaris

queue1.enqueue ('A')

queue1.enqueue ('B')

queue1.enqueue ('C')

queue1.enqueue ('D')

com analitzar XML a Java

queue1.enqueue ('E')

imprimir (cua1)

# Dequeu tots els elements necessaris

print ('Deueued:', queue1.dequeue ())

print ('Deueued:', queue1.dequeue ())

print ('Deueued:', queue1.dequeue ())

print ('Deueued:', queue1.dequeue ())

print ('Deueued:', queue1.dequeue ())

print ('Deueued:', queue1.dequeue ())

# Mostra tots els elements de la cua.

cua1.display ()

Sortida:

Dades de cua (frontal a posterior): A B C D E

En cua: A

Posat a la cua: B

Posat a la cua: C

Posat a la cua: D

Posat a la cua: E

la cua ja està buida

Posat a la cua: cap

cua buida

java té una relació

Aplicacions de la cua

A hores d’ara, ja heu entès els conceptes bàsics de la cua. Ara, per aprofundir-hi, analitzarem algunes de les seves aplicacions.

  • Exemple 1:

Cua d'impressió al Windows utilitza una cua per emmagatzemar tots els treballs d'impressió actius i pendents. Quan volem imprimir documents, emetem ordres d'impressió una darrere l'altra. Basant-se en les ordres d’impressió, els documents s’alinearan a la cua d’impressió. Quan la impressora estigui llesta, el document s'enviarà primer en primer lloc per imprimir-lo.

Suposem que heu emès comandes d'impressió per a 3 documents a l'ordre doc1, seguits de doc2 i doc3.
La cua d'impressió s'omplirà com es mostra a continuació:

doc-n, on el document és el document enviat per imprimir i n, és el nombre de pàgines del document. Per exemple, doc2-10 significa que s'ha d'imprimir doc2 i que té 10 pàgines. Aquí teniu un codi que simula l’operació de la cua d’impressió. Consulteu el codi i observeu com s’utilitza la cua en aquesta implementació.

class Queue: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [Cap] * self .__ max_size self .__ posterior = -1 self .__ front = 0 def is_full (self): if (self .__ posterior = = self .__ max_size-1): return True return False def is_empty (self): if (self .__ frontal> self .__ posterior): return True return False def enqueue (self, data): if (self.is_full ()): print ('La cua està plena !!!') else: self .__ posterior + = 1 self .__ elements [self .__ posterior] = def deueue de dades (self): if (self.is_empty ()): print ('La cua està buida!) !! ') else: data = self .__ elements [self .__ front] self .__ front + = 1 return display def display (self): per a índex en l'interval (self .__ frontal, self .__ posterior + 1): print (elements .__ [index]) def get_max_size (self): return self .__ max_size #Podeu utilitzar el següent __str __ () per imprimir els elements de l’objecte DS mentre #debugging def __str __ (self): msg = [] index = self .__ front while (índex<=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()

Sortida:

doc1-5 enviat per imprimir

doc2-3 enviat per imprimir

doc3-6 enviat per imprimir

imprès doc1-5

Queda el núm. de pàgines a la impressora: 7

imprès doc2-3

Queda el núm. de pàgines a la impressora: 4

No s'ha pogut imprimir doc3. No hi ha prou pàgines a la impressora

  • Exemple 2:

Intentem entendre un altre exemple que utilitza l'estructura de dades de la cua. Podeu intentar comprendre el codi i dir què fa la següent funció?

  1. diversió (n):
  2. aqueue = Cua (100)
  3. per a un número (1, n + 1):
  4. cola (núm)
  5. resultat = 1
  6. while (not (aqueue.is_empty ())):
  7. num = AQUUE.DEQUEUE ()
  8. resultat * = núm
  9. imprimir (resultat)

Quan la funció fun () s’invoca passant n,

  • les línies 2 a 4 fan cues als elements de l'1 al n
  • les línies 5 a 8 troben el producte d’aquests elements descuantant-lo en una a una

Amb això, arribem al final d’aquest article d’estructura de dades de cua. Si heu entès i executat els codis per vosaltres mateixos, ja no sou principiants de la cua de l'estructura de dades.

Tens alguna pregunta? Si us plau, mencioneu-lo a la secció de comentaris d’aquest article i us respondrem el més aviat possible.

Per obtenir coneixements en profunditat sobre Python juntament amb les seves diverses aplicacions, podeu inscriure-us a la publicació amb assistència les 24 hores del dia, els 7 dies de la setmana i accés permanent