Ред се може описати као не-примитивна линеарна структура података која следи ФИФО редослед у коме се елементи података убацују са једног краја (задњи крај) и бришу са другог краја (предњи крај). Друге варијације реда су кружни ред, двоструко завршени ред и ред приоритета.
Цомпарисон Цхарт
| Основа за поређење | Линеар Куеуе | Цирцулар Куеуе |
|---|---|---|
| Басиц | Организује елементе података и инструкције у редоследу један за другим. | Распоређује податке у кружном узорку где је последњи елемент повезан са првим елементом. |
| Редослед извршења задатка | Задаци се извршавају како би били постављени раније (ФИФО). | Редослед извршавања задатка може се променити. |
| Уметање и брисање | Нови елемент се додаје са задњег краја и уклања са предње стране. | Убацивање и брисање се може обавити на било којој позицији. |
| Перформансе | Неефикасан | Ради боље од линеарног реда. |
Дефиниција Линеар Куеуе
Линеарни ред је рационално прва на првом месту поредана. То је такозвано линеарно, јер личи на правац где су елементи позиционирани један за другим. Садржи хомогену колекцију елемената у које се додају нови елементи на једном крају и бришу са другог краја. Концепт реда се може разумети на примеру реда публике који чека испред шалтера за карте да би добио казалишну карту. У овом реду, особа се придружује задњем крају реда да би узела карту и карта се издаје на предњем крају реда.
Постоји неколико операција које се изводе у реду
- Прво, ред је иницијализован на нулу (тј. Празан).
- Одредите да ли је ред празан или не.
- Одредите да ли је ред пун или не.
- Уметање новог елемента са задњег краја (Енкуеуе).
- Брисање елемента са предње стране (Декуеуе).
Ред се може имплементирати на два начина
- Статички (помоћу поља)
- Динамично (помоћу показивача)
Ограничење линеарног реда је да креира сценарио у којем се нови елемент не може додати у ред чак и ако ред садржи празне просторе. Ова ситуација је илустрована на слици испод. Овде задња страна показује последњи индекс док су све кутије још увек празне, не може се додати нови елемент.
Дефиниција кружног реда
Кружни ред је варијанта линеарног реда који ефективно превазилази ограничење линеарног реда. У кружном реду, нови елемент се додаје на прву позицију реда ако је задња заузета и простор је на располагању. Када је у питању линеарни ред, уметање се може извршити само са задњег краја и брисања са предњег краја. У пуном реду након извршавања низа узастопних брисања у реду појављује се одређена ситуација у којој ниједан нови елемент не може да се дода даље, чак и ако је расположиви простор зато што стање подтока (Реар = мак - 1) још увек постоји.
Кружни ред спаја два краја кроз показивач где први елемент долази после последњег елемента. Такође прати и предњу и задњу страну, имплементирајући неке додатне логике тако да може пратити елементе које треба уметнути и избрисати. Са овим, кружни ред не генерише стање преливања све док се ред не попуни у стварном стању.
Неки услови праћени кружним редом:
- Фронт мора да показује на први елемент.
- Ред ће бити празан ако је Фронт = Реар.
- Када се дода нови елемент, ред се повећава за вредност један (Реар = Реар + 1).
- Када се неки елемент избрише из реда, предњи део се повећава за један (Фронт = Фронт + 1).
Кључне разлике између Линеар Куеуе и Цирцулар Куеуе
- Линеарни ред је редоследна листа у којој су елементи података организовани у редоследу редоследа. Насупрот томе, кружни ред чува податке на кружни начин.
- Линеарни ред следи ФИФО редослед за извршење задатка (елемент који се додаје на прву позицију ће бити избрисан на првој позицији). Насупрот томе, у кружном реду редослед операција које се изводе на елементу може да се промени.
- Уметање и брисање елемената је фиксно у линеарном реду тј. Додавање са задњег краја и брисање са предњег краја. С друге стране, кружни ред је способан да уметне и избрише елемент из било које тачке док се не заузме.
- Линеарни ред испушта меморијски простор, док кружни ред омогућава ефикасно коришћење простора.
Имплементација линеарног реда
Алгоритам који је дат испод илуструје додавање елемената у ред:
Ред треба три варијабле података укључујући један низ за чување реда, а други за складиштење предње и задње почетне позиције која је -1.
инсерт (итем, куеуе, н, реар) {иф (реар == н) и печати "куеуе оверфлов"; друго {задње = задње + 1; ред [задња] = ставка; }} Алгоритам који је дат испод илуструје брисање елемената у реду:
делете_цирцулар (итем, куеуе, реар, фронт) {иф (реар == фронт), а затим принт "куеуе ундерфлов"; елсе {фронт = фронт + 1; итем = куеуе [фронт]; }} Имплементација кружног реда
Алгоритам за тумачење додавања елемента у кружном реду:
инсерт_цирцулар (ставка, ред, задњи, предњи) {задња = (задња + 1) мод н; ако (предња == задња) онда се штампа "ред је пун"; елсе {куеуе [реар] = итем; }} Алгоритам објашњава брисање елемента у кружном реду:
делете_цирцулар (итем, куеуе, реар, фронт) {иф (фронт == реар) принт ("куеуе ис емпти"); елсе {фронт = фронт + 1; итем = куеуе [фронт]; }} Закључак
Линеарни ред је неефикасан у одређеним случајевима када су елементи потребни за пребацивање на празна мјеста како би се извршила операција уметања. То је разлог због којег настаје расипање простора за складиштење, док кружни ред користи одговарајуће простор за складиштење јер се елементи додају на било којој позицији ако постоји празан простор.
