logo

TechCodeview

Deque (или опашка с двоен край)

В тази статия ще обсъдим двустранната опашка или deque. Първо трябва да видим кратко описание на опашката.

Какво е опашка?

Опашката е структура от данни, в която всичко, което дойде първо, ще излезе първо и следва политиката FIFO (First-In-First-Out). Вмъкването в опашката се извършва от единия край, известен като заден край или опашка, като има предвид, че изтриването се извършва от друг край, известен като преден край или глава на опашката.

bash променлива

Примерът за опашка от реалния свят е опашката за билети пред кино зала, където човекът, който влезе първи на опашката, получава билета пръв, а човекът, който влиза последен на опашката, получава билета най-накрая.

Какво е Deque (или опашка с двоен край)

Deque означава Double Ended Queue. Deque е линейна структура от данни, където операциите за вмъкване и изтриване се извършват от двата края. Можем да кажем, че deque е обобщена версия на опашката.

Въпреки че вмъкването и изтриването в deque може да се извърши от двата края, то не следва правилото FIFO. Представянето на deque е дадено, както следва -

Deque (или опашка с двоен край)

Видове deque

Има два вида deque -

  • Опашка с ограничен вход
  • Опашка с ограничен изход

Опашка с ограничен вход

В опашка с ограничен вход операцията по вмъкване може да се извърши само от единия край, докато изтриването може да се извърши от двата края.

Deque (или опашка с двоен край)

Опашка с ограничен изход

В опашката с ограничен изход операцията по изтриване може да се извърши само в единия край, докато вмъкването може да се извърши от двата края.

Deque (или опашка с двоен край)

Операции, извършвани върху deque

Има следните операции, които могат да бъдат приложени към deque -

  • Вмъкване отпред
  • Вмъкване отзад
  • Изтриване отпред
  • Изтриване отзад

Можем също така да извършваме операции за надникване в deque заедно с операциите, изброени по-горе. Чрез операцията peek можем да получим предните и задните елементи на deque. Така че, в допълнение към горните операции, следните операции също се поддържат в deque -

knn алгоритъм
  • Вземете предния предмет от дека
  • Вземете задния елемент от дека
  • Проверете дали deque е пълна или не
  • Проверява дали deque е празна или не

Сега нека разберем операцията, извършена върху deque, използвайки пример.

Вмъкване в предния край

При тази операция елементът се вмъква от предния край на опашката. Преди да изпълним операцията, първо трябва да проверим дали опашката е пълна или не. Ако опашката не е пълна, тогава елементът може да бъде вмъкнат от предния край, като се използват условията по-долу -

  • Ако опашката е празна, и задната, и предната част се инициализират с 0. Сега и двете ще сочат към първия елемент.
  • В противен случай проверете позицията на предната част, ако предната част е по-малка от 1 (предна<1), then reinitialize it by front = n - 1, т.е. последният индекс на масива.
Deque (или опашка с двоен край)

Вмъкване в задния край

При тази операция елементът се вмъква от задния край на опашката. Преди да изпълним операцията, първо трябва да проверим отново дали опашката е пълна или не. Ако опашката не е пълна, тогава елементът може да бъде вмъкнат от задния край, като се използват условията по-долу -

  • Ако опашката е празна, и задната, и предната част се инициализират с 0. Сега и двете ще сочат към първия елемент.
  • В противен случай увеличете задната част с 1. Ако задната част е с последен индекс (или размер - 1), тогава вместо да я увеличим с 1, трябва да я направим равна на 0.
Deque (или опашка с двоен край)

Изтриване в предния край

При тази операция елементът се изтрива от предния край на опашката. Преди да изпълним операцията, първо трябва да проверим дали опашката е празна или не.

регресионно тестване в софтуерното тестване

Ако опашката е празна, т.е. front = -1, това е условието за препълване и не можем да извършим изтриването. Ако опашката не е пълна, тогава елементът може да бъде вмъкнат от предния край, като се използват условията по-долу -

Ако deque има само един елемент, задайте rear = -1 и front = -1.

В противен случай, ако front е в края (това означава front = size - 1), задайте front = 0.

бутон в центъра css

В противен случай увеличете предната част с 1 (т.е. предната част = предната част + 1).

Deque (или опашка с двоен край)

Изтриване в задния край

При тази операция елементът се изтрива от задния край на опашката. Преди да изпълним операцията, първо трябва да проверим дали опашката е празна или не.

Ако опашката е празна, т.е. front = -1, това е условието за препълване и не можем да извършим изтриването.

Ако deque има само един елемент, задайте rear = -1 и front = -1.

Ако rear = 0 (rear е отпред), тогава задайте rear = n - 1.

В противен случай намалете задната част с 1 (или задната = задната -1).

Deque (или опашка с двоен край)

Чекът е празен

Тази операция се извършва, за да се провери дали втората последователност е празна или не. Ако front = -1, това означава, че deque е празен.

Проверка пълна

Тази операция се извършва, за да се провери дали deque е пълна или не. Ако front = rear + 1, или front = 0 и rear = n - 1, това означава, че deque е пълен.

Времевата сложност на всички горепосочени операции на двойката е O(1), т.е. постоянна.

Приложения на deque

  • Deque може да се използва както като стек, така и като опашка, тъй като поддържа и двете операции.
  • Deque може да се използва като палиндромна проверка, което означава, че ако прочетем низа от двата края, низът ще бъде същият.

Внедряване на deque

Сега нека видим имплементацията на deque в програмния език C.

как да изтеглите играта pigeon на android 
 #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; }

Изход:

Deque (или опашка с двоен край)

И така, това е всичко за статията. Надяваме се, че статията ще бъде полезна и информативна за вас.