Tāpat kā kaudze, rinda ir lineāra datu struktūra, kas glabā vienumus mapē First In First Out ( FIFO ) veidā. Ja ir rinda, vispirms tiek noņemts vismazāk pievienotais vienums. Labs rindas piemērs ir jebkura resursa patērētāju rinda, kurā pirmais tiek apkalpots patērētājs, kurš bija pirmais.

Ar rindu saistītās darbības ir:

• Rinda: Pievieno vienumu rindai. Ja rinda ir pilna, tiek uzskatīts, ka tas ir pārpildes nosacījums — laika sarežģītība: O(1)
• Attiecīgi: Noņem vienumu no rindas. Vienumi tiek izspiesti tādā pašā secībā, kādā tie tiek stumti. Ja rinda ir tukša, tiek uzskatīts, ka tas ir nepietiekamas plūsmas nosacījums — laika sarežģītība: O(1)
• Priekšpuse: Saņemt priekšējo vienumu no rindas — laika sarežģītība: O(1)
• Aizmugure: Saņemt pēdējo vienumu no rindas — laika sarežģītība: O(1)

Ieviesiet rindu Python

Ir dažādi veidi, kā ieviest rindu Python. Šajā rakstā ir aprakstīta rindas ieviešana, izmantojot Python bibliotēkas datu struktūras un moduļus. Python Queue var ieviest šādos veidos:

• sarakstu
• kolekcijas.deque
• aste.aste

Īstenošana, izmantojot sarakstu

Saraksts ir Python iebūvēta datu struktūra, ko var izmantot kā rindu. enqueue() un vietā attiecīgi () , pievienot () un pop () funkcija tiek izmantota. Tomēr saraksti šim nolūkam ir diezgan lēni, jo elementa ievietošana vai dzēšana sākumā prasa visu pārējo elementu nobīdi par vienu, kas prasa O(n) laiku.
Kods simulē rindu, izmantojot Python sarakstu. Tas pievieno elementus 'a' , 'b' , un 'c' uz rindu un pēc tam noņem tos no rindas, kā rezultātā rinda beigās ir tukša. Izvadā tiek parādīta sākotnējā rinda, elementi, kas izslēgti no rindas ( 'a' , 'b' , 'c' ), un rindas stāvoklis ir tukšs.

Python3

Izvade:

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 

Īstenošana, izmantojot collections.deque

Rinda Python var ieviest, izmantojot deque klasi no kolekcijas moduļa. Deque ir priekšroka, nevis saraksts gadījumos, kad mums ir nepieciešamas ātrākas pievienošanas un pop operācijas no abiem konteinera galiem, jo ​​deque nodrošina O(1) laika sarežģītību pievienošanas un pop operācijām, salīdzinot ar sarakstu, kas nodrošina O(n) laika sarežģītību. . Enqueue un deque vietā tiek izmantotas funkcijas append() un popleft().
Kods izmanto a deque> no collections> modulis, lai attēlotu rindu. Tas pievieno 'a' , 'b' , un 'c' uz rindu un nokārto tos ar q.popleft()> , kā rezultātā rinda ir tukša. Nekomentējot q.popleft()> pēc tam, kad rinda ir tukša, tiktu paaugstināts an IndexError> . Kods parāda rindas darbības un apstrādā tukšas rindas scenāriju.

Python3

Izvade:

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 

Īstenošana, izmantojot queue.Queue

Rinda ir iebūvēts Python modulis, kas tiek izmantots rindas ieviešanai. queue.Queue(maxsize) inicializē mainīgo līdz maksimālajam izmēram maxsize. Nulles maksimālais lielums “0” nozīmē bezgalīgu rindu. Šī rinda atbilst FIFO likumam.
Šajā modulī ir pieejamas dažādas funkcijas:

• maksimālais izmērs – rindā atļauto vienumu skaits.
• tukšs () – Atgrieziet True, ja rinda ir tukša, vai False pretējā gadījumā.
• pilns () – Atgrieziet vērtību True, ja rindā ir maksimālie vienumi. Ja rinda tika inicializēta ar maxsize=0 (noklusējums), tad full() nekad neatgriež True.
• gūt() – Noņemiet un atgrieziet preci no rindas. Ja rinda ir tukša, pagaidiet, līdz prece ir pieejama.
• get_nowait() – Atgrieziet preci, ja tāda ir uzreiz pieejama, pretējā gadījumā paaugstiniet QueueEmpty.
• likt (prece) – Ievietojiet preci rindā. Ja rinda ir pilna, pirms preces pievienošanas uzgaidiet, līdz ir pieejama brīva vieta.
• put_nowait(prece) – Ievietojiet vienumu rindā bez bloķēšanas. Ja uzreiz nav pieejams neviens brīvs slots, paaugstiniet QueueFull.
• qsize() – Atgriezt rindā esošo vienumu skaitu.

Piemērs: Šis kods izmanto Queue> klase no queue> modulis. Tas sākas ar tukšu rindu un aizpilda to ar ' a’, 'b' , un 'c' . Pēc rindas noņemšanas rinda kļūst tukša, un tiek pievienots “1”. Neskatoties uz to, ka tas agrāk bija tukšs, tas joprojām ir pilns, jo maksimālais lielums ir iestatīts uz 3. Kods parāda rindas darbības, tostarp pārbauda, ​​vai tā ir pilna un tukša.

Python3

Izvade:

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