Опашката може да бъде описана като непримитивна линейна структура на данни следва реда FIFO, в който елементите от данни се вмъкват от единия край (задния край) и се изтриват от другия край (предния край). Другите вариации на опашката са кръговата опашка, двойно завършваща опашка и приоритетна опашка.
Сравнителна таблица
| Основа за сравнение | Линейна опашка | Кръгла опашка |
|---|---|---|
| Основен | Организира елементите от данни и инструкциите в последователна последователност една след друга. | Подрежда данните в кръговия модел, където последният елемент е свързан с първия елемент. |
| Ред на изпълнение на задачата | Задачите се изпълняват по реда, по който са били поставени преди (FIFO). | Редът за изпълнение на дадена задача може да се промени. |
| Вмъкване и изтриване | Новият елемент се добавя от задния край и се сваля отпред. | Вмъкването и изтриването може да се направи на всяка позиция. |
| производителност | Неефикасен | Работи по-добре от линейната опашка. |
Дефиниция на линейна опашка
Линейната опашка е рационално първи в първия изреден списък. Тя е така наречена линейна, защото прилича на права линия, където елементите са разположени една след друга. Той съдържа хомогенна колекция от елементи, в които се добавят нови елементи в единия край и се изтриват от друг край. Концепцията на опашката може да бъде разбрана чрез примера на опашката от аудиторията, която чака пред билето за билети, за да получи билет за театър. В тази опашка лицето се присъединява към задния край на опашката, за да вземе билета и билетът се издава в предния край на опашката.
В опашката се изпълняват няколко операции
- Първо, опашката се инициализира до нула (т.е. празна).
- Определете дали опашката е празна или не.
- Определете дали опашката е пълна или не.
- Вмъкване на новия елемент от задния край (Enqueue).
- Изтриване на елемента от предния край (Dequeue).
Опашката може да бъде изпълнена по два начина
- Статично (с използване на масиви)
- Динамично (с помощта на указатели)
Ограничението на линейната опашка е, че създава сценарий, в който не може да се добавя нов елемент в опашката, дори ако опашката съдържа празни пространства. Тази ситуация е илюстрирана на фигурата, дадена по-долу. Тук задната част сочи към последния индекс, докато всички полета са празни, не може да се добави нов елемент.
Дефиниция на кръгова опашка
Кръглата опашка е вариант на линейната опашка, която ефективно преодолява ограничаването на линейната опашка. В кръгова опашка новият елемент се добавя в първата позиция на опашката, ако последната е заета и пространството е налично. Когато става въпрос за линейна опашка, вмъкването може да се извърши само от задния край и изтриването от предния край. В пълна опашка след извършване на поредица от последователни изтривания в опашката възниква определена ситуация, в която не може да бъде добавен нов елемент, дори ако наличното пространство, тъй като условието за подпълване (Rear = max - 1) все още съществува.
Кръглата опашка свързва двата края чрез показалеца, където първият елемент идва след последния елемент. Той също така следи отпред и отзад, като прилага някаква допълнителна логика, така че да може да проследи елементите, които трябва да бъдат вмъкнати и изтрити. С това, кръговата опашка не генерира условие за преливане, докато опашката не е пълна в действителната.
Някои условия, следвани от кръговата опашка:
- Предната част трябва да сочи към първия елемент.
- Опашката ще бъде празна, ако Front = Rear.
- Когато се добави нов елемент, опашката се увеличава с стойност one (Rear = Rear + 1).
- Когато елемент се изтрива от опашката, фронтът се увеличава с един (Front = Front + 1).
Ключови разлики между линейната опашка и кръговата опашка
- Линейната опашка е подреден списък, в който елементите от данни са организирани в последователен ред. Обратно, кръговата опашка съхранява данните по кръгова форма.
- Линейната опашка следва реда FIFO за изпълнение на задачата (елементът, добавен в първата позиция, ще бъде изтрит в първата позиция). Обратно, в кръговата опашка редът на операциите, изпълнявани върху даден елемент, може да се промени.
- Вмъкването и изтриването на елементите се фиксира в линейна опашка, т.е. добавяне от задния край и изтриване от предния край. От друга страна, кръговата опашка е в състояние да вмъкне и изтрие елемента от всяка точка, докато не е незает.
- Линейната опашка губи място в паметта, докато кръговата опашка прави ефективното използване на пространството.
Изпълнение на линейната опашка
Даденият по-долу алгоритъм илюстрира добавянето на елементи в опашката:
Опашката се нуждае от три променливи данни, включващи един масив за съхраняване на опашката и други за съхраняване на предната и задната начална позиция, която е -1.
insert (item, queue, n, rear) {if (отзад == n) и след това отпечатайте "queue overflow"; друго (отзад = зад + 1; опашка [отзад] = елемент; }} Даденият по-долу алгоритъм илюстрира изтриването на елементи в опашката:
delete_circular (елемент, опашка, заден, преден) {if (отзад == отпред) и след това отпечатайте "queue underflow"; иначе {front = front + 1; item = queue [отпред]; }} Изпълнение на кръговата опашка
Алгоритъм за тълкуване на добавянето на елемента в кръговата опашка:
insert_circular (позиция, опашка, задна, предна) {задна = (задна + 1) mod n; ако (отпред == отзад) след това печат "опашката е пълна"; else {опашка [отзад] = елемент; }} Алгоритъмът обяснява изтриването на елемента в кръговата опашка:
delete_circular (елемент, опашка, заден, преден) {if (отпред == отзад) след това отпечатайте ("опашката е празна"); иначе {front = front + 1; item = queue [отпред]; }} заключение
Линейната опашка е неефективна в някои случаи, когато се изисква елементите да преминат към свободните пространства, за да се извърши операция по вмъкване. Това е причината да губи мястото за съхранение, докато кръговата опашка прави правилното използване на пространството за съхранение, тъй като елементите се добавят на всяка позиция, ако съществува празно пространство.
