Selles õpetuses saate teada, mis on järjekord. Samuti leiate järjekorra rakendamise C, C ++, Java ja Python.
Järjekord on programmeerimisel kasulik andmestruktuur. See sarnaneb piletijärjekorraga kinosaali taga, kus esimene järjekorda astuja on esimene, kes pileti saab.
Järjekord järgib reeglit First In First Out (FIFO) - esimene, mis läheb sisse, on see, mis tuleb esimesena välja.
FIFO järjekorra esitus
Kuna ülaloleval pildil hoiti 1 järjekorras enne 2, eemaldatakse see ka esimesena järjekorrast. See järgib FIFO reeglit.
In programmeerimine poolest, pannes objekte järjekorras nimetatakse Lisa järjekorda ja elementide eemaldamine järjekorda nimetatakse dequeue .
Saame järjekorra rakendada mis tahes programmeerimiskeeles, nagu C, C ++, Java, Python või C #, kuid spetsifikatsioon on üsna sama.
Järjekorra põhitoimingud
Järjekord on objekt (abstraktne andmestruktuur - ADT), mis võimaldab järgmisi toiminguid:
- Enqueue : lisage järjekorra lõppu element
- Dequeue : eemaldage järjekorra esiosast element
- IsEmpty : kontrollige, kas järjekord on tühi
- IsFull : kontrollige, kas järjekord on täis
- Peek : hankige järjekorra esikülje väärtus seda eemaldamata
Järjekorra töötamine
Järjekorratoimingud toimivad järgmiselt:
- kaks osutit ESI ja TAGA
- FRONT jälgib järjekorra esimest elementi
- TAGASI jälgi järjekorra viimast elementi
- alguses määrake FRONT ja REAR väärtus väärtuseks -1
Rakenda operatsiooni
- kontrollige, kas järjekord on täis
- esimese elemendi jaoks määrake FRONT väärtuseks 0
- tõsta REAR indeksit 1 võrra
- lisage uus element asendisse, millele REAR osutab
Dequeue'i operatsioon
- kontrollige, kas järjekord on tühi
- tagastab väärtuse, mille osutas FRONT
- suurendage FRONT indeksit 1 võrra
- viimase elemendi jaoks lähtestage FRONT ja REAR väärtused väärtusele -1
Enqueue ja Dequeue toimingud
Järjekordade rakendused Pythonis, Java-s, C-s ja C ++ -s
Tavaliselt kasutame massiive Java ja C / ++ järjekordade loomiseks. Pythoni puhul kasutame loendeid.
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; )
Järjekorra piirangud
Nagu näete alloleval pildil, on pärast mõningast kinnitamist ja mahavõtmist järjekorra suurust vähendatud.
Järjekorra piiramine
Ja indeksid 0 ja 1 saame lisada ainult siis, kui järjekord on lähtestatud (kui kõik elemendid on eemaldatud).
Kui REAR jõuab viimase indeksini, saame tühjadesse ruumidesse (0 ja 1) salvestada täiendavaid elemente, siis saame tühjad ruumid ära kasutada. Selle teostab modifitseeritud järjekord, mida nimetatakse ringjärjekorraks.
Keerukuse analüüs
Massiivi kasutades on järjekorras enqueue ja dequeue toimingute keerukus O(1).
Järjekorra rakendused
- Protsessori ajastamine, ketta ajastamine
- Kui andmeid edastatakse asünkroonselt kahe protsessi vahel. Sünkroonimiseks kasutatakse järjekorda. Näiteks: IO puhvrid, torud, faili IO jne
- Katkestuste käsitlemine reaalajas süsteemides.
- Kõnekeskuse telefonisüsteemid kasutavad järjekordi, et inimesi neile helistada.
Soovitatavad lugemised
- Järjekorra tüübid
- Ringjärjekord
- Deque andmete struktuur
- Prioriteedijärjekord
