Meni

Struktura podatkov čakalne vrste v jeziku C ++ z ilustracijo

  • Glavni
  • Drugo
  • Struktura podatkov čakalne vrste v jeziku C ++ z ilustracijo

queue data structure c with illustration

Preizkusite Naš Instrument Za Odpravo Težav

Kratek uvod v čakalno vrsto v C ++ z ilustracijo.

Čakalna vrsta je osnovna podatkovna struktura, tako kot sklad. V nasprotju s skladom, ki uporablja pristop LIFO, vrsta uporablja pristop FIFO (prvi vhod, prvi izhod). S tem pristopom je prvi element, ki je dodan v čakalno vrsto, prvi element, ki je odstranjen iz čakalne vrste. Tako kot Stack je vrsta tudi linearna podatkovna struktura.

najboljši brezplačni pc čistejši windows 7

V resnični analogiji si lahko predstavljamo čakalno vrsto avtobusa, kjer potniki čakajo na avtobus v čakalni vrsti ali vrsti. Prvi potnik v vrsti najprej vstopi v avtobus, saj je potnik tisti, ki je prišel prvi.

=> Tukaj preberite priljubljeno serijo usposabljanj za C ++.

Čakalna vrsta v jeziku C ++

Kaj se boste naučili:

Čakalna vrsta v C ++

V programskem smislu je čakalno vrsto mogoče obravnavati kot nabor ali zbirko elementov, kot je prikazano spodaj. Elementi so razporejeni linearno.

čakalna vrsta

Imamo dva konca, tj. 'Spredaj' in 'zadaj' čakalne vrste. Ko je vrsta prazna, sta oba kazalca nastavljena na -1.

Kazalec 'zadnji' je kraj, od koder so elementi vstavljeni v čakalno vrsto. Postopek dodajanja / vstavljanja elementov v čakalno vrsto se imenuje »čakalna vrsta«.

Kazalec 'sprednji' del je kraj, od koder so elementi odstranjeni iz čakalne vrste. Postopek odstranjevanja / brisanja elementov iz čakalne vrste se imenuje »odstrani«.

Ko je vrednost zadnjega kazalca velikost-1, rečemo, da je vrsta polna. Ko je sprednja stran nična, je vrsta prazna.

Osnovne operacije

Struktura podatkov o čakalni vrsti vključuje naslednje operacije:

  • EnQueue: V čakalno vrsto doda element. Dodajanje elementa v čakalno vrsto je vedno na zadnji strani čakalne vrste.
  • DeQueue: Odstrani element iz čakalne vrste. Element se vedno odstrani ali postavi v čakalno vrsto s sprednje strani čakalne vrste.
  • je prazno: Preveri, ali je vrsta prazna.
  • je polna: Preveri, ali je vrsta polna.
  • pokukati: Pridobi element na sprednji strani čakalne vrste, ne da bi ga odstranil.

V čakalno vrsto

V tem postopku se izvedejo naslednji koraki:

  • Preverite, ali je vrsta polna.
  • Če je polno, ustvarite napako pri prelivanju in zapustite.
  • V nasprotnem primeru prirastek 'zadaj'.
  • Lokaciji dodajte element, ki ga kaže ‘zadaj’.
  • Vrnite uspeh.

Dequeue

Postopek odstranjevanja iz vrstnega reda je sestavljen iz naslednjih korakov:

  • Preverite, ali je vrsta prazna.
  • Če je prazno, prikažite napako podtoka in zapustite.
  • V nasprotnem primeru je element dostopa označen s „spredaj“.
  • Povečajte 'front', da kaže na naslednje dostopne podatke.
  • Vrnite uspeh.

Nato bomo videli podroben prikaz operacij vstavljanja in brisanja v čakalni vrsti.

Ilustracija

ilustracija vstavljanja in brisanja v čakalni vrsti

To je prazna vrsta in tako imamo zadaj in prazno nastavljeno na -1.

Nato v čakalno vrsto dodamo 1 in posledično se zadnji kazalec premakne naprej za eno mesto.

Operacija EnQueue

Na naslednji sliki v čakalno vrsto dodamo element 2 s premikom zadnjega kazalca naprej za še en korak.

dodajte element 2 v vrsto

Na naslednji sliki dodamo element 3 in premaknemo zadnji kazalec za 1.

dodajte element 3

V tem trenutku ima zadnji kazalec vrednost 2, medtem ko je sprednji kazalec na 0thlokaciji.

Nato izbrišemo element, na katerega kaže sprednji kazalec. Ker je sprednji kazalec na 0, je element, ki se izbriše, 1.

DeQueue delovanje

Tako je prvi element, vpisan v čakalno vrsto, tj. 1, prvi element, odstranjen iz čakalne vrste. Posledično se bo po prvi dequeue sprednji kazalec premaknil naprej t0 na naslednjo lokacijo, ki je 1.

Izvajanje matrike za čakalno vrsto

Izvedimo strukturo podatkov čakalne vrste s pomočjo C ++.

#include #define MAX_SIZE 5 using namespace std; class Queue { private: int myqueue(MAX_SIZE), front, rear; public: Queue(){ front = -1; rear = -1; } boolisFull(){ if(front == 0 && rear == MAX_SIZE - 1){ return true; } return false; } boolisEmpty(){ if(front == -1) return true; else return false; } void enQueue(int value){ if(isFull()){ cout << endl<< 'Queue is full!!'; } else { if(front == -1) front = 0; rear++; myqueue(rear) = value; cout << value << ' '; } } int deQueue(){ int value; if(isEmpty()){ cout << 'Queue is empty!!' <= rear){ //only one element in queue front = -1; rear = -1; } else { front++; } cout << endl < ' << value << ' from myqueue'; return(value); } } /* Function to display elements of Queue */ void displayQueue() { int i; if(isEmpty()) { cout << endl << 'Queue is Empty!!' << endl; } else { cout << endl << 'Front = ' << front; cout << endl << 'Queue elements : '; for(i=front; i<=rear; i++) cout << myqueue(i) << ' '; cout << endl << 'Rear = ' << rear << endl; } } }; int main() { Queue myq; myq.deQueue(); //deQueue cout<<'Queue created:'< queue is full myq.enQueue(60); myq.displayQueue(); //deQueue =>removes 10 myq.deQueue(); //queue after dequeue myq.displayQueue(); return 0; }

Izhod:

Čakalna vrsta je prazna !!
Čakalna vrsta ustvarjena:
10 20 30 40 50
Čakalna vrsta je polna !!
Spredaj = 0
Elementi čakalne vrste: 10 20 30 40 50
Zadaj = 4

Izbrisano => 10 iz moje vrste
Spredaj = 1
Elementi čakalne vrste: 20 30 40 50
Zadaj = 4

Zgornja izvedba prikazuje vrsto, ki je predstavljena kot matrika. Za matriko določimo max_size. Določimo tudi operacije čakanja in razveljavitve ter operacije isFull in isEmpty.

Spodaj je predstavljena Java izvedba strukture podatkov čakalne vrste.

// A class representing a queue class Queue { int front, rear, size; int max_size; int myqueue(); public Queue(int max_size) { this.max_size = max_size; front = this.size = 0; rear = max_size - 1; myqueue = new int(this.max_size); } //if size = max_size , queue is full boolean isFull(Queue queue) { return (queue.size == queue.max_size); } // size = 0, queue is empty boolean isEmpty(Queue queue) { return (queue.size == 0); } // enqueue - add an element to the queue void enqueue( int item) { if (isFull(this)) return; this.rear = (this.rear + 1)%this.max_size; this.myqueue(this.rear) = item; this.size = this.size + 1; System.out.print(item + ' ' ); } // dequeue - remove an elment from the queue int dequeue() { if (isEmpty(this)) return Integer.MIN_VALUE; int item = this.myqueue(this.front); this.front = (this.front + 1)%this.max_size; this.size = this.size - 1; return item; } // move to front of the queue int front() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.front); } // move to the rear of the queue int rear() { if (isEmpty(this)) return Integer.MIN_VALUE; return this.myqueue(this.rear); } } // main class class Main { public static void main(String() args) { Queue queue = new Queue(1000); System.out.println('Queue created as:'); queue.enqueue(10); queue.enqueue(20); queue.enqueue(30); queue.enqueue(40); System.out.println(' Element ' + queue.dequeue() + ' dequeued from queue '); System.out.println('Front item is ' + queue.front()); System.out.println('Rear item is ' + queue.rear()); } }

Izhod:

Čakalna vrsta ustvarjena kot:
10 20 30 40
Element 10 je postavljen iz čakalne vrste

Sprednji element je 20
Zadnji element je 40

Zgornja izvedba je podobna izvedbi C ++.

Nato izvedimo čakalno vrsto v jeziku C ++ s pomočjo povezanega seznama.

Izvedba povezanega seznama za čakalno vrsto:

#include using namespace std; struct node { int data; struct node *next; }; struct node* front = NULL; struct node* rear = NULL; struct node* temp; void Insert(int val) { if (rear == NULL) { rear = new node; rear->next = NULL; rear->data = val; front = rear; } else { temp=new node; rear->next = temp; temp->data = val; temp->next = NULL; rear = temp; } } void Delete() { temp = front; if (front == NULL) { cout<<'Queue is empty!!'next; cout<<'Element deleted from queue is : '

Izhod:

Čakalna vrsta ustvarjena:
10 20 30 40 50
Element, izbrisan iz čakalne vrste, je: 10
Čakalna vrsta po enem izbrisu:
20 30 40 50

najdi razliko med dvema datotekama

Stack Vs. Čakalna vrsta

Skladi in čakalne vrste so sekundarne podatkovne strukture, ki jih je mogoče uporabiti za shranjevanje podatkov. Lahko jih programiramo z uporabo primarnih podatkovnih struktur, kot so nizi in povezani seznami. Po podrobni obravnavi obeh podatkovnih struktur je čas, da razpravljamo o glavnih razlikah med tema dvema podatkovnima strukturama.

SkladiČakalne vrste
Uporablja pristop LIFO (zadnji vhod, prvi izhod).Uporablja pristop FIFO (First in, First out).
Elementi se dodajo ali izbrišejo samo z enega konca, ki se imenuje »Vrh« sklada.Elementi se dodajo s konca čakalne vrste „zadaj“ in odstranijo s sprednje strani čakalne vrste.
Osnovni operaciji sklada sta 'push' in 'Pop'.Osnovni operaciji čakalne vrste sta »čakanje« in »odstranjevanje iz vrst«.
Vse operacije na kupu lahko izvedemo tako, da za dostop do vrha sklada ohranimo le en kazalec.V čakalnih vrstah moramo vzdrževati dva kazalca, enega za dostop do sprednje strani čakalne vrste in drugega za zadnji del čakalne vrste.
Sklop se večinoma uporablja za reševanje rekurzivnih problemov.Čakalne vrste se uporabljajo za reševanje težav, povezanih z naročeno obdelavo.

Aplikacije v čakalni vrsti

Spodaj bomo razpravljali o različnih aplikacijah strukture podatkov čakalne vrste.

  • Podatkovna struktura čakalne vrste se uporablja pri različnih načrtovanjih procesorjev in diskov. Tu imamo več nalog, ki hkrati zahtevajo CPU ali disk. Čas procesorja ali diska je predviden za vsako opravilo s pomočjo čakalne vrste.
  • Čakalna vrsta se lahko uporablja tudi za spool tiskanje, pri čemer je število tiskalnih opravil postavljeno v čakalno vrsto.
  • Ravnanje s prekinitvami v sistemih v realnem času poteka z uporabo podatkovne strukture čakalne vrste. Prekinitve se obravnavajo v vrstnem redu, kot so prispele.
  • Najširše iskanje, pri katerem se preusmerijo sosednja vozlišča drevesa, preden se premaknete na naslednjo stopnjo, uporabi čakalno vrsto za izvedbo.
  • Telefonski sistemi klicnega centra uporabljajo čakalne vrste, da zadržijo klice, dokler se na njih ne odzovejo predstavniki storitve.

Na splošno lahko rečemo, da se struktura podatkov o čakalni vrsti uporablja vsakič, ko potrebujemo servisiranje virov ali postavk v vrstnem redu, kot so, tj.

Zaključek

Čakalna vrsta je struktura podatkov FIFO (First In, First Out), ki se večinoma uporablja v virih, kjer je potrebno razporejanje. Ima dva kazalca zadaj in spredaj na dveh koncih, ki se uporabljata za vstavljanje elementa in odstranitev elementa v / iz čakalne vrste.

V naslednji vadnici bomo spoznali nekatere razširitve čakalne vrste, kot so prednostna in krožna vrsta.

=> Za ogled celotnega seznama vadnic za C ++ glejte tukaj.

Priporočeno branje

^