Черги з двостороннім доступом

Черга з двостороннім доступом (deque) являє собою щось схоже і на вектор, і на зв’язаний список. Як і вектор, цей тип контейнера підтримує довільний доступ []. Як і в списку, доступ може бути одержаний до кінця і до початку черги. В цілому це нагадує вектор з двома кінцями. Підтримуються функції front(), push_front і pop_front().

Для векторів і двосторонніх черг пам’ять резервується по-різному. Вектор завжди займає суміжні ділянки пам’яті. Тому при його розростанні резервується нова ділянка пам’яті, де контейнер може поміститися цілком. Натомість черга з двостороннім доступом може розміщуватися в кількох сегментах пам’яті, не обов’язково суміжних. В цьому є і плюси, і мінуси. Черга гарантовано буде розміщена в пам’яті, однак доступ до сегментованих об’єктів буде повільнішим.

Далі приведений приклад програми, яка працює з чергою:

#include<iostream>

#include<conio>

#include<deque>

using namespace std;

int main()

{deque<int>deq;

deq.push_back(30);

deq.push_back(40);

deq.push_back(50); //проштовхування елемента в кінець

deq.push_front(20);

deq.push_front(10);//проштовхування елемента в початок

deq[2]=33;//зміна довільного елементу контейнера

for(int j=0;j<deq.size();j++)

cout<<deq[j]<<" ";//вивести елемент

cout<<endl;

getch();

return 0;

}

Програма 15.16