Front v C++ Standard Template Library (STL)
Fronty sú typom kontajnerových adaptérov, ktoré fungujú v usporiadaní typu prvý dovnútra prvý von (FIFO). Prvky sa vkladajú zozadu (koniec) a spredu sa odstraňujú. Fronty využívajú zapuzdrený objekt deque resp zoznam (trieda sekvenčného kontajnera) ako jeho základný kontajner, ktorý poskytuje špecifickú sadu členských funkcií na prístup k jeho prvkom.
Nasleduje príklad na demonštráciu fronty a jej rôznych metód.
CPP
// CPP code to illustrate Queue in> // Standard Template Library (STL)> #include> #include> using> namespace> std;> // Print the queue> void> showq(queue <> int> >gq)> {> > queue <> int> >g = gq;> > while> (!g.empty()) {> > cout < <> ' '> < < g.front();> > g.pop();> > }> > cout < <> '
'> ;> }> // Driver Code> int> main()> {> > queue <> int> >gquiz;> > gquiz.push(10);> > gquiz.push(20);> > gquiz.push(30);> > cout < <> 'The queue gquiz is : '> ;> > showq(gquiz);> > cout < <> '
gquiz.size() : '> < < gquiz.size();> > cout < <> '
gquiz.front() : '> < < gquiz.front();> > cout < <> '
gquiz.back() : '> < < gquiz.back();> > cout < <> '
gquiz.pop() : '> ;> > gquiz.pop();> > showq(gquiz);> > return> 0;> }> |
Výkon
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Metódy fronty sú:
Časová zložitosť a definícia nasledujúcich funkcií sú nasledovné:
| front::prázdny() | O(1) |
| front::veľkosť() | O(1) |
| fronta::miesto() | O(1) |
| front::front() | O(1) |
| fronta::späť() | O(1) |
| fronta::push(g) | O(1) |
| fronta::pop() | O(1) |
| Metóda | Definícia |
|---|---|
| front::prázdny() | Vráti, či je front prázdny. Ak je front prázdny, vráti hodnotu true, inak vráti hodnotu false. |
| front::veľkosť() | Vráti veľkosť frontu. |
| fronta::swap() | Vymeňte obsah dvoch frontov, ale fronty musia byť rovnakého typu údajov, aj keď veľkosti sa môžu líšiť. |
| fronta::miesto() | Vložte nový prvok do kontajnera frontu, nový prvok sa pridá na koniec frontu. |
| front::front() | Vráti odkaz na prvý prvok frontu. |
| fronta::späť() | Vráti odkaz na posledný prvok frontu. |
| fronta::push(g) | Pridá prvok „g“ na koniec frontu. |
| fronta::pop() | Odstráni prvý prvok frontu. |
C++ program pre niektoré ďalšie metódy
C++
// CPP code to illustrate Queue operations in STL> // Divyansh Mishra -->divyanshmishra101010> #include> #include> using> namespace> std;> // Print the queue> void> print_queue(queue <> int> >q)> {> > queue <> int> >teplota = q;> > while> (!temp.empty()) {> > cout < < temp.front() < <> ' '> ;> > temp.pop();> > }> > cout < <> '
'> ;> }> // Driver Code> int> main()> {> > queue <> int> >q1;> > q1.push(1);> > q1.push(2);> > q1.push(3);> > cout < <> 'The first queue is : '> ;> > print_queue(q1);> > > queue <> int> >q2;> > q2.push(4);> > q2.push(5);> > q2.push(6);> > cout < <> 'The second queue is : '> ;> > print_queue(q2);> > > > q1.swap(q2);> > > cout < <> 'After swapping, the first queue is : '> ;> > print_queue(q1);> > cout < <> 'After swapping the second queue is : '> ;> > print_queue(q2);> > > cout |
Výkon
The first queue is : 1 2 3 The second queue is : 4 5 6 After swapping, the first queue is : 4 5 6 After swapping the second queue is : 1 2 3 0
Časová a priestorová zložitosť operácií v tomto kóde je nasledovná:
funkcia print_queue:
Časová zložitosť: O(n), kde n je počet prvkov vo fronte.
Priestorová zložitosť: O(n), kde n je počet prvkov vo fronte.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Časová zložitosť: O(1) pre každú operáciu push.
Priestorová zložitosť: O(n), kde n je celkový počet prvkov v oboch frontoch.
q1.swap(q2):
Časová zložitosť: O(1) pre každú swapovú operáciu.
Priestorová zložitosť: O(1), pretože táto operácia iba zamieňa interné ukazovatele dvoch frontov.
q1.empty():
Časová zložitosť: O(1), pretože táto operácia jednoducho skontroluje, či je front prázdny.
Priestorová zložitosť: O(1), keďže na túto operáciu sa nepoužíva žiadny priestor navyše.
Celkovo je časová a priestorová zložitosť tohto kódu primeraná a efektívna pre typické prípady použitia.
Najnovšie články o C++ Queue
