Šioje pamokoje sužinosite, kas yra eilė. Taip pat rasite eilės įgyvendinimą C, C ++, Java ir Python.
Eilė yra naudinga duomenų struktūra programuojant. Tai panašu į bilietų eilę už kino salės, kur pirmasis įeinantis į eilę yra pirmasis, kuris gauna bilietą.
Eilė vadovaujasi „ First In First Out“ (FIFO) taisykle - pirmas dalykas yra tas, kuris išeina pirmas.
FIFO atstovavimas eilėje
Ankstesniame paveikslėlyje, kadangi 1 buvo laikomas eilėje iki 2, jis taip pat pirmasis pašalinamas iš eilės. Tai atitinka FIFO taisyklę.
Programavimo požiūriu elementų įdėjimas į eilę vadinamas „ enqueue“ , o elementų pašalinimas iš eilės - „ dequeue“ .
Eilę galime įdiegti bet kuria programavimo kalba, pvz., C, C ++, Java, Python ar C #, tačiau specifikacija yra beveik tokia pati.
Pagrindinės eilės operacijos
Eilė yra objektas (abstrakti duomenų struktūra - ADT), leidžiantis atlikti šias operacijas:
- Enqueue : pridėkite elementą prie eilės pabaigos
- Ištrinti : pašalinkite elementą iš eilės priekio
- „IsEmpty“ : patikrinkite, ar eilė tuščia
- „IsFull“ : patikrinkite, ar eilė pilna
- Žvilgtelėti : Gaukite eilės priekinės dalies vertės nepašalindami
Eilės darbas
Eilės operacijos veikia taip:
- du rodyklės Priekinė ir Užpakalinė
- „FRONT“ seka pirmąjį eilės elementą
- REAR sekti paskutinį eilės elementą
- iš pradžių nustatykite FRONT ir REAR vertę į -1
Enqueue operacija
- patikrinkite, ar eilė pilna
- pirmajam elementui nustatykite FRONT reikšmę 0
- padidinti REAR indeksą 1
- pridėkite naują elementą į vietą, į kurią nukreipia REAR
„Dequeue“ operacija
- patikrinkite, ar eilė tuščia
- grąžinkite FRONT nurodytą vertę
- padidinkite FRONT indeksą 1
- paskutiniam elementui nustatykite FRONT ir REAR reikšmes į -1
Enqueue ir Dequeue operacijos
Eilių diegimas Python, Java, C ir C ++
Dažniausiai naudojame masyvus, kad įdiegtume eiles „Java“ ir „C / ++“. „Python“ atveju mes naudojame sąrašus.
„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; )
Eilės apribojimai
Kaip matote paveikslėlyje žemiau, šiek tiek pritraukus ir nuleidžiant, eilės dydis sumažėjo.
Eilės ribojimas
Indeksus 0 ir 1 galime pridėti tik tada, kai eilė nustatoma iš naujo (kai visi elementai yra panaikinti).
Kai REAR pasieks paskutinį indeksą, jei tuščiose vietose (0 ir 1) galime laikyti papildomų elementų, galime panaudoti tuščias vietas. Tai įgyvendina modifikuota eilė, vadinama žiedine.
Sudėtingumo analizė
Enqueue ir dequeue operacijų sudėtingumas eilėje naudojant masyvą yra O(1).
Eilės programos
- Procesoriaus planavimas, disko planavimas
- Kai duomenys perduodami asinchroniškai tarp dviejų procesų. Eilė naudojama sinchronizavimui. Pavyzdžiui: IO buferiai, vamzdžiai, failų IO ir kt
- Pertraukimų tvarkymas realaus laiko sistemose.
- Skambučių centro telefono sistemos naudoja eiles, kad sutvarkytų jiems skambinančius žmones.
Rekomenduojami skaitiniai
- Eilės tipai
- Žiedinė eilė
- „Deque“ duomenų struktūra
- Pirmenybės eilė
