Kolejki to rodzaj adapterów kontenerów, które działają w układzie FIFO (pierwsze weszło, pierwsze wyszło). Elementy wstawiane są od tyłu (końca) i usuwane od przodu. Kolejki używają hermetyzowanego obiektu deque lub lista (sekwencyjna klasa kontenera) jako kontener bazowy, zapewniający określony zestaw funkcji członkowskich umożliwiających dostęp do jego elementów.
Poniżej znajduje się przykład ilustrujący kolejkę i jej różne metody.
CPP
Podstawowe informacje o kompilacji Ubuntu
// 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;> }> |
>
>Wyjście
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30>
Metody kolejkowania to:
jsp javatpoint
Złożoność czasowa i definicja następujących funkcji są następujące:
| kolejka::pusta() | O(1) |
| kolejka::rozmiar() | O(1) |
| kolejka::miejsce() | O(1) |
| kolejka::front() | O(1) |
| kolejka::wstecz() | O(1) |
| kolejka::push(g) | O(1) |
| kolejka::pop() | O(1) |
| metoda | Definicja |
|---|---|
| kolejka::pusta() | Zwraca informację, czy kolejka jest pusta. Zwraca wartość true, jeśli kolejka jest pusta, w przeciwnym razie zwraca wartość false. |
| kolejka::rozmiar() | Zwraca rozmiar kolejki. |
| kolejka::zamień() | Wymieniaj zawartość dwóch kolejek, ale kolejki muszą być tego samego typu danych, chociaż rozmiary mogą się różnić. |
| kolejka::miejsce() | Wstaw nowy element do kontenera kolejki, nowy element zostanie dodany na koniec kolejki. |
| kolejka::front() | Zwraca referencję do pierwszego elementu kolejki. |
| kolejka::wstecz() | Zwraca referencję do ostatniego elementu kolejki. |
| kolejka::push(g) | Dodaje element „g” na końcu kolejki. |
| kolejka::pop() | Usuwa pierwszy element kolejki. |
Program C++ dla kilku dodatkowych metod
C++
przekreślenie przeceny
// 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>>temperatura = 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 |
>
>Wyjście
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>
Złożoność czasowa i przestrzenna operacji w tym kodzie jest następująca:
funkcja print_queue:
Złożoność czasowa: O(n), gdzie n jest liczbą elementów w kolejce.
Złożoność przestrzenna: O(n), gdzie n jest liczbą elementów w kolejce.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Złożoność czasowa: O(1) dla każdej operacji push.
Złożoność przestrzenna: O(n), gdzie n jest całkowitą liczbą elementów w obu kolejkach.
q1.zamień(q2):
Złożoność czasowa: O(1) dla każdej operacji wymiany.
Złożoność przestrzenna: O(1), ponieważ ta operacja zamienia tylko wewnętrzne wskaźniki obu kolejek.
q1.puste():
Algorytm „prima”
Złożoność czasowa: O(1), ponieważ ta operacja po prostu sprawdza, czy kolejka jest pusta.
Złożoność przestrzenna: O(1), ponieważ do tej operacji nie jest wykorzystywana żadna dodatkowa przestrzeń.
Ogólnie rzecz biorąc, złożoność czasowa i przestrzenna tego kodu jest rozsądna i wydajna w typowych przypadkach użycia.
Najnowsze artykuły na temat kolejki C++