Как Deque работает внутри C++?

Как преобразовать строку в int в C++ Программирование и разработка

Deque или Double Ended Queue — это обобщенная версия структуры данных Queue, которая позволяет выполнять вставку и удаление на обоих концах. Он поддерживает доступ к элементам с временной сложностью O (1), а вставка и удаление элементов спереди и сзади выполняются с временной сложностью O (1).

Практическое применение Deque

Способность Deque вставлять и удалять с обеих сторон делает его одним из самых полезных контейнеров в STL. Реальные приложения упомянуты ниже:

  1. Применяется и как стек, и как очередь, поскольку поддерживает обе операции.
  2. Хранение истории веб-браузера.
  3. Хранение списка операций отмены программного приложения.
  4. Алгоритм планирования работы

Как Deque работает внутри C++ STL

Двухсторонняя очередь STL реализуется с использованием массивов данных или массивов указателей на блоки памяти, а не связанного списка. В зависимости от требований к хранилищу количество блоков и размер массива указателей динамически колеблются. Эти блоки памяти содержат элементы в соседних местах.

Блок памяти автоматически выделяется при создании объекта очереди, чтобы объекты можно было хранить в смежных местах.

  1. Затем Deque выделяет новый блок памяти и присоединяется к нему перед предыдущим блоком памяти, когда мы помещаем элемент перед ним. Теперь, если мы еще раз добавим фрагменты на передний план, они будут храниться в этом новом блоке памяти, пока он полностью не заполнится.
  2. Когда элемент вставляется в конец двухсторонней очереди, выделенный блок памяти удерживает его до тех пор, пока он не будет полностью заполнен; если это происходит, выделяется новый блок памяти и подключается к концу предыдущего блока. Элементы, добавленные в конец дека, теперь хранятся в этом новом блоке памяти.

Так как деку не нужно сдвигать элемент на 1, как это делает массив в блоке памяти, чтобы освободить место впереди, вы можете думать о ней как о связанном списке векторов. Чтобы выделить ему новый блок памяти, он сначала определяет, осталось ли место перед первым элементом в текущем блоке памяти.

Сложность времени:

  • Доступ к элементам — O(1)
  • Вставка или удаление элементов — O(N)
  • Вставка или удаление элементов в начале или конце — O(1)
Читайте также:  Что означает пустота в Java?

Пример:

С++

// C++ code to show working of the deque
#include <deque>
#include <iostream>
using namespace std;
 
// Driver Code
int main()
{
    deque<int> d = { 1, 2, 3 };
 
    d.push_back(4);
    d.push_front(0);
 
    cout << "Elements in Deque: " << endl;
 
    for (int i : d)
        cout << i << " ";
    cout << endl;
 
    d.pop_back();
 
    cout << "\n"
         << "Elements in Deque after pop_back(): " << endl;
 
    for (int i : d)
        cout << i << " ";
    cout << endl;
 
    cout << "\n"
         << "Elements in Deque after pop_front(): " << endl;
 
    d.pop_front();
 
    for (int i : d)
        cout << i << " ";
    cout << endl;
 
    cout << "\n"
         << "Element in front of deque: " << d.front()
         << endl;
    cout << "Element in back of deque: " << d.back()
         << endl;
 
    cout << "Iteam at 1th Index: " << d.at(1) << endl;
 
    cout << "Size of deque: " << d.size() << endl;
    cout << "Is deque empty: " << d.empty() << endl;
 
    cout << "\n"
         << "After deleting all elements of deque:"
         << "\n\n";
 
    d.erase(d.begin(), d.end());
 
    cout << "Size of deque: " << d.size() << endl;
    cout << "Is deque empty: " << d.empty() << endl;
}

Вывод

Elements in Deque: 
0 1 2 3 4 

Elements in Deque after pop_back(): 
0 1 2 3 

Elements in Deque after pop_front(): 
1 2 3 

Element in front of deque: 1
Element in back of deque: 3
Iteam at 1th Index: 2
Size of deque: 3
Is deque empty: 0

After deleting all elements of deque:

Size of deque: 0
Is deque empty: 1

Оцените статью
bestprogrammer.ru
Добавить комментарий

Adblock
detector