Menu

Struktura dat fronty v C ++ s ilustrací

queue data structure c with illustration

Vyzkoušejte Náš Nástroj Pro Odstranění Problémů

Stručný úvod do fronty v C ++ s ilustrací.

Fronta je základní datová struktura jako zásobník. Na rozdíl od zásobníku, který používá přístup LIFO, používá fronta přístup FIFO (první dovnitř, první ven). S tímto přístupem je první položka přidaná do fronty první položkou, která má být z fronty odebrána. Stejně jako Stack je fronta také lineární datovou strukturou.

Otázky a odpovědi k rozhovorům s webovými službami pro zkušené v Javě

V analogii reálného světa si můžeme představit autobusovou frontu, kde cestující čekají na autobus ve frontě nebo na lince. První cestující v řadě vstoupí do autobusu jako první, protože cestující je ten, kdo přišel jako první.

=> Přečtěte si zde populární sérii školení C ++.

Fronta v C ++

Co se naučíte:

Fronta v C ++

Z hlediska softwaru lze frontu zobrazit jako sadu nebo kolekci prvků, jak je znázorněno níže. Prvky jsou uspořádány lineárně.

fronta

Máme dva konce, tj. „Přední“ a „zadní“ fronty. Když je fronta prázdná, pak jsou oba ukazatele nastaveny na -1.

„Zadní“ koncový ukazatel je místo, odkud jsou prvky vloženy do fronty. Operace přidávání / vkládání prvků do fronty se nazývá „enqueue“.

„Přední“ koncový ukazatel je místo, odkud jsou prvky odebrány z fronty. Operace odebrání / odstranění prvků z fronty se nazývá „dequeue“.

Když je hodnota zadního ukazatele velikost-1, řekneme, že fronta je plná. Když je přední strana prázdná, fronta je prázdná.

Základní operace

Struktura dat fronty zahrnuje následující operace:

  • Zařadit do fronty: Přidá položku do fronty. Přidání položky do fronty se vždy provádí v zadní části fronty.
  • Fronta: Odebere položku z fronty. Položka je odebrána nebo zrušena ve frontě vždy z přední části fronty.
  • je prázdný: Zkontroluje, zda je fronta prázdná.
  • je plný: Zkontroluje, zda je fronta plná.
  • nahlédnout: Získá prvek v přední části fronty bez jeho odebrání.

Zařadit do fronty

V tomto procesu se provádějí následující kroky:

  • Zkontrolujte, zda je fronta plná.
  • Pokud je plná, způsobí chybu přetečení a ukončí se.
  • Jinak přírůstek „vzadu“.
  • Přidejte prvek na místo označené „vzadu“.
  • Vraťte úspěch.

Dequeue

Operace dequeue sestává z následujících kroků:

  • Zkontrolujte, zda je fronta prázdná.
  • Pokud je prázdný, zobrazí se chyba podtečení a ukončí se.
  • Jinak je na přístupový prvek poukázáno slovem „vpředu“.
  • Zvětšete „přední část“, aby ukazovala na další přístupná data.
  • Vraťte úspěch.

Dále uvidíme podrobnou ilustraci operací vložení a odstranění ve frontě.

Ilustrace

ilustrace vkládání a mazání ve frontě

Toto je prázdná fronta, a proto máme zadní a prázdnou nastavenou na -1.

Dále přidáme 1 do fronty a ve výsledku se zadní ukazatel posune dopředu o jedno místo.

Operace EnQueue

Na dalším obrázku přidáme prvek 2 do fronty posunutím zadního ukazatele dopředu o další přírůstek.

přidat prvek 2 do fronty

Na následujícím obrázku přidáme prvek 3 a posuneme zadní ukazatel o 1.

přidat prvek 3

V tomto okamžiku má zadní ukazatel hodnotu 2, zatímco přední je na 0thumístění.

Dále odstraníme prvek, na který ukazuje přední ukazatel. Protože přední ukazatel je na 0, je odstraněný prvek 1.

Operace DeQueue

Takže první prvek zadaný do fronty, tj. 1, se stane prvním prvkem odstraněným z fronty. Výsledkem je, že po první dekádě se nyní přední ukazatel přesune dopředu o t další umístění, které je 1.

Implementace pole pro frontu

Implementujme datovou strukturu fronty pomocí 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ýstup:

Fronta je prázdná !!
Fronta vytvořena:
10 20 30 40 50
Fronta je plná !!
Přední = 0
Prvky fronty: 10 20 30 40 50
Zadní = 4

Smazáno => 10 z myqueue
Přední = 1
Prvky fronty: 20 30 40 50
Zadní = 4

Výše uvedená implementace zobrazuje frontu představovanou jako pole. Určíme max_size pro pole. Rovněž definujeme operace zařazení a odstranění fronty, stejně jako operace isFull a isEmpty.

Níže je uvedena implementace datové struktury fronty v prostředí 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ýstup:

Fronta vytvořena jako:
10 20 30 40
Prvek 10 vyřazen z fronty

Přední položka je 20
Zadní položka je 40

Výše uvedená implementace je podobná implementaci C ++.

Dále pojďme implementovat frontu v C ++ pomocí propojeného seznamu.

Implementace propojeného seznamu pro frontu:

#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ýstup:

Fronta vytvořena:
10 20 30 40 50
Prvek odstraněný z fronty je: 10
Fronta po jednom odstranění:
20 30 40 50

jaký je nejlepší stahovač hudby pro telefon Android

Stack vs. Fronta

Zásobníky a fronty jsou sekundární datové struktury, které lze použít k ukládání dat. Mohou být programovány pomocí primárních datových struktur, jako jsou pole a propojené seznamy. Po podrobném projednání obou datových struktur je čas diskutovat o hlavních rozdílech mezi těmito dvěma datovými strukturami.

HromádkyFronty
Používá přístup LIFO (Last in, First out).Používá přístup FIFO (první dovnitř, první ven).
Položky jsou přidávány nebo mazány pouze z jednoho konce zvaného „Horní část“ zásobníku.Položky se přidávají ze „zadního“ konce fronty a odebírají se z „přední“ fronty.
Základní operace pro zásobník jsou „push“ a „pop“.Základní operace pro frontu jsou „enqueue“ a „dequeue“.
Můžeme provádět všechny operace na zásobníku udržováním pouze jednoho ukazatele pro přístup k horní části zásobníku.Ve frontách musíme udržovat dva ukazatele, jeden pro přístup k přední části fronty a druhý pro přístup k zadní části fronty.
Zásobník se většinou používá k řešení rekurzivních problémů.Fronty se používají k řešení problémů souvisejících s objednaným zpracováním.

Aplikace fronty

Pojďme diskutovat níže o různých aplikacích struktury dat fronty.

  • Struktura dat fronty se používá při různých plánování CPU a disků. Zde máme několik úkolů vyžadujících CPU nebo disk současně. Čas CPU nebo disku je naplánován pro každou úlohu pomocí fronty.
  • Frontu lze také použít pro zařazování tisku, kde je počet tiskových úloh umístěn do fronty.
  • Zpracování přerušení v systémech v reálném čase se provádí pomocí datové struktury fronty. Přerušení jsou zpracována v pořadí, v jakém dorazí.
  • Prohledávání na šířku, ve kterém jsou procházeny sousední uzly stromu, než přejde na další úroveň, používá pro implementaci frontu.
  • Telefonní systémy call centra používají fronty k přidržení hovorů, dokud na ně neodpoví servisní zástupci.

Obecně lze říci, že datová struktura fronty se používá vždy, když požadujeme, aby byly prostředky nebo položky obsluhovány v pořadí, v jakém přicházejí, tj. Nejprve dovnitř, první ven.

Závěr

Fronta je datová struktura FIFO (First In, First Out), která se většinou používá ve zdrojích, kde je vyžadováno plánování. Má dva ukazatele vzadu a vpředu na dvou koncích a slouží k vložení prvku a odebrání prvku do / z fronty.

V našem dalším kurzu se dozvíme o některých rozšířeních fronty, jako je prioritní fronta a kruhová fronta.

=> Prohlédněte si úplný seznam výukových programů C ++ zde.

Doporučené čtení

^