Meniu

Structura datelor în coadă în C ++ cu ilustrație

  • Principal
  • Alte
  • Structura datelor în coadă în C ++ cu ilustrație

queue data structure c with illustration

Încercați Instrumentul Nostru Pentru Eliminarea Problemelor

O scurtă introducere la coadă în C ++ cu ilustrație.

Coada este o structură de date de bază la fel ca o stivă. Spre deosebire de stiva care utilizează abordarea LIFO, coada utilizează abordarea FIFO (primul intrat, primul ieșit). Cu această abordare, primul element care este adăugat la coadă este primul element care trebuie eliminat din coadă. La fel ca Stack, coada este, de asemenea, o structură de date liniară.

administratorul informatica intervievează întrebări și răspunsuri

Într-o analogie din lumea reală, ne putem imagina o coadă de autobuz în care pasagerii așteaptă autobuzul într-o coadă sau o linie. Primul pasager din linie intră primul în autobuz, deoarece acel pasager se întâmplă să fie cel care a venit primul.

=> Citiți aici seria populară de formare C ++.

Coadă în C ++

Ce veți învăța:

Coadă în C ++

În termeni software, coada poate fi vizualizată ca un set sau o colecție de elemente așa cum se arată mai jos. Elementele sunt dispuse liniar.

coadă

Avem două capete, adică „față” și „spate” ale cozii. Când coada este goală, ambele indicatoare sunt setate la -1.

Pointerul „spate” este locul de unde elementele sunt inserate în coadă. Operația de adăugare / inserare a elementelor în coadă se numește „enqueue”.

Pointerul „frontal” este locul de unde elementele sunt eliminate din coadă. Operațiunea de eliminare / ștergere a elementelor din coadă se numește „dequeue”.

Când valoarea indicatorului din spate este mărimea-1, atunci spunem că coada este plină. Când partea frontală este nulă, atunci coada este goală.

Operațiuni de bază

Structura de date a cozii include următoarele operații:

  • EnQueue: Adaugă un element la coadă. Adăugarea unui articol la coadă se face întotdeauna în partea din spate a cozii.
  • DeQueue: Elimină un element din coadă. Un element este îndepărtat sau scoat din coadă întotdeauna din partea din față a cozii.
  • este gol: Verifică dacă coada este goală.
  • e plin: Verifică dacă coada este plină.
  • arunca o privire: Obține un element în partea din față a cozii fără a-l elimina.

Strângeți

În acest proces, se efectuează următorii pași:

  • Verificați dacă coada este plină.
  • Dacă este plin, produceți o eroare de depășire și ieșiți.
  • Altfel, crește „spate”.
  • Adăugați un element la locația indicată de „spate”.
  • Întoarce succesul.

Scoateți

Operația de stingere a cozii constă din următorii pași:

  • Verificați dacă coada este goală.
  • Dacă este gol, afișați o eroare de debordare și ieșiți.
  • Altfel, elementul de acces este indicat prin „față”.
  • Măriți „fața” pentru a indica următoarele date accesibile.
  • Întoarce succesul.

Apoi, vom vedea o ilustrare detaliată a operațiilor de inserare și ștergere în coadă.

Ilustrare

ilustrarea inserării și ștergerii în coadă

Aceasta este o coadă goală și, astfel, avem setul din spate și gol la -1.

Apoi, adăugăm 1 la coadă și, ca rezultat, indicatorul din spate se deplasează înainte cu o singură locație.

Operațiunea EnQueue

În figura următoare, adăugăm elementul 2 la coadă mișcând indicatorul din spate înainte cu un alt increment.

adăugați elementul 2 la coadă

În figura următoare, adăugăm elementul 3 și mutăm indicatorul din spate cu 1.

adăugați elementul 3

În acest moment, indicatorul din spate are valoarea 2, în timp ce indicatorul din față este la 0aLocație.

Apoi, ștergem elementul indicat de indicatorul frontal. Deoarece indicatorul frontal este la 0, elementul șters este 1.

Operațiunea DeQueue

Astfel, primul element introdus în coadă, adică 1 se întâmplă să fie primul element eliminat din coadă. Ca rezultat, după prima coadă, indicatorul frontal acum va fi mutat înainte t0 următoarea locație care este 1.

Implementarea matricei pentru coadă

Să implementăm structura datelor cozii folosind 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; }

Ieșire:

Coada este goală !!
Coadă creată:
10 20 30 40 50
Coada este plină !!
Front = 0
Elemente coadă: 10 20 30 40 50
Spate = 4

Șters => 10 din coadă
Front = 1
Elemente de coadă: 20 30 40 50
Spate = 4

Implementarea de mai sus arată coada reprezentată ca o matrice. Specificăm max_size pentru matrice. De asemenea, definim operațiile de coadă și de coadă, precum și operațiile isFull și isEmpty.

Mai jos este implementarea Java a structurii de date a cozii.

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

Ieșire:

Coadă creată ca:
10 20 30 40
Elementul 10 scos din coadă

Elementul frontal este 20
Elementul din spate este 40

Implementarea de mai sus este similară cu implementarea C ++.

Apoi, să implementăm coada în C ++ folosind o listă legată.

Implementarea listei legate pentru coadă:

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

Ieșire:

Coadă creată:
10 20 30 40 50
Elementul șters din coadă este: 10
Coada după o ștergere:
20 30 40 50

cum se deschide fișierul json în Windows 10

Stiva vs. Coadă

Stivele și cozile sunt structuri de date secundare care pot fi utilizate pentru stocarea datelor. Ele pot fi programate folosind structurile de date primare, cum ar fi matrici și liste legate. După ce am discutat în detaliu ambele structuri de date, este timpul să discutăm principalele diferențe dintre aceste două structuri de date.

StiveCozi
Folosește abordarea LIFO (Last in, First out).Folosește abordarea FIFO (First in, First out).
Elementele sunt adăugate sau șterse dintr-un singur capăt numit „Sus” al stivei.Elementele sunt adăugate de la capătul „Spate” al cozii și sunt eliminate din „fața” cozii.
Operațiunile de bază pentru stivă sunt „push” și „Pop”.Operațiunile de bază pentru o coadă sunt „enqueue” și „dequeue”.
Putem face toate operațiunile pe stivă menținând un singur indicator pentru a accesa partea de sus a stivei.În cozi, trebuie să menținem două indicatoare, una pentru a accesa partea din față a cozii și a doua pentru a accesa partea din spate a cozii.
Stiva este folosită mai ales pentru rezolvarea problemelor recursive.Cozile sunt folosite pentru a rezolva problemele legate de procesarea comandată.

Aplicații de coadă

Să discutăm mai jos diferitele aplicații ale structurii de date a cozii.

  • Structura de date a cozii este utilizată în diferite planificări ale procesorului și discului. Aici avem mai multe sarcini care necesită CPU sau disc în același timp. Durata procesorului sau a discului este programată pentru fiecare activitate folosind o coadă.
  • Coada poate fi utilizată și pentru spoolingul de tipărire în care numărul de lucrări de imprimare este plasat într-o coadă.
  • Gestionarea întreruperilor în sistemele în timp real se face utilizând o structură de date în coadă. Întreruperile sunt tratate în ordinea în care ajung.
  • Prima căutare în lățime în care sunt traversate nodurile vecine ale unui copac înainte de a trece la nivelul următor utilizează o coadă pentru implementare.
  • Sistemele de telefonie din centrul de apeluri folosesc cozi pentru a reține apelurile până când acestea sunt primite de către reprezentanții serviciului.

În general, putem spune că structura de date a cozii este utilizată ori de câte ori avem nevoie ca resursele sau articolele să fie deservite în ordinea în care ajung, adică First in, First Out.

Concluzie

Coada este o structură de date FIFO (First In, First Out) care este utilizată în principal în resurse în care este necesară programarea. Are două indicatoare din spate și din față la două capete și acestea sunt utilizate pentru a introduce un element și, respectiv, pentru a scoate un element din / din coadă.

În următorul nostru tutorial, vom afla despre unele dintre extensiile cozii, cum ar fi coada prioritară și coada circulară.

=> Consultați aici pentru a explora lista completă de tutoriale C ++.

Lectură recomandată

^