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
elimina la memòria cau npm
// 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:
codi de mostra c#
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 |
>
mètodes de cadena java
>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():
com ordenar una matriu en java
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++