Menu

Dátová štruktúra frontu v C ++ s ilustráciou

  • Hlavná
  • Iné
  • Dátová štruktúra frontu v C ++ s ilustráciou

queue data structure c with illustration

Stručný úvod do frontu v C ++ s ilustráciou.

Fronta je základná dátová štruktúra, rovnako ako zásobník. Na rozdiel od zásobníka, ktorý používa prístup LIFO, front používa prístup FIFO (prvý dovnútra, prvý von). S týmto prístupom je prvá položka, ktorá sa pridá do frontu, prvou položkou, ktorá sa odstráni z frontu. Rovnako ako Stack je front tiež lineárnou dátovou štruktúrou.

V analógii zo skutočného sveta si môžeme predstaviť autobusovú frontu, kde cestujúci čakajú na autobus v rade alebo rade. Prvý cestujúci v rade vstúpi do autobusu prvý, pretože týmto cestujúcim je ten, ktorý prišiel prvý.

nástroje na testovanie pokojných webových služieb

=> Prečítajte si populárnu sériu školení C ++ tu.

Poradie v jazyku C ++

Čo sa dozviete:

Poradie v jazyku C ++

Pokiaľ ide o softvér, frontu je možné zobraziť ako množinu alebo kolekciu prvkov, ako je uvedené nižšie. Prvky sú usporiadané lineárne.

poradie

Máme dva konce, tj. „Predný“ a „zadný“ v poradí. Keď je poradie prázdne, potom sú oba ukazovatele nastavené na -1.

„Zadný“ koncový ukazovateľ je miesto, odkiaľ sa vkladajú prvky do poradia. Operácia pridávania / vkladania prvkov do frontu sa nazýva „zaradenie do fronty“.

„Predný“ koncový ukazovateľ je miesto, odkiaľ sú prvky odstránené z poradia. Operácia odstránenia / odstránenia prvkov z frontu sa nazýva „dequeue“.

Keď je hodnota zadného ukazovateľa veľkosť-1, potom hovoríme, že poradie je plné. Ak je predná strana nulová, poradie je prázdne.

Základné operácie

Štruktúra dát frontu obsahuje nasledujúce operácie:

  • Poradie: Pridá položku do frontu. Pridanie položky do poradia sa vždy deje na konci poradia.
  • DeQueue: Odstráni položku z frontu. Položka sa odstráni alebo sa do fronty zaradí vždy z prednej časti frontu.
  • je prázdny: Skontroluje, či je rad prázdny.
  • je plný: Skontroluje, či je rad plný.
  • nahliadnuť: Získava prvok na začiatku frontu bez jeho odstránenia.

Zaradiť do poradia

V tomto procese sa vykonávajú nasledujúce kroky:

  • Skontrolujte, či je poradie plné.
  • Ak je plná, spôsobte chybu pretečenia a ukončite prácu.
  • Inak, prírastok „zozadu“.
  • Pridajte prvok na miesto označené „zozadu“.
  • Návrat úspechu.

Dequeue

Operácia zaradenia do fronty pozostáva z nasledujúcich krokov:

  • Skontrolujte, či je rad prázdny.
  • Ak je prázdne, zobrazí sa chyba podtečenia a výstup je ukončený.
  • Inak je na prístupový prvok poukázané výrazom „spredu“.
  • Zvyšujte „predok“, aby ukazoval na ďalšie prístupné údaje.
  • Návrat úspechu.

Ďalej uvidíme podrobnú ilustráciu operácií vkladania a mazania vo fronte.

Ilustrácia

ilustrácia vkladania a mazania vo fronte

Toto je prázdny rad, a preto máme zadné a prázdne nastavené na -1.

Ďalej do fronty pridáme 1 a vo výsledku sa zadný ukazovateľ posunie dopredu o jedno miesto.

Prevádzka fronty

Na nasledujúcom obrázku pridáme prvok 2 do poradia posunutím zadného ukazovateľa dopredu o ďalší prírastok.

pridať prvok 2 do poradia

Na nasledujúcom obrázku pridáme prvok 3 a posunieme zadný ukazovateľ o 1.

pridať prvok 3

V tomto okamihu má zadný ukazovateľ hodnotu 2, zatiaľ čo predný ukazovateľ je na nulethumiestnenie.

Ďalej vymažeme prvok, na ktorý ukazuje predný ukazovateľ. Pretože je predný ukazovateľ na nule, odstránený prvok je 1.

Prevádzka fronty

Prvý prvok zaradený do poradia, tj. 1, sa teda stane prvým prvkom odstráneným z poradia. Výsledkom je, že po prvom dequeue sa teraz posunie predný ukazovateľ dopredu na ďalšie miesto, ktoré je 1.

Implementácia poľa pre frontu

Implementujme štruktúru údajov frontu pomocou 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; }

Výkon:

Fronta je prázdna !!
Fronta vytvorená:
10 20 30 40 50
Fronta je plná !!
Predná strana = 0
Prvky poradia: 10 20 30 40 50
Zadná strana = 4

Odstránené => 10 z myqueue
Predná strana = 1
Prvky poradia: 20 30 40 50
Zadná strana = 4

Vyššie uvedená implementácia zobrazuje front predstavovaný ako pole. Zadáme max_size pre pole. Definujeme tiež operácie zaradenia a vyradenia z frontu, ako aj operácie isFull a isEmpty.

Ďalej je uvedená implementácia štruktúry frontu údajov v prostredí Java.

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

Výkon:

Fronta vytvorená ako:
10 20 30 40
Element 10 vyradený z poradia

Predná položka je 20
Zadná položka je 40

Vyššie uvedená implementácia je podobná implementácii C ++.

Ďalej implementujme front v C ++ pomocou prepojeného zoznamu.

Implementácia prepojeného zoznamu pre front:

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

Výkon:

Fronta vytvorená:
10 20 30 40 50
Prvok odstránený z poradia je: 10
Poradie po jednom odstránení:
20 30 40 50

Stack vs. Fronta

Stohy a fronty sú sekundárne dátové štruktúry, ktoré sa dajú použiť na ukladanie údajov. Môžu byť programované pomocou primárnych dátových štruktúr, ako sú polia a prepojené zoznamy. Po podrobnom prediskutovaní oboch dátových štruktúr je čas diskutovať o hlavných rozdieloch medzi týmito dvoma dátovými štruktúrami.

čo je dobrý sťahovač mp3
StohyFronty
Používa prístup LIFO (Last in, First out).Používa prístup FIFO (prvý dovnútra, prvý von).
Položky sa pridávajú alebo mazajú iba z jedného konca, ktorý sa nazýva „Vrchná časť“ zásobníka.Položky sa pridávajú z „zadného“ konca frontu a odstraňujú sa z „prednej“ fronty.
Základné operácie pre zásobník sú „push“ a „pop“.Základné operácie pre front sú „zaradenie do fronty“ a „zaradenie do fronty“.
Všetky operácie nad zásobníkom môžeme robiť tak, že udržíme iba jeden ukazovateľ na prístup k hornej časti zásobníka.Vo frontoch musíme udržiavať dva ukazovatele, jeden pre prístup k prednej časti frontu a druhý pre prístup k zadnej časti frontu.
Zásobník sa väčšinou používa na riešenie rekurzívnych problémov.Fronty sa používajú na riešenie problémov súvisiacich s objednaným spracovaním.

Aplikácie frontu

Ďalej diskutujeme o rôznych aplikáciách štruktúry údajov o fronte.

  • Štruktúra údajov frontu sa používa pri rôznych plánovaní CPU a diskov. Tu máme viac úloh vyžadujúcich súčasne procesor alebo disk. Čas CPU alebo disku je naplánovaný pre každú úlohu pomocou frontu.
  • Frontu je možné použiť aj na spoolovanie tlače, pri ktorom je počet tlačových úloh zaradený do frontu.
  • Manipulácia s prerušeniami v systémoch v reálnom čase sa vykonáva pomocou dátovej štruktúry frontu. Prerušenia sa vybavujú v poradí, v akom prídu.
  • Pri hľadaní na šírku, v ktorom sa prekonávajú susedné uzly stromu, pred prechodom na ďalšiu úroveň, sa na implementáciu použije front.
  • Telefónne systémy call centra používajú fronty na zadržanie hovorov, kým na ne neodpovie zástupca servisu.

Všeobecne sa dá povedať, že dátová štruktúra frontu sa používa vždy, keď požadujeme, aby sa prostriedky alebo položky obsluhovali v poradí, v akom prichádzajú, tj. Prvý dovnútra, Prvý von.

Záver

Fronta je dátová štruktúra FIFO (prvý vstup, prvý výstup), ktorá sa väčšinou používa v prostriedkoch, kde sa vyžaduje plánovanie. Má dva ukazovatele vzadu a vpredu na dvoch koncoch a slúžia na vloženie prvku a odstránenie prvku do / z poradia.

V našom ďalšom návode sa dozvieme o niektorých rozšíreniach frontu, ako sú prioritné fronty a kruhové fronty.

=> Ak chcete preskúmať celý zoznam výukových programov C ++, prečítajte si tu.

Odporúčané čítanie

^