Ред са два краја

У информатици, ред са два краја (енгл. Доубле-ендед-qуеуе, углавном се пише деqуе, изговара се дек) је апстрактан тип података који је уопштење реда, у који се елементи могу додавати или уклањати са почетка(главе) или краја(репа).^[1]

Именовање уреди

Деqуе се понекад пише и као деqуеуе, али се тај термин углавном не користи пошто је деqуеуе такође глагол који значи "уклонити из реда". Упркос томе, неколико библиотека и неки аутори, као Ахо, Хопкрофт, и Улман у свом уџбенику Структуре података и алгоритми(Дата струцтурес анд алгоритхмс), користе термин деqуеуе. Џон Мичел, аутор дела Концепти у програмским језицима(Цонцептс ин Программинг Лангуагес), такође користи овај термин.

Разлике и подтипови уреди

Разликује се од реда који ради на принципу ФИФО, у који се елементи само могу додати на један крај а вадити са другог краја. Деqуе може да има неке од следећих подтипова:

Деqуе са ограничењем на улаз: брисање елемената се може вршити на оба краја док се убацивање може вршити само на једном крају.
Деqуе са ограничењем на излаз: убацивање елемената се може вршити на оба краја док се брисање може вршити само на јредом крају.

Основни као и најуобичајенији типови листа у рачунарству, редови и стекови се могу сматрати посебним обликом редова са два краја, и могу се имплементирати коришћењем истих.

Операције уреди

Основне операције које се могу вршити су убацивање и вађење са било ког краја. Углавном се и имплементира операција која ће да врати вредност са било ког од крајева деqуе-а без његовог брисања.

Имена се разликују међу језицима; неки од значајнијих језика:

операција	уобичајена имена	Ада	C++	Јава	Перл	ПХП	Пyтхон	Рубy	ЈаваСцрипт
убацити елемент на крај	ињецт, сноц	`Append`	`push_back`	`offerLast`	`push`	`array_push`	`append`	`push`	`push`
убацити елемент на почетак	пусх, цонс	`Prepend`	`push_front`	`offerFirst`	`unshift`	`array_unshift`	`appendleft`	`unshift`	`unshift`
избрисати последњи елемент	ејецт	`Delete_Last`	`pop_back`	`pollLast`	`pop`	`array_pop`	`pop`	`pop`	`pop`
избрисати први елемент	поп	`Delete_First`	`pop_front`	`pollFirst`	`shift`	`array_shift`	`popleft`	`shift`	`shift`
погледати последњи елемент		`Last_Element`	`back`	`peekLast`	`$array[-1]`	`end`	`<obj>[-1]`	`last`	`<obj>[<obj>.length - 1]`
погледати први елемент		`First_Element`	`front`	`peekFirst`	`$array[0]`	`reset`	`<obj>[0]`	`first`	`<obj>[0]`

Имплементације уреди

Постоје најмање два уобичајена начина за ефикасно имплементирање деqуе-а: коришћењем модификованог динамичког низа или двоструко повезане листе.

Приступ коришћењем динамичког низа користи варијанту динамичког низа који може да се проширује са оба краја. Такви низови имају сва својства динамичких низова, као што су константно време насумичном приступу подацима, добра локалност референци, неефикасно убацивање/избацивање елемената у средини, као и амортизовано константно време за убацивање/брисање на оба краја, уместо само на једном крају. Три уобичајене имплементације:

Складиштење деqуе-а у кружном баферу који се проширује тек када се напуни до краја. Овиме се постиже мања учесталост проширивања.
Алоцирање садржаја деqуе-а почевши од центра низа који се користи за реализацију и проширивање истог тек кад се достигне било који од крајева. Овакав приступ може захтевати учесталија проширивања и трошити више простора, посебно када се елементи додају само са једног краја.
Складиштење садржаја у више мањих низова, притом алоцирајући додатне низове с почетка или краја по потреби. Индексирање се имплементира тако што се користи динаминчки низ који чува показиваче на сваки од мањих низова.

Подршка од стране програмских језика уреди

Ада-ини контејнери обезбеђују генеричке пакете: Ада.Цонтаинерс.Вецторс који садржи имплементацију динамичких низова, односно Ада.Цонтаинерс.Доублy_Линкед_Листс који садржи имплементацију двоструко повезаних листи.

C++-ова библиотека стандардних шаблона овезбеђује шаблоне класа стд::деqуе и стд::лист које садрже имплементације деqуе-а, односно листа.

Од верзије 6, Јава-ин Цоллецтионс Фрамеwорк обезбеђује нови Deque интерфејс који обезбеђује функционалност уметања и брисања са оба краја. Класе као сто су ArrayDeque (која је такође новина у Јава 6) и LinkedList имплементирају овај интефејс и обезбеђују имплементације динамичког низа, односно повезаних листи. Међутим, тхе АрраyДеqуе, насупрот свом имену, не подржава насумичан приступ елементима.

Пyтхон 2.4 је увео collections модул са подршком за деqуе објекте. Од верзије 5.3, проширење ПХП-ове СПЛ садржи 'СплДоублyЛинкедЛист' класу која се може користити за имплементацију деqуе-а. Претходно су се морале користити низовне функције арраy_схифт/унсхифт/поп/пусх да би се направио деqуе.

ГХЦ-ов Дата.Сеqуенце модул имплементира ефикасан, функционалан ред са два караја у Хаскелу. Имплементација користи 2-3 стабло са прибележеним величинама. Постоје и друге могућности за имплементацију чисто функционалних редова са два краја (већином користећи лењо израчунавање).^[2]^[3]

Сложеност уреди

У имплементацији која користи двоструко повезану листу изузимајући време потребно за алокацију/деалокацију временска сложеност свих операција је О(1). Узгред, временска сложеност убацивања и брисања елемената у средини је такође О(1) ако се користи итератор. Додуше, временска сложеност за приступ елементу користећи индекс је О(н).
Користећи проширив низ, амортизована временска сложеност свих операција је О(1). Такође је и временска сложеност насумичног приступа елементу О(1), док је временска сложеност уметања и брисања елемената из средине О(н).

Примене уреди

Пример где деqуе може бити употребљен је А-Стеал алгоритам за распоређивање послова.^[4] Овај алгоритам имплементира распоређивање послова за неколико процесора. Чува се засебан деqуе за сваки од процесора који садржи нити које сваки процесор треба да изврши. Да би извршио следећу нит, процесор узима елемент из деqуе-а (користећи операцију "избриши први елемент"). Ако тренутна нит направи копију себе(форк-ује), ставља се на почетак деqуе-а (користећи операцију "убацити на почетак реда") и покреће се нова нит. Када један од процесора заврши извршење својих нити (тј. ред је празан), може да "украде" нит другог процесора тако што узима последњи елемент из деqуе-а другог процесора (користећи операцију "избриши последњи елемент") и извршава ту нит. Овај алгоритам користи Интел-ова Тхреадинг Буилдинг Блоцкс (ТББ) библиотека за паралелно програмирање.

Види још уреди

Референце уреди

^ Кнутх, Доналд (1997). „Стацкс, Qуеуес, анд Деqуес”. Тхе Арт оф Цомпутер Программинг: Фундаментал Алгоритхмс. 1 (3рд изд.). Волуме 1: Аддисон-Wеслеy. стр. 238—243. ИСБН 978-0-201-89683-1.
^ http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf C. Окасаки, "Пурелy Фунцтионал Дата Струцтурес", Септембер 1996
^ Буцхсбаум, А.L.; Тарјан, Р.Е. (1995). „Цонфлуентлy персистент деqуес виа дата струцтурал боотстраппинг”. Јоурнал оф Алгоритхмс. 18 (3): 513—547. С2ЦИД 5551651. дои:10.1006/јагм.1995.1020.
^ Еитан Фрацхтенберг, Уwе Сцхwиегелсхохн (2007). Јоб Сцхедулинг Стратегиес фор Параллел Процессинг: 12тх Интернатионал Wорксхоп, ЈССПП 2006. Спрингер. ИСБН 978-3-540-71034-9. Сее пп. 22.

Литература уреди

Еитан Фрацхтенберг, Уwе Сцхwиегелсхохн (2007). Јоб Сцхедулинг Стратегиес фор Параллел Процессинг: 12тх Интернатионал Wорксхоп, ЈССПП 2006. Спрингер. ИСБН 978-3-540-71034-9. Сее пп. 22.

Спољашње везе уреди

[1] Кнутх, Доналд (1997). „Стацкс, Qуеуес, анд Деqуес”. Тхе Арт оф Цомпутер Программинг: Фундаментал Алгоритхмс. 1 (3рд изд.). Волуме 1: Аддисон-Wеслеy. стр. 238—243. ИСБН 978-0-201-89683-1.

[2] ttp://www.cs.cmu.edu/~rwh/theses/okasaki.pdf C. Окасаки, "Пурелy Фунцтионал Дата Струцтурес", Септембер 1996

[3] Буцхсбаум, А.L.; Тарјан, Р.Е. (1995). „Цонфлуентлy персистент деqуес виа дата струцтурал боотстраппинг”. Јоурнал оф Алгоритхмс. 18 (3): 513—547. С2ЦИД 5551651. дои:10.1006/јагм.1995.1020.

[4] Еитан Фрацхтенберг, Уwе Сцхwиегелсхохн (2007). Јоб Сцхедулинг Стратегиес фор Параллел Процессинг: 12тх Интернатионал Wорксхоп, ЈССПП 2006. Спрингер. ИСБН 978-3-540-71034-9. Сее пп. 22.

[1]

[2]

[3]

[4]