Двустранна опашка

Double-ended Queue

В тази тема ще разгледаме абстрактната структура данни "Двустранна Опашка" (също позната като "Дек") и нейна конкретна имплементация чрез "Циклична Опашка". Ще видим как тя съхранява данните, какви операции поддържа, и с каква сложност се изпълнява всяка от тях. Допълнително ще видим защо е хубаво да имплементираме структурите данни върху динамичен масив, вместо да заделяме памет за всеки нов елемент. В края на темата сме предоставили пълна имплементация като шаблонен клас, както и код, с който да тествате ваша такава.

Автор: Александър Георгиев

След като разгледахме какво е опашка, сега ще видим едно по-специално нейно надграждане - така наречената "двустранна опашка" или "дек" ("double-ended queue" или "deque" на английски). При нея имаме допълнителна фукнционалност: можем да добавяме и вадим елементи както от началото, така и от края на опашката, а също така и да достъпваме константно елементи с произволен индекс (а не само тези в краищата). Освен допълнителната функционалност, друг плюс на тази имплементация е, че работи малко по-бързо на практика, тъй като заделя памет на по-големи парчета и се възползва от cache locality, тъй като елементите на опашката се държат в последователни блокове памет.

Опашка в динамичен масив

До сега разгледахме една от възможните имплементации на опашка - ползвайки свързан списък. Съществува обаче и друг начин, по който може да бъде имплементирана тя - пазейки данните в динамичен масив. Тъй като заделянето на голямо парче памет обикновено е по-бързо, отколкото на много на брой малки парчета (а също така и заради това как работи кеша на паметта), то ползвайки динамичен масив на практика можем да постигнем по-добро бързодействие. Нещо повече, тъй като елементите са разположени последователно в масив, можем да имплементираме операции, които са невъзможни във варианта със свързан списък - например O(1) достъп до произволен елемент в опашката.

Циклична опашка

На пръв поглед не можем просто да "премахнем" първия елемент на масив с O(1) - за целта би трябвало да преместим всички останали елементи с една позиция наляво. Вместо да правим това, ще ползваме една идея, която се нарича "циклична опашка". Идеята е относително проста и ще разгледаме тук.

Менажиране на паметта

Както и при динамичния масив ще заделяме нова памет и копираме досегашните елементи в нея само когато се наложи да пазим повече елементи, от бройката, за които сме заделили памет. Вече видяхме, че амортизираната сложност на това "разширяване" е O(N) за добавянето на N елемента. Ще считаме, че ползваме vector за менажиране на паметта и не ни се налага да го разширяваме (тоест винаги имаме достатъчно място за елементите).

Цикличност на елементите

За разлика от стандартния масив, в цикличния вариант първият елемент може да не е на нулева позиция, ами на произволна такава (която ще индексираме с променлива head). Допълнително, нека масивът има общо CAPACITY на брой клетки. Ще считаме, че елементите му са "зациклени" - тоест, че след последната клетка в масива (с индекс CAPACITY-1) следва отново първата (с индекс 0). Така ако имаме индекса на първата клетка head и броя елементи size, които пазим в масива, то индексът на последния от тях е (head + size - 1) % CAPACITY. Забележете, че така е възможно последната клетка да има по-малък индекс от първата!

Добавяне на елемент

Нека разгледаме как можем да добавим нов елемент съответно в началото и в края на опашката. Първо трябва да си гарантираме, че има поне една свободна клетка - тоест ако size == CAPACITY трябва да разширим динамичния масива. Ако имаме свободна клетка, то сме сигурни, че клетките с индекси (head - 1 + CAPACITY) % CAPACITY и (head + size) % CAPACITY са свободни (а в случая, когато има само една свободна клетка, тези индекси ще съвпадат). Така съответните операции са:

Ако искаме да добавим елемент в началото на опашката правим head = (head - 1 + CAPACITY) % CAPACITY, слагаме го на тази позиция и увеличаваме size с единица.
Ако искаме да добавим елемент в края на опашката го слагаме на позиция (head + size) % CAPACITY и увеличаваме size с единица.

Независимо дали добавяме в началото или края, всички операции, които правим са константни, съответно и самото добавяне е O(1).

Премахване на елемент

Премахването на елемент (от началото или края на опашката) е сходно с добавянето. Първо проверяваме, дали имаме поне един елемент в опашката (тоест дали size > 0). Ако нямаме, то хвърляме някакъв exception или печатаме съобщение за грешка. Ако имаме, съответните операции са:

Ако искаме да премахнем елемента в началото на опашката, правим head = (head + 1) % CAPACITY, и след това намаляваме size с единица.
Ако искаме да премахнем елемента в края на опашката, просто намаляваме size с единица.

И в двата случая имаме само модификация на променливи, съответно премахването на елемент (независимо дали е от началото или края) също е със сложност O(1).

Достъп до елементите

Освен достъп до първия и последния елемент в опашката (които са с индекси, съответно, head и (head + size - 1) % CAPACITY), можем да индексираме елемент на произволен индекс index - той ще е на позиция (head + index) % CAPACITY. Както знаем индексирането в масив е константно, съответно достъпът до всеки един елемент от опашката става с O(1).

Допълнителни операции

Не е изискване двустранната опашка да поддържа тези операции, но често те биват имплементирани (включително в STL-ския deque).

Ако искаме да добавим елемент на произволна позиция index, то първо местим всички елементи с индекси (head + index) % CAPACITY, head + index + 1) % CAPACITY, ... (head + size - 1) % CAPACITY с една позиция надясно, после поставяме новия елемент на позиция (head + index) % CAPACITY, и накрая увеличаваме size с единица.
Ако искаме да премахнем елемент от произволна позиция index, то местим елементите с индекси (head + index + 1) % CAPACITY, head + index + 2) % CAPACITY, ... (head + size - 1) % CAPACITY с една позиция наляво, и после намаляваме size с единица.

?	Лека оптимизация тук би било да видим кои елементи са по-малко на брой - тези преди `index` или тези след него и да местим тях. В най-лошия случай обаче все пак трябва да преместим `size/2` елемента, тоест операцията е линейна.

Забележете, че докато добавянето и премахването на елемент от началото и края на опашката беше доста "евтино" (константно), то правенето на това на и от произволна позиция изисква преместването на потенциално всички или почти всички елементи - тоест е O(size).

Двустранна опашка (дек)

Двустранна опашка или дек (от английски: deque = double-ended queue), както ще го срещнете по-често, представлява опашка с два края - хора могат да се нареждат както в края на опашката (както е при стандартната опашка), така и да предреждат всички и да се нареждат в нейното начало. Това е полезно ако има хора (обекти) с два вида приоритет - стандартен (които биват нареждани на края на опашката) и висок (които биват нареждани в началото на опашката).

Примерна задача

Имате поле с N реда и M колони. Някои от клетките са заледени, докато други не са. Можете или да пристъпите в съседна по хоризонтала или вертикала клетка за време 1 секунда, или да се плъзнете по хоризонтална или вертикална отсечка от две или повече заледени клетки за време 1 секунда за цялото плъзгане.

Дадено ви е кои клетки са заледени и кои не, а също така в коя клетка започвате и до коя искате да стигнете. Пита се какво е най-малкото време, за което можете да стигнете до там?

Задачата напомня на стандартно търсене в ширина, ама не съвсем. Тъй като трябва да разглеждате последователности от заледени клетки, наивната имплементация би била със стейт [N][M] (в коя клетка се намирате в момента) и сложност O(N∙M∙max(N, M)), тъй като от всяка клетка бихте разгледали до O(max(N, M)) продължения.

Вместо това можете да имате стейт [N][M][4] (в коя клетка се намирате в момента и каква е била последната ви посока на движение). Така ако в момента сте на заледена клетка и искате да се преместите в друга заледена клетка в същата посока, в която сте се движили до сега, това би било с цена 0 (просто сте се "плъзнали"). Можете да ползвате двустранна опашка и да добавяте такива състояния в началото на опашката, постигайки сложност O(N∙M).

Интерфейс

?	Всяко нещо си има край. Само кренвиршът и двустранната опашка имат два края.

Двустранната опашка представлява надграждане на стандартната опашка, като може да бъде реализирана по сходен начин или с (дву)свързан списък (която имплементация ползвахме за стандартната опашка), или с циклична опашка (чиято идея разгледахме в началото на тази тема и сме ползвали при примерната реализация). В интерфейса на тази структура данни има няколко разлики:

push() се казва push_back()
pop() се казва pop_front()
Има допълнителен метод push_front(), който добавя елемент в началото на опашката
Има допълнителен метод pop_back(), който премахва елемент от края на опашката

Възползвайки се от начина на имплементация (ползвайки динамичен масив за пазене на елементите, съответно поставяйки ги последователно в едно парче памет) в примерната реализация сме имплементирали и функция at(index), която връща елемент с произволен индекс за O(1). Забележете, че не можем да премахнем този елемент с тази сложност - можем единствено да вземем (и, потенциално, променим) неговата стойност.

Имплементация

Ще приемем, че ползваме прости типове (int, double, long long, и т.н.), за които не е нужно да се вика деструктор при pop_front() и pop_back(). В пълната имплементация, която сме дали най-долу, се справяме и с това.

Данни

Ще пазим следните данни: самите елементи (data), броя елементи, които в момента опашката съдържа (size), максималния брой елементи, които текущият масив с данни може да съхранява (capacity), и индекса на първия валиден елемент (head)

struct Deque {
    DataType*
 data;
    int
 head,
 size,
 capacity;
    Deque() {
        data =
 nullptr;
        head =
 size =
 capacity =
 0
;
    }
};

Инициализация

Инициализира опашката. Повторно викане без да се изтрие масивът с данните ще доведе до memory leak.

void
 init(Deque&
 deque) {
    deque.size =
 deque.head =
 0
;
    deque.capacity =
 INIT_CAPACITY;
    deque.data =
 new
 DataType[deque.capacity];
}

Трябва да зададем начален размер на масива с данните и да заделим памет за него.

size()

Връща броя налични елементи в масива.

int
 size(Deque&
 deque) {
    return
 deque.size;
}

empty()

Проверява дали опашката е празна.

bool
 empty(Deque&
 deque) {
    return
 deque.size =
=
 0
;
}

clear()

Премахва всички елементи от опашката.

void
 clear(Deque&
 deque) {
    if
 (deque.data !
= nullptr)
        delete
 [] deque.data;
    init(deque
);
}

Ако вече сме заделили памет, трябва да я изтрием, след което да инициализираме данните наново.

reserve()

Променя размера на масива, който ползваме за съхранение на данните.

void
 reserve(Deque&
 deque
,
 int nsize) {
    DataType*
 ndata =
 new
 DataType[nsize];
    for
 (int
 i =
 0
;
 i <
 deque.size;
 i+
+)
        ndata[i] =
 deque.data[(deque.head +
 i) %
 deque.capacity];
    delete
 [] deque.data;
    deque.capacity =
 nsize;
    deque.data =
 ndata;
    deque.head =
 0
;
}

Сходно с динамичния масив, когато не ни достига място, увеличаваме размера на масива с данните двойно и копираме елементите там. Забележете, че можем единствено да разширяваме масива - смаляването му може да доведе до crash.

push_front()

Добавя елемент в началото на опашката.

void
 push_front(Deque&
 deque
,
 const
 DataType& value) {
    if
 (deque.capacity =
= deque.size)
        reserve(deque
,
 deque.size *
 2
);
    deque.head =
 (deque.head +
 deque.capacity -
 1
) %
 deque.capacity;
    deque.data[deque.head] =
 value;
    deque.size+
+
;
}

Увеличаваме размера на масива с данните ако се налага, след което местим указателя към първия елемент с една позиция (циклично) наляво и слагаме новия елемент там. Разбира се, накрая не забравяме да увеличим броя елементи.

push_back()

Добавя елемент в края на опашката.

void
 push_back(Deque&
 deque
,
 const
 DataType& value) {
    if
 (deque.capacity =
= deque.size)
        reserve(deque
,
 deque.size *
 2
);
    deque.data[(deque.head +
 deque.size) %
 deque.capacity] =
 value;
    deque.size+
+
;
}

Увеличаваме размера на масива с данните ако се налага, след което слагаме новия елемент на позицията веднага след сегашния последен (циклично). Отново увеличаваме броя елементи.

pop_front()

Премахва първия ("най-предния") елемент от опашката.

void
 pop_front(Deque&
 deque) {
    assert(deque.size >
 0
);
    deque.head =
 (deque.head +
 1
) %
 deque.capacity;
    deque.size-
-
;
}

Проверяваме, че има поне един елемент, след което местим указателя към първия елемент с една позиция (циклично) надясно и намаляваме броя елементи.

pop_back()

Премахва последния ("най-задния") елемент от опашката.

void
 pop_back(Deque&
 deque) {
    assert(deque.size >
 0
);
    deque.size-
-
;
}

Проверяваме, че има поне един елемент, след което просто намаляваме броя елементи.

front()

Връща първия ("най-предния") елемент от опашката.

DataType&
 front(Deque&
 deque) {
    assert(deque.size >
 0
);
    return
 deque.data[deque.head];
}

Проверяваме, че имаме поне един елемент, след което връщаме сочения от указателя към първия елемент.

back()

Връща последния ("най-задния") елемент от опашката.

DataType&
 back(Deque&
 deque) {
    assert(deque.size >
 0
);
    return
 deque.data[(deque.head +
 deque.size -
 1
) %
 deque.capacity];
}

Проверяваме, че имаме поне един елемент, след което намираме индекса на последния (ползвайки указателя към първия и броя на елементите) и връщаме съответния елемент.

at(index)

Връща елемента на позиция index.

DataType&
 at(Deque&
 deque
,
 int index) {
    assert(index >
=
 0
 &
&
 index <
 deque.size);
    return
 deque.data[(deque.head +
 index) %
 deque.capacity];
}

Проверяваме, че желаният индекс е валиден, след което изчисляваме истинския индекс в цикличния масив и връщаме съответния елемент.

Цялостна имплементация

Цялостна имплементация и тестове: Deque.h | DequeTester.cpp

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 3968 пъти.