Cua a la biblioteca de plantilles estàndard (STL) de C++
Les cues són un tipus d'adaptadors de contenidors que funcionen en un tipus d'arranjament FIFO (primer en entrar, primer sortit). Els elements s'insereixen a la part posterior (extrem) i s'eliminen de la part davantera. Les cues utilitzen un objecte encapsulat de deque o llista (classe de contenidor seqüencial) com a contenidor subjacent, proporcionant un conjunt específic de funcions membre per accedir als seus elements.
A continuació es mostra un exemple per demostrar la cua i els seus diferents mètodes.
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;> }> |
Sortida
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Els mètodes de cua són:
La complexitat temporal i la definició de les funcions següents són les següents:
| cua::buida() | O(1) |
| queue::size() | O(1) |
| queue::place() | O(1) |
| cua::front() | O(1) |
| queue::back() | O(1) |
| queue::push(g) | O(1) |
| queue::pop() | O(1) |
| Mètode | Definició |
|---|---|
| cua::buida() | Retorna si la cua està buida. Torna true si la cua està buida, en cas contrari retorna false. |
| queue::size() | Retorna la mida de la cua. |
| queue::swap() | Canvia el contingut de dues cues, però les cues han de ser del mateix tipus de dades, encara que les mides poden ser diferents. |
| queue::place() | Inseriu un element nou al contenidor de la cua, l'element nou s'afegeix al final de la cua. |
| cua::front() | Retorna una referència al primer element de la cua. |
| queue::back() | Retorna una referència a l'últim element de la cua. |
| queue::push(g) | Afegeix l'element 'g' al final de la cua. |
| queue::pop() | Esborra el primer element de la cua. |
Programa C++ per a alguns mètodes més
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> >temp = 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 |
Sortida
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
Les complexitats temporals i espacials de les operacions d'aquest codi són les següents:
funció print_queue:
Complexitat temporal: O(n), on n és el nombre d'elements de la cua.
Complexitat espacial: O(n), on n és el nombre d'elements de la cua.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Complexitat temporal: O(1) per a cada operació d'impuls.
Complexitat espacial: O(n), on n és el nombre total d'elements en ambdues cues.
q1.swap(q2):
Complexitat temporal: O(1) per a cada operació d'intercanvi.
Complexitat de l'espai: O(1), ja que aquesta operació només intercanvia els punters interns de les dues cues.
q1.empty():
Complexitat temporal: O(1), ja que aquesta operació simplement comprova si la cua està buida.
Complexitat de l'espai: O(1), ja que no s'utilitza cap espai addicional per a aquesta operació.
En general, les complexitats de temps i espai d'aquest codi són raonables i eficients per als casos d'ús típics.
Articles recents sobre la cua de C++
