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

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

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

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

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

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

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

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

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

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

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

Доступ к элементам — O(1)
Вставка или удаление элементов — O(N)
Вставка или удаление элементов в начале или конце — O(1)

Пример:

С++

// 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