Meni

Struktura podataka u redu čekanja u C ++ s ilustracijom

  • Glavni
  • Ostalo
  • Struktura podataka u redu čekanja u C ++ s ilustracijom

queue data structure c with illustration

Isprobajte Naš Instrument Za Uklanjanje Problema

Kratki uvod u red čekanja na C ++ s ilustracijom.

Red čekanja je osnovna struktura podataka baš kao i stog. Za razliku od stoga koji koristi LIFO pristup, red koristi FIFO (prvi ulaz, prvi izlaz) pristup. Ovim pristupom prva stavka koja se doda u red prva je stavka koja se uklanja iz reda. Baš kao i Stack, red je također linearna struktura podataka.

etl ispitivanje pitanja i odgovori za iskusni pdf

U stvarnoj analogiji možemo zamisliti red autobusa u kojem putnici čekaju autobus u redu ili na redu. Prvi putnik u redu prvi uđe u autobus, jer je slučajno taj putnik prvi došao.

=> Ovdje pročitajte popularne serije obuke za C ++.

Red čekanja u C ++

Što ćete naučiti:

Red čekanja na C ++

U softverskom smislu, red se može gledati kao skup ili zbirka elemenata kao što je prikazano u nastavku. Elementi su poredani linearno.

red

Imamo dva kraja, tj. 'Prednji' i 'stražnji' red. Kad je red prazan, tada su oba pokazivača postavljena na -1.

Pokazivač 'stražnji' kraj je mjesto odakle su elementi umetnuti u red. Operacija dodavanja / umetanja elemenata u red naziva se 'enqueue'.

Krajnji pokazivač 'prednji' mjesto je odakle se elementi uklanjaju iz reda. Operacija uklanjanja / brisanja elemenata iz reda naziva se 'uklanjanje iz reda'.

Kada je vrijednost stražnjeg pokazivača veličina-1, tada kažemo da je red pun. Kada je prednja strana null, tada je red prazan.

Osnovne operacije

Struktura podataka o redu čekanja uključuje sljedeće operacije:

  • Red čekanja: Dodaje stavku u red čekanja. Dodavanje stavke u red uvijek se vrši na stražnjem dijelu reda.
  • DeQueue: Uklanja stavku iz reda. Stavka se uklanja ili uklanja iz reda uvijek s prednje strane reda.
  • prazno je: Provjerava je li red prazan.
  • puno je: Provjerava je li red pun.
  • zaviriti: Dobiva element na čekanju reda bez uklanjanja.

Stavite u red čekanja

U ovom procesu izvode se sljedeći koraci:

  • Provjerite je li red pun.
  • Ako je puna, stvorite pogrešku prelijevanja i izađite.
  • Inače, prirast 'straga'.
  • Dodajte element na mjesto označeno s 'straga'.
  • Vrati uspjeh.

Dequeue

Operacija uklanjanja iz redova sastoji se od sljedećih koraka:

  • Provjerite je li red prazan.
  • Ako je prazno, prikažite pogrešku podlijevanja i izađite.
  • Inače, na pristupni element ističe 'prednja strana'.
  • Povećajte 'front' kako bi ukazao na sljedeće dostupne podatke.
  • Vrati uspjeh.

Zatim ćemo vidjeti detaljnu ilustraciju operacija umetanja i brisanja u redu čekanja.

Ilustracija

ilustracija umetanja i brisanja u redu čekanja

Ovo je prazan red i stoga imamo stražnji i prazni postavljeni na -1.

Dalje, u red čekamo 1, a kao rezultat, stražnji se pokazivač pomiče naprijed za jedno mjesto.

EnQueue rad

Na sljedećoj slici dodajemo element 2 u red pomicanjem stražnjeg pokazivača naprijed za još jedan korak.

dodajte element 2 u red čekanja

Na sljedećoj slici dodajemo element 3 i pomičemo stražnji pokazivač za 1.

dodati element 3

U ovom trenutku stražnji pokazivač ima vrijednost 2, dok je prednji pokazivač na 0thmjesto.

Dalje, brišemo element usmjeren prednjim pokazivačem. Kako je prednji pokazivač na 0, element koji se briše je 1.

DeQueue rad

Tako je prvi element unet u red, tj. 1, prvi element uklonjen iz reda. Kao rezultat, nakon prvog uklanjanja iz redova, prednji pokazivač sada će se pomaknuti naprijed t0 na sljedeće mjesto koje je 1.

Implementacija niza za red čekanja

Primijenimo strukturu podataka o redu čekanja pomoću 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; }

Izlaz:

Red je prazan !!
Stvoren je red:
10 20 30 40 50
Red je pun !!
Prednja strana = 0
Elementi reda: 10 20 30 40 50
Stražnji = 4

Izbrisano => 10 iz mojeg reda
Prednja = 1
Elementi reda: 20 30 40 50
Stražnji = 4

Gornja implementacija prikazuje red predstavljen kao niz. Određujemo max_size za polje. Također definiramo operacije enqueue i dequeue, kao i operacije isFull i isEmpty.

Dolje je data Java implementacija strukture podataka o redu čekanja.

// 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()); } }

Izlaz:

Red čekanja stvoren kao:
10 20 30 40
Element 10 uklonjen iz reda čekanja

Prednja stavka je 20
Stražnja stavka je 40

Iznad je implementacija slična izvedbi C ++.

Dalje, implementiramo red u C ++ pomoću povezanog popisa.

Implementacija povezanog popisa za red čekanja:

#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 : '

Izlaz:

Stvoren red čekanja:
10 20 30 40 50
Element izbrisan iz reda je: 10
Red čekanja nakon jednog brisanja:
20 30 40 50

koji je najbolji besplatni mp3 downloader

Stack vs. Red

Nizovi i redovi su sekundarne strukture podataka koje se mogu koristiti za pohranu podataka. Mogu se programirati pomoću primarnih struktura podataka poput nizova i povezanih popisa. Nakon detaljnog razgovora o obje strukture podataka, vrijeme je da razgovaramo o glavnim razlikama između ove dvije strukture podataka.

StogoviRedovi
Koristi pristup LIFO (zadnji ulaz, prvi izlaz).Koristi FIFO (First in, First out) pristup.
Stavke se dodaju ili brišu samo s jednog kraja koji se naziva 'Vrh' stoga.Stavke se dodaju sa 'stražnjeg' kraja reda i uklanjaju s 'prednje strane' reda.
Osnovne operacije za stog su 'push' i 'Pop'.Osnovne operacije za red su 'enqueue' i 'dequeue'.
Sve operacije na stogu možemo obaviti zadržavanjem samo jednog pokazivača za pristup vrhu stoga.U redovima trebamo održavati dva pokazivača, jedan za pristup prednjem dijelu reda i drugi za pristup stražnjem dijelu reda.
Stog se uglavnom koristi za rješavanje rekurzivnih problema.Redovi se koriste za rješavanje problema povezanih s naručenom obradom.

Primjene u redu čekanja

Razgovarajmo o raznim primjenama strukture podataka o redu u nastavku.

  • Struktura podataka o redu čekanja koristi se u raznim rasporedima CPU-a i diskova. Ovdje imamo više zadataka koji istovremeno trebaju CPU ili disk. Vrijeme CPU-a ili diska predviđeno je za svaki zadatak pomoću reda.
  • Red čekanja može se koristiti i za namotavanje ispisa pri čemu je broj zadataka ispisa smješten u red čekanja.
  • Rukovanje prekidima u sustavima u stvarnom vremenu vrši se korištenjem strukture podataka u redu. Prekidi se rješavaju redoslijedom kojim su stigli.
  • Pretraživanje u širini, u kojem se prelaze susjedni čvorovi stabla prije prelaska na sljedeću razinu, koristi red za implementaciju.
  • Telefonski sustavi pozivnog centra koriste redove za zadržavanje poziva dok na njih ne odgovore predstavnici usluga.

Općenito, možemo reći da se struktura podataka o redu čekanja koristi kad god trebamo da se resursi ili stavke servisiraju redoslijedom kojim stižu, tj. First in, First Out

Zaključak

Red čekanja je FIFO (First In, First Out) struktura podataka koja se uglavnom koristi u resursima gdje je potrebno raspoređivanje. Ima dva pokazivača straga i sprijeda na dva kraja i oni se koriste za umetanje elementa i uklanjanje elementa u / iz reda.

U našem sljedećem vodiču naučit ćemo o nekim proširenjima reda, kao što su prioritetni red i kružni red.

=> Pogledajte ovdje kako biste istražili cjeloviti popis vodiča za C ++.

Preporučena literatura

^