Jono C++ Standard Template Libraryssa (STL)
Jonot ovat eräänlaisia konttisovittimia, jotka toimivat FIFO-tyyppisessä järjestelyssä. Elementit lisätään taakse (päähän) ja poistetaan edestä. Jonot käyttävät kapseloitua deque-objektia tai lista (peräkkäinen säiliöluokka) sen taustalla oleva säilöntä, joka tarjoaa tietyn joukon jäsentoimintoja, joiden avulla pääset käsiksi sen elementteihin.
Seuraavassa on esimerkki jonon ja sen eri menetelmien havainnollistamiseksi.
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;> }> |
Lähtö
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Jonomenetelmät ovat:
Seuraavien funktioiden aikamonimutkaisuus ja määritelmät ovat seuraavat:
| jono::tyhjä() | O(1) |
| jono::koko() | O(1) |
| jono::paikka() | O(1) |
| jono::front() | O(1) |
| jono::takaisin() | O(1) |
| jono::push(g) | O(1) |
| jono::pop() | O(1) |
| Menetelmä | Määritelmä |
|---|---|
| jono::tyhjä() | Palauttaa, onko jono tyhjä. Se palauttaa tosi, jos jono on tyhjä, muuten palauttaa false. |
| jono::koko() | Palauttaa jonon koon. |
| jono::swap() | Vaihda kahden jonon sisältö, mutta jonojen on oltava samaa tietotyyppiä, vaikka koot voivat vaihdella. |
| jono::paikka() | Lisää uusi elementti jonosäiliöön, uusi elementti lisätään jonon loppuun. |
| jono::front() | Palauttaa viittauksen jonon ensimmäiseen elementtiin. |
| jono::takaisin() | Palauttaa viittauksen jonon viimeiseen elementtiin. |
| jono::push(g) | Lisää elementin 'g' jonon loppuun. |
| jono::pop() | Poistaa jonon ensimmäisen elementin. |
C++-ohjelma joillekin muille menetelmille
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> >lämpötila = 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 |
Lähtö
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
Tämän koodin toimintojen aika- ja tilamonimutkaisuudet ovat seuraavat:
print_queue-toiminto:
Aika monimutkaisuus: O(n), missä n on jonon elementtien lukumäärä.
Tilan monimutkaisuus: O(n), missä n on jonon elementtien lukumäärä.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Aika monimutkaisuus: O(1) jokaiselle push-operaatiolle.
Tilan monimutkaisuus: O(n), missä n on elementtien kokonaismäärä molemmissa jonoissa.
q1.swap(q2):
Aika monimutkaisuus: O(1) jokaiselle swap-operaatiolle.
Tilan monimutkaisuus: O(1), koska tämä toiminto vaihtaa vain kahden jonon sisäiset osoittimet.
q1.empty():
Aika monimutkaisuus: O(1), koska tämä toiminto yksinkertaisesti tarkistaa, onko jono tyhjä.
Tilan monimutkaisuus: O(1), koska tähän operaatioon ei käytetä ylimääräistä tilaa.
Kaiken kaikkiaan tämän koodin aika- ja tilamonimutkaisuus on kohtuullinen ja tehokas tyypillisiin käyttötapauksiin.
Viimeisimmät artikkelit C++-jonosta
