logo

TechCodeview

Декуе (или двострани ред)

У овом чланку ћемо разговарати о двостраном реду или низу. Прво би требало да видимо кратак опис реда.

Шта је ред?

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

линук пречице на тастатури

Пример из стварног света је ред за улазнице испред биоскопске сале, где особа која прва уђе у реду добија карту прва, а особа која уђе последња у реду добија карту на крају.

Шта је Декуе (или двострани ред)

Декуе је скраћеница од Доубле Ендед Куеуе. Декуе је линеарна структура података у којој се операције уметања и брисања изводе са оба краја. Можемо рећи да је декуе генерализована верзија реда.

Иако се уметање и брисање у низу може извршити на оба краја, оно не прати ФИФО правило. Репрезентација дека је дата на следећи начин -

Декуе (или двострани ред)

Врсте дека

Постоје две врсте дека -

  • Ограничени ред за унос
  • Излаз ограничени ред

Унос ограничен ред чекања

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

Декуе (или двострани ред)

Излаз ограничен ред чекања

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

Декуе (или двострани ред)

Операције изведене на декуе

Постоје следеће операције које се могу применити на декуе -

  • Уметање напред
  • Уметање позади
  • Брисање испред
  • Брисање позади

Такође можемо да извршимо операције завиривања у деку заједно са горе наведеним операцијама. Операцијом пеек можемо добити предње и задње елементе дека. Дакле, поред горе наведених операција, следеће операције су такође подржане у низу -

нумпи стандардна девијација
  • Узмите предњи предмет из дека
  • Узмите задњи предмет из дека
  • Проверите да ли је дека пуна или не
  • Проверава да ли је декуе празан или не

Сада, хајде да разумемо операцију изведену на декуе користећи пример.

Уметање на предњем крају

У овој операцији, елемент се убацује са предњег краја реда. Пре имплементације операције, прво морамо да проверимо да ли је ред пун или не. Ако ред није пун, онда се елемент може уметнути са предњег краја коришћењем услова у наставку -

  • Ако је ред празан, и задњи и предњи се иницијализују са 0. Сада ће оба показивати на први елемент.
  • У супротном, проверите положај предњег дела ако је предњи део мањи од 1 (предњи<1), then reinitialize it by фронт = н - 1 , тј. последњи индекс низа.
Декуе (или двострани ред)

Уметање на задњем крају

У овој операцији, елемент се убацује са задњег краја реда. Пре имплементације операције, прво морамо поново да проверимо да ли је ред пун или не. Ако ред није пун, онда се елемент може убацити са задње стране користећи следеће услове -

образац дизајна градитеља
  • Ако је ред празан, и задњи и предњи се иницијализују са 0. Сада ће оба показивати на први елемент.
  • У супротном, увећајте задњи део за 1. Ако је задњи индекс на последњем индексу (или величина - 1), онда уместо да га повећавамо за 1, морамо га учинити једнаким 0.
Декуе (или двострани ред)

Брисање на предњем крају

У овој операцији, елемент се брише са предњег краја реда. Пре имплементације операције, прво морамо да проверимо да ли је ред празан или не.

Ако је ред празан, тј. фронт = -1, то је услов нижег протока и не можемо извршити брисање. Ако ред није пун, онда се елемент може уметнути са предњег краја коришћењем услова у наставку -

Ако декуе има само један елемент, поставите реар = -1 и фронт = -1.

Иначе, ако је предњи део на крају (то значи предњи део = величина - 1), поставите предњи део = 0.

супв

Иначе повећајте предњу страну за 1, (тј. фронт = фронт + 1).

Декуе (или двострани ред)

Брисање на задњем крају

У овој операцији, елемент се брише са задњег краја реда. Пре имплементације операције, прво морамо да проверимо да ли је ред празан или не.

Ако је ред празан, тј. фронт = -1, то је услов нижег протока и не можемо извршити брисање.

Ако декуе има само један елемент, поставите реар = -1 и фронт = -1.

Ако је задњи = 0 (позади је напред), онда поставите задњи = н - 1.

У супротном, смањите задњи део за 1 (или реар = реар -1).

Декуе (или двострани ред)

Чек је празан

Ова операција се изводи да би се проверило да ли је декуе празан или не. Ако је фронт = -1, то значи да је декуе празан.

Проверите потпуно

Ова операција се изводи да би се проверило да ли је декуе пун или не. Ако је фронт = реар + 1, или фронт = 0 и реар = н - 1, то значи да је декуе пун.

Временска сложеност свих горе наведених операција низа је О(1), тј. константна.

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

  • Декуе се може користити и као стог и као ред, јер подржава обе операције.
  • Декуе се може користити као провера палиндрома значи да ако читамо стринг са оба краја, стринг би био исти.

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

Сада, да видимо имплементацију декуе у програмском језику Ц.

дискретна математичка негација 
 #include #define size 5 int deque[size]; int f = -1, r = -1; // insert_front function will insert the value from the front void insert_front(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { f=r=0; deque[f]=x; } else if(f==0) { f=size-1; deque[f]=x; } else { f=f-1; deque[f]=x; } } // insert_rear function will insert the value from the rear void insert_rear(int x) { if((f==0 &amp;&amp; r==size-1) || (f==r+1)) { printf(&apos;Overflow&apos;); } else if((f==-1) &amp;&amp; (r==-1)) { r=0; deque[r]=x; } else if(r==size-1) { r=0; deque[r]=x; } else { r++; deque[r]=x; } } // display function prints all the value of deque. void display() { int i=f; printf(&apos;
Elements in a deque are: &apos;); while(i!=r) { printf(&apos;%d &apos;,deque[i]); i=(i+1)%size; } printf(&apos;%d&apos;,deque[r]); } // getfront function retrieves the first value of the deque. void getfront() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at front is: %d&apos;, deque[f]); } } // getrear function retrieves the last value of the deque. void getrear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else { printf(&apos;
The value of the element at rear is %d&apos;, deque[r]); } } // delete_front() function deletes the element from the front void delete_front() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=-1; r=-1; } else if(f==(size-1)) { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=0; } else { printf(&apos;
The deleted element is %d&apos;, deque[f]); f=f+1; } } // delete_rear() function deletes the element from the rear void delete_rear() { if((f==-1) &amp;&amp; (r==-1)) { printf(&apos;Deque is empty&apos;); } else if(f==r) { printf(&apos;
The deleted element is %d&apos;, deque[r]); f=-1; r=-1; } else if(r==0) { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=size-1; } else { printf(&apos;
The deleted element is %d&apos;, deque[r]); r=r-1; } } int main() { insert_front(20); insert_front(10); insert_rear(30); insert_rear(50); insert_rear(80); display(); // Calling the display function to retrieve the values of deque getfront(); // Retrieve the value at front-end getrear(); // Retrieve the value at rear-end delete_front(); delete_rear(); display(); // calling display function to retrieve values after deletion return 0; }

Излаз:

Декуе (или двострани ред)

Дакле, то је све о чланку. Надам се да ће вам чланак бити користан и информативан.