Tässä opetusohjelmassa opit jonon olevan. Lisäksi löydät jonon toteutuksen C, C ++, Java ja Python.
Jono on hyödyllinen tietorakenne ohjelmoinnissa. Se on samanlainen kuin lippujono elokuvateatterisalin ulkopuolella, jossa jonoon saapuu ensimmäinen henkilö, joka saa lipun.
Jono noudattaa First In First Out (FIFO) -sääntöä - ensin menevä kohde on ensin tuleva kohde.
FIFO-jonon esitys
Yllä olevassa kuvassa, koska 1 pidettiin jonossa ennen 2, se poistetaan myös ensimmäiseksi jonosta. Se noudattaa FIFO- sääntöä.
Ohjelmoinnissa kannalta, mikä kohteita jonossa on nimeltään enqueue ja poistamalla kohteita jonosta kutsutaan dequeue .
Voimme toteuttaa jonon millä tahansa ohjelmointikielellä, kuten C, C ++, Java, Python tai C #, mutta määrittely on melkein sama.
Jonon perustoiminnot
Jono on objekti (abstrakti tietorakenne - ADT), joka sallii seuraavat toiminnot:
- Enqueue : Lisää elementti jonon loppuun
- Irrota : Poista elementti jonon etuosasta
- IsEmpty : Tarkista, onko jono tyhjä
- IsFull : Tarkista, onko jono täynnä
- Kurkistus : Hanki jonon etuosan arvo poistamatta sitä
Jonon toiminta
Jonotoiminnot toimivat seuraavasti:
- kaksi osoitinta ETU ja TAKA
- FRONT seuraa jonon ensimmäistä osaa
- TAKA seuraa jonon viimeinen elementti
- aseta ensin FRONT- ja REAR-arvoksi -1
Saavuta toiminta
- tarkista onko jono täynnä
- Aseta ensimmäisen elementin arvoksi FRONT arvoksi 0
- nosta REAR-indeksiä yhdellä
- lisää uusi elementti kohtaan REAR
Dequeue-käyttö
- tarkista onko jono tyhjä
- palauta FRONTin osoittama arvo
- lisää FRONT-indeksiä yhdellä
- palauta viimeisen elementin FRONT- ja REAR-arvot arvoon -1
Enqueue- ja Dequeue-toiminnot
Jonototeutukset Pythonissa, Java: ssa, C: ssä ja C ++: ssa
Käytämme yleensä taulukoita jonojen toteuttamiseen Java- ja C / ++ -järjestelmissä. Pythonin tapauksessa käytämme luetteloita.
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; )
Jonon rajoitukset
Kuten alla olevasta kuvasta näet, jonon kokoa on pienennetty jonkin verran kiinnittämisen ja purkamisen jälkeen.
Jonon rajoittaminen
Ja indeksit 0 ja 1 voidaan lisätä vain, kun jono nollataan (kun kaikki elementit on purettu).
Kun REAR on saavuttanut viimeisen indeksin, jos voimme tallentaa ylimääräisiä elementtejä tyhjiin tiloihin (0 ja 1), voimme käyttää tyhjiä tiloja. Tämä toteutetaan muokatulla jonolla, jota kutsutaan pyöreäksi jonoksi.
Monimutkaisuusanalyysi
Matriisin avulla jonossa olevien enqueue- ja dequeue-toimintojen monimutkaisuus on O(1).
Jonon sovellukset
- Suorittimen ajoitus, levyn ajoitus
- Kun tietoja siirretään asynkronisesti kahden prosessin välillä, synkronointiin käytetään jonoa. Esimerkiksi: IO-puskurit, putket, tiedosto IO jne
- Keskeytysten käsittely reaaliaikaisissa järjestelmissä.
- Puhelinkeskuksen puhelinjärjestelmät käyttävät jonoja pitääkseen heitä soittavat järjestyksessä.
Suositeltavat lukemat
- Jonon tyypit
- Pyöreä jono
- Deque-tietorakenne
- Prioriteettijono
