Līdzīgi kā Queue ir lineāra datu struktūra, kas atbilst noteiktai secībai, kādā tiek veiktas datu glabāšanas darbības. Pasūtījums ir pirmais iekšā pirmais (FIFO) . Var iedomāties rindu kā cilvēku rindu, kas gaida, lai kaut ko saņemtu secīgā secībā, kas sākas no rindas sākuma. Tas ir sakārtots saraksts, kurā ievietošana tiek veikta vienā galā, ko sauc par aizmuguri, un svītrojumi tiek veikti no otra gala, kas pazīstams kā priekšpuse. Labs rindas piemērs ir jebkura resursa patērētāju rinda, kurā pirmais tiek apkalpots patērētājs, kurš bija pirmais.
Atšķirība starp skursteņiem un rindām ir noņemšana. Kaudzē mēs noņemam pēdējo pievienoto vienumu; rindā, mēs noņemam vienumu, kas tika pievienots vismazāk.
Rindas Datu struktūra
semantiskā kļūda
Pamatdarbības rindā:
- enqueue(): ievieto elementu rindas beigās, t.i., aizmugurē. dequeue (): šī darbība noņem un atgriež elementu, kas atrodas rindas priekšgalā. front (): šī darbība atgriež elementu priekšpusē, to nenoņemot. rear (): šī darbība atgriež elementu aizmugurē, to nenoņemot. isEmpty(): šī darbība norāda, vai rinda ir tukša vai nav. isFull(): šī darbība norāda, vai rinda ir pilna vai nē. size(): šī darbība atgriež rindas lielumu, t.i., kopējo tajā esošo elementu skaitu.
Rindu veidi:
- Vienkāršā rinda: vienkārša rinda, kas pazīstama arī kā lineārā rinda, ir rindas visvienkāršākā versija. Šeit elementa ievietošana, t.i., rindošanas darbība, notiek aizmugurē, un elementa noņemšana, t.i., darbība rindā tiek veikta priekšgalā. Problēma ir tāda, ka, ja mēs paceļam kādu vienumu no priekšpuses un pēc tam aizmugures, sasniedzot rindas ietilpību, un, lai gan priekšā ir tukšas vietas, tas nozīmē, ka rinda nav pilna, bet saskaņā ar nosacījumu funkcijai isFull(), tas parādīs, ka tad rinda ir pilna. Lai atrisinātu šo problēmu, mēs izmantojam apļveida rindu.
- Apļveida rinda : Apļveida rindā rindas elements darbojas kā apļveida gredzens. Apļveida rindas darbība ir līdzīga lineārajai rindai, izņemot to, ka pēdējais elements ir savienots ar pirmo elementu. Tās priekšrocība ir tā, ka atmiņa tiek izmantota labāk. Tas ir tāpēc, ka, ja ir tukša vieta, t.i., ja rindā noteiktā vietā nav neviena elementa, elementu var viegli pievienot šajā pozīcijā, izmantojot modulo kapacitāti ( %n ).
- Prioritātes rinda : Šī rinda ir īpašs rindas veids. Tās īpatnība ir tāda, ka tā sakārto elementus rindā, pamatojoties uz kādu prioritāti. Prioritāte var būt tāda, kurā prioritāte ir elementam ar visaugstāko vērtību, tāpēc tas veido rindu ar dilstošu vērtību secību. Prioritāte var būt arī tāda, ka elements ar viszemāko vērtību iegūst augstāko prioritāti, tādējādi tas savukārt veido rindu ar pieaugošu vērtību secību. Iepriekš definētā prioritātes rindā C++ piešķir prioritāti augstākajai vērtībai, savukārt Java dod prioritāti zemākajai vērtībai.
- Attiecīgi : Rinda ir pazīstama arī kā Double Ended Queue. Kā norāda nosaukums ar dubultgaliem, tas nozīmē, ka elementu var ievietot vai noņemt no abiem rindas galiem, atšķirībā no citām rindām, kurās to var izdarīt tikai no viena gala. Šīs īpašības dēļ tas var neatbilst rekvizītam First In First Out.
Rindas lietojumprogrammas:
Rinda tiek izmantota, ja lietas nav nekavējoties jāapstrādā, bet tās ir jāapstrādā F pirmkārt es n F pirmkārt O ut pasūtiet patīk Platuma pirmā meklēšana . Šis rindas īpašums padara to noderīgu arī šādos scenārijos.
- Ja resurss tiek koplietots starp vairākiem patērētājiem. Piemēri: CPU plānošana, diska plānošana. Kad dati tiek pārsūtīti asinhroni (dati ne vienmēr tiek saņemti tādā pašā ātrumā kā nosūtīti) starp diviem procesiem. Piemēri ir IO buferi, caurules, fails IO utt. Rinda var tikt izmantota kā būtiska sastāvdaļa dažādās citās datu struktūrās.
Rindas masīva ieviešana:
Lai ieviestu rindu, mums ir jāseko līdzi diviem indeksiem, priekšējam un aizmugurējam. Mēs ievietojam vienumu rindā aizmugurē, bet no priekšpuses. Ja mēs vienkārši palielināsim priekšējo un aizmugurējo indeksu, tad var rasties problēmas, priekšpuse var sasniegt masīva galu. Šīs problēmas risinājums ir palielināt priekšējo un aizmugurējo daļu apļveida veidā.
Soļi, lai izveidotu rindu:
- Pārbaudiet, vai rinda ir pilna
- Ja tas ir pilns, izdrukājiet pārpildījumu un izejiet
- Ja rinda nav pilna, palieliniet līdz un pievienojiet elementu
Darbības, lai pārtrauktu rindu:
- Pārbaudiet, vai rinda ir tukša vai nav
- ja tas ir tukšs, izdrukājiet apakšpildu un izejiet
- ja tas nav tukšs, drukājiet elementu galvā un palieliniet galviņu
Zemāk ir programma, lai ieviestu iepriekš minēto darbību rindā
C++
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->jauda = jauda;> >queue->priekšā = rinda->izmērs = 0;> >// This is important, see the enqueue> >queue->aizmugure = ietilpība - 1;> >queue->masīvs =>new> int>[queue->jauda];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->izmērs == rinda->kapacitāte);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->izmērs == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->aizmugure = (rinda->aizmugure + 1)> >% queue->jauda;> >queue->masīvs[rinda->aizmugure] = vienums;> >queue->izmērs = rinda->izmērs + 1;> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->masīvs[rinda->priekšpuse];> >queue->front = (rinda->priekšpuse + 1)> >% queue->jauda;> >queue->izmērs = rinda->izmērs - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masīvs[rinda->priekšpuse];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masīvs[rinda->aizmugure];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->jauda = jauda;> >queue->priekšā = rinda->izmērs = 0;> >// This is important, see the enqueue> >queue->aizmugure = ietilpība - 1;> >queue->masīvs = (>int>*)>malloc>(> >queue->ietilpība *>>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->izmērs == rinda->kapacitāte);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->izmērs == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->aizmugure = (rinda->aizmugure + 1)> >% queue->jauda;> >queue->masīvs[rinda->aizmugure] = vienums;> >queue->izmērs = rinda->izmērs + 1;> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->masīvs[rinda->priekšpuse];> >queue->front = (rinda->priekšpuse + 1)> >% queue->jauda;> >queue->izmērs = rinda->izmērs - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masīvs[rinda->priekšpuse];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masīvs[rinda->aizmugure];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
>
Java
java
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
>
Javascript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
>Izvade
python inicializācijas saraksts
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
Sarežģītības analīze:
- Laika sarežģītība
| Operācijas | Sarežģītība |
|---|---|
| Rinda (ievietošana) | O(1) |
| Deque (dzēšana) | O(1) |
| Priekšpuse (esiet priekšā) | O(1) |
| Aizmugure (aizmugure) | O(1) |
| IsFull (pārbaudiet, vai rinda ir pilna vai nav) | O(1) |
| IsEmpty (pārbaudiet, vai rinda ir tukša vai nav) | O(1) |
- Palīgtelpa:
O(N), kur N ir elementu glabāšanas masīva lielums.
Masīva ieviešanas priekšrocības:
- Viegli īstenojams.
- Lielu datu apjomu var viegli pārvaldīt efektīvi.
- Tādas darbības kā ievietošana un dzēšana var veikt viegli, jo tiek ievērots noteikums pirmais pirmais ārā.
Masīva ieviešanas trūkumi:
- Statiskā datu struktūra, fiksēts izmērs.
- Ja rindā ir liels skaits rindas un rindas operāciju, kādā brīdī (priekšējo un aizmugurējo indeksu lineāra pieauguma gadījumā) mēs varam nevarēs ievietot rindā elementus pat tad, ja rinda ir tukša (šī problēma tiek novērsta izmantojot apļveida rindu).
- Maksimālais rindas lielums ir jādefinē iepriekš.