Fronta v C++ Standard Template Library (STL)
Fronty jsou typem adaptérů kontejnerů, které fungují v uspořádání typu první dovnitř, první ven (FIFO). Prvky jsou vloženy na zadní (konec) a jsou odstraněny zepředu. Fronty používají zapouzdřený objekt deque resp seznam (třída sekvenčního kontejneru) jako jeho základní kontejner, který poskytuje specifickou sadu členských funkcí pro přístup k jeho prvkům.
Následuje příklad, který demonstruje frontu a její různé metody.
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ýstup
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Metody fronty jsou:
Časová složitost a definice následujících funkcí jsou následující:
| fronta::empty() | O(1) |
| fronta::velikost() | O(1) |
| fronta::místo() | O(1) |
| fronta::front() | O(1) |
| fronta::zpět() | O(1) |
| fronta::push(g) | O(1) |
| fronta::pop() | O(1) |
| Metoda | Definice |
|---|---|
| fronta::empty() | Vrací, zda je fronta prázdná. Pokud je fronta prázdná, vrátí hodnotu true, jinak vrátí hodnotu false. |
| fronta::velikost() | Vrátí velikost fronty. |
| fronta::swap() | Vyměňte obsah dvou front, ale fronty musí být stejného datového typu, i když velikosti se mohou lišit. |
| fronta::místo() | Vložte nový prvek do kontejneru fronty, nový prvek se přidá na konec fronty. |
| fronta::front() | Vrátí odkaz na první prvek fronty. |
| fronta::zpět() | Vrátí odkaz na poslední prvek fronty. |
| fronta::push(g) | Přidá prvek „g“ na konec fronty. |
| fronta::pop() | Odstraní první prvek fronty. |
C++ program pro některé další metody
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ýstup
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 prostorová složitost operací v tomto kódu je následující:
funkce print_queue:
Časová složitost: O(n), kde n je počet prvků ve frontě.
Složitost prostoru: O(n), kde n je počet prvků ve frontě.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Časová složitost: O(1) pro každou operaci push.
Složitost prostoru: O(n), kde n je celkový počet prvků v obou frontách.
q1.swap(q2):
Časová složitost: O(1) pro každou operaci swapu.
Prostorová složitost: O(1), protože tato operace pouze prohodí vnitřní ukazatele dvou front.
q1.empty():
Časová složitost: O(1), protože tato operace jednoduše zkontroluje, zda je fronta prázdná.
Prostorová složitost: O(1), protože pro tuto operaci není použit žádný prostor navíc.
Celkově jsou časové a prostorové složitosti tohoto kódu přiměřené a efektivní pro typické případy použití.
Nedávné články o C++ Queue
