Šajā apmācībā jūs uzzināsiet, kas ir rinda. Turklāt jūs atradīsit rindas ieviešanu C, C ++, Java un Python.
Rinda ir noderīga datu struktūra programmēšanā. Tas ir līdzīgs biļešu rindai ārpus kinozāles, kur pirmais, kurš ierodas rindā, ir pirmais, kurš saņem biļeti.
Rinda seko noteikumam First In First Out (FIFO) - vienums, kas iet vispirms, ir tas, kas iznāk pirmais.
FIFO rindas attēlojums
Iepriekš minētajā attēlā, tā kā 1 tika turēts rindā pirms 2, tas ir pirmais, kas tiek noņemts arī no rindas. Tas atbilst FIFO noteikumam.
Programmēšanas ziņā priekšmetu ievietošana rindā tiek saukta par enqueue , bet priekšmetu noņemšana no rindas - par dequeue .
Mēs varam ieviest rindu jebkurā programmēšanas valodā, piemēram, C, C ++, Java, Python vai C #, taču specifikācija ir gandrīz vienāda.
Rindas pamatdarbības
Rinda ir objekts (abstrakta datu struktūra - ADT), kas ļauj veikt šādas darbības:
- Enqueue : pievienojiet elementu rindas beigās
- Dequeue : Noņemiet elementu no rindas priekšpuses
- IsTukšs : pārbaudiet, vai rinda nav tukša
- IsFull : pārbaudiet, vai rinda ir pilna
- Palūrēt : iegūstiet rindas priekšpuses vērtību, to nenoņemot
Darbojas rindā
Rindas darbības darbojas šādi:
- divi rādītāji FRONT un REAR
- FRONT izsekot rindas pirmajam elementam
- REAR izsekot rindas pēdējam elementam
- sākotnēji iestatiet vērtību FRONT un REAR uz -1
Enqueue darbība
- pārbaudiet, vai rinda ir pilna
- pirmajam elementam iestatiet FRONT vērtību 0
- palielināt REAR indeksu par 1
- pievienojiet jauno elementu pozīcijā, uz kuru norāda REAR
Dequeue darbība
- pārbaudiet, vai rinda nav tukša
- atgrieziet FRONT norādīto vērtību
- palieliniet FRONT indeksu par 1
- pēdējam elementam iestatiet FRONT un REAR vērtības uz -1
Enqueue un Dequeue operācijas
Rindas ieviešana Python, Java, C un C ++
Mēs parasti izmantojam masīvus, lai ieviestu rindas Java un C / ++. Python gadījumā mēs izmantojam sarakstus.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #define SIZE 5 using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) bool isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear++; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) int deQueue() ( int element; if (isEmpty()) ( cout << "Queue is empty" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Rindas ierobežojumi
Kā redzams zemāk redzamajā attēlā, pēc nelielas pievilināšanas un atslābināšanas rindas lielums ir samazināts.
Rindas ierobežošana
Un indeksus 0 un 1 mēs varam pievienot tikai tad, kad rinda ir atiestatīta (kad visi elementi ir atcelti).
Kad REAR sasniedz pēdējo indeksu, ja tukšos laukumos (0 un 1) varam uzglabāt papildu elementus, mēs varam izmantot tukšās vietas. To īsteno modificēta rinda, ko sauc par apļveida rindu.
Sarežģītības analīze
Enqueue un dequeue operāciju sarežģītība rindā, izmantojot masīvu, ir O(1).
Rindas pieteikumi
- CPU plānošana, diska plānošana
- Kad dati tiek asinhroni pārsūtīti starp diviem procesiem. Sinhronizēšanai tiek izmantota rinda. Piemēram: IO buferi, caurules, failu IO utt
- Pārtraukumu apstrāde reāllaika sistēmās.
- Zvanu centra tālruņu sistēmas izmanto rindas, lai uzturētu kārtībā cilvēkus, kuri viņiem zvana.
Ieteicamie lasījumi
- Rindas veidi
- Apļveida rinda
- Deque datu struktūra
- Prioritārā rinda
