Черга в стандартній бібліотеці шаблонів C++ (STL)
Черги — це тип контейнерних адаптерів, які працюють за типом організації «першим прийшов, першим вийшов» (FIFO). Елементи вставляються ззаду (торцем) і видаляються спереду. Черги використовують інкапсульований об’єкт deque або список (послідовний контейнерний клас) як базовий контейнер, надаючи певний набір функцій-членів для доступу до його елементів.
Нижче наведено приклад для демонстрації черги та її різних методів.
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;> }> |
Вихід
The queue gquiz is : 10 20 30 gquiz.size() : 3 gquiz.front() : 10 gquiz.back() : 30 gquiz.pop() : 20 30
Методи черги:
Часова складність і визначення наступних функцій наступні:
| queue::empty() | О(1) |
| queue::size() | О(1) |
| queue::place() | О(1) |
| queue::front() | О(1) |
| queue::back() | О(1) |
| queue::push(g) | О(1) |
| queue::pop() | О(1) |
| метод | Визначення |
|---|---|
| queue::empty() | Повертає, чи черга порожня. Він повертає true, якщо черга порожня, інакше повертає false. |
| queue::size() | Повертає розмір черги. |
| queue::swap() | Обмінюйтеся вмістом двох черг, але черги мають бути одного типу даних, хоча розміри можуть відрізнятися. |
| queue::place() | Вставте новий елемент у контейнер черги, новий елемент буде додано в кінець черги. |
| queue::front() | Повертає посилання на перший елемент черги. |
| queue::back() | Повертає посилання на останній елемент черги. |
| queue::push(g) | Додає елемент «g» у кінець черги. |
| queue::pop() | Видаляє перший елемент черги. |
C++ програма для деяких інших методів
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 |
Вихід
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
Часові та просторові складності операцій у цьому коді такі:
функція print_queue:
Часова складність: O(n), де n – кількість елементів у черзі.
Складність простору: O(n), де n – кількість елементів у черзі.
q1.push(1), q1.push(2), q1.push(3), q2.push(4), q2.push(5), q2.push(6):
Часова складність: O(1) для кожної операції натискання.
Складність простору: O(n), де n – загальна кількість елементів в обох чергах.
q1.swap(q2):
Часова складність: O(1) для кожної операції обміну.
Складність простору: O(1), оскільки ця операція міняє місцями лише внутрішні покажчики двох черг.
q1.empty():
Часова складність: O(1), оскільки ця операція просто перевіряє, чи черга порожня.
Складність простору: O(1), оскільки для цієї операції не використовується додатковий простір.
Загалом, часові та просторові складності цього коду розумні та ефективні для типових випадків використання.
Останні статті про чергу C++
