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

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

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

  1. Статия за структурата данни "Double-ended queue" (en.wikipedia.org)
  2. STL Deque (www.cplusplus.com)
  3. Обикновена опашка (www.informatika.bg)
  4. Квадратична опашка (www.informatika.bg)


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

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: