Ред (тип података)

У рачунарству, ред (енгл. queue) је посебна врста апстрактног типа података код којег су главне (или једине) операције додавање елемената на крај реда, као и уклањање елемената са почетка реда. Ред представља ФИФО структуру(енгл. First-In-First-Out], што подразумева да први елемент који се додаје у ред ће бити и први елемент који ће бити уклоњен из реда. Ово је еквивалентно са захтевом да када се дода нови елемент у ред, да би се он уклонио морају бити уклоњени сви елементи који су додати пре њега.

Примена реда

Ред је пример линеарне структуре података и доста се користи у рачунарству, транспорту и операционим истраживањима где се различити ентитети као што су подаци, предмети, лица или догађаји чувају, како би касније били обрађени. У овом контексту, ред обавља функцију бафера.

Редови су уобичајени у програмирању, где су имплементирани као структуре података заједно са приступним рутинама, као једна класа у објектно-оријентисаном програмирању. Заједничке имплементације су циркуларни бафери и повезане листе.

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

Теоретски, једна карактеристика реда је да нема специфичан капацитет. Без обзира на то колико елемената ред већ садржи, увек се може додати нови елемент. Ред такође може бити празан и у том случају уклањање елемента је немогуће све док се опет не дода нови елемент. Низови фиксиране дужине имају ограничен капацитет, али није истина да чланови низа морају бити копирани на почетак реда. Једноставан трик претварања низа у затворен круг и пустити главу и реп реда да се бесконачно врте у том кругу чини непотребним померање чланова низа. Ако је н дужина низа, онда индекси по модулу н ће окренути низ у круг. Ово је још увек концептуално најједноставнији начин да се изгради ред на језику високог нивоа, али је и даље спор јер индекси низа морају бити поређани од нуле до н, где је н величина низа, и то захтева време за проверу да ли је неки елемент изван границе низа. Величина низа мора бити декларисана пре времена, али неке имплементације удвоструче декларисану величину низа када дође до прекорачења. Већина модерних језика са објектима или показивачима садрже библиотеке са динамичким листама. Такве структуре података могу да немају ограничен капацитет поред меморијских ограничења. Прекорачење реда се дешава када покушамо да додамо елемент на попуњен ред, а поткорачење реда када покушамо да уклонимо елемент из празног реда.

Постоји неколико ефикасних имплементација ФИФО редова. Ефикасна имплементација подразумева да је време потребно за додавање елемента или уклањање елемента О(1).

Повезана листа
- Двоструко повезана листа има временску сложеност уметања и брисања елемента на оба краја О(1), тако да је природан избор за ред.
- Једноструко повезана листа има ефикасно убацивање и брисање елемента на једном крају. Међутим, мала модификација увођењем показивача ће омогућити ефикасну имплементацију реда.
Ред са два краја се имплементира уз помоћ модификованог динамичког низа.

Редови и програмски језици

Редови могу бити имплементирани као посебан тип података, или се могу посматрати као редови са два краја, ако нису имплементирани одвојено. Стандардна библиотека језика C++ дефинише "red" као класу која је ограничена само на операције додавања или уклањања. Од Ј2СЕ5.0, Јава садржи Ред интерфејс, који прецизира операције реда. ПХП има СплQуеуе класу и независне библиотеке.

Види још

Референце

Доналд Кнутх (1997). „Стацкс, Qуеуес, анд Деqуес”. Тхе Арт оф Цомпутер Программинг. Волуме 1: Фундаментал Алгоритхмс, Тхирд Едитион. Аддисон-Wеслеy. стр. 238-243. ИСБН 978-0-201-89683-1.
Тхомас Х. Цормен; Цхарлес Е. Леисерсон; Роналд L. Ривест; Цлиффорд Стеин (2001). „Стацкс анд qуеуес”. Интродуцтион то Алгоритхмс (2нд изд.). МИТ Пресс анд МцГраw-Хилл. стр. 200-204. ИСБН 978-0-262-03293-3.
Wиллиам Форд; Wиллиам Топп (2002). „Qуеуес анд Приоритy Qуеуес”. Дата Струцтурес wитх C++ анд СТЛ. Сецонд Едитион. Прентице Халл. стр. 386-390. ИСБН 978-0-13-085850-4.
Адам Дроздек (2005). „Стацкс анд Qуеуес”. Дата Струцтурес анд Алгоритхмс ин C++. Тхирд Едитион. Тхомсон Цоурсе Тецхнологy. стр. 137—169. ИСБН 978-0-534-49182-6.

Спољашње везе