Ръководство за начинаещи за разбиране на опашки и приоритетни опашки

Като програмист ще работите с различни структури от данни в зависимост от обхвата на вашите проекти. Една такава концепция е структура от данни на опашката; опашките са от съществено значение за учениците и се използват в много важни алгоритми. Подобно на опашките, приоритетните опашки споделят подобна концепция, но имат няколко фундаментални разлики.

Прочетете, за да разберете опашките и приоритетните опашки.

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

Опашката е проста структура от данни, която има разнообразни приложения в проекти за кодиране в реалния живот. Структурите на данните са по своята същност абстрактни, но заради простотата си представяме, че структура от данни на опашката има линейна форма с два различни края.

По отношение на времевата сложност, опашката позволява вмъкване (enqueue) и изтриване (dequeue) в O (1) време. Поради своята асимптотична ефективност, опашките са ефективни за големи масиви от данни. Опашките са от типа „първи в първи пръв изход“ (FIFO), което означава, че първо ще бъде достъпен елемент от данни, който е вмъкнат пръв. За разлика от това, стековете имат характер „последен в първи излизащ“ (LIFO) и имат само един отворен край.

Представете си опашка за билети в кино; всеки нов клиент, който пристигне, се присъединява към опашката в единия край. Един по един всеки клиент купува билет и напуска опашката от предния край. Структурата на данните на опашката функционира точно като всяка опашка в реалния свят и данните се вмъкват (enqueue) в единия край и се премахват (dequeue) в другия край. Надяваме се сега да разберете причините защо опашките следват методология на FIFO.

Опашката има много приложения за кодиране в реалния живот. Той е по -често използван в приложения, където данните не се нуждаят от незабавна обработка, а по -скоро в ред FIFO. Планиране на дискове, асинхронен пренос на данни, семафори са някои типични приложения. Задачите за планиране на първи дошъл първи обслужване, като спулинг на печат или буфери за входно устройство също използват опашка.

Какво е приоритетна опашка?

Приоритетна опашка е подобна на опашка, но има допълнителни свойства. Когато елемент от данни е подреден в опашката за приоритет, той получава приоритетен номер. За разлика от изваждането на стандартна опашка, елементи от данни с висок приоритет се изваждат преди елементи с нисък приоритет. Приоритетът замества реда на пристигане в приоритетна опашка, поради което приоритетните опашки нямат последователен характер на FIFO.

Свързани: Алгоритми, които всеки програмист трябва да знае

Програмистите могат да реализират приоритетна опашка по няколко начина. Простата реализация е да се използва масив с елемент от структура/клас данни, като елементът от данни ще съдържа приоритета на всеки елемент от данни и самите данни. Друго изпълнение на примитивна приоритетна опашка е да се използва свързан списък. Приоритетните опашки, изпълнени чрез свързани списъци, са функционални, но не са идеални поради тяхната производителност.

Можете да реализирате по -добра приоритетна опашка с купчина. Ако си спомняте, двоичните купчини дават максималния или минималния елемент за 0 (1) време, а вмъкването отнема само 0 (logN) време. С помощта на купчини приоритетните опашки дават по -добра производителност асимптотично в сравнение с опашките или масивите.

Приоритетната опашка също има разнообразие от основни приложения. Приоритетните опашки са от решаващо значение за графичните алгоритми, като например минималното обхващащо дърво на Prim и алгоритъма на най -краткия път на Dijkstra. Те са идеални и в алгоритмите за планиране на процеса на компютърни процесори (CPU).

Научете структурите на данните

Опашките и приоритетните опашки са важни структури от данни за всички начинаещи. От решаващо значение е учениците да се чувстват удобно да прилагат тези структури от данни и да ги използват в различни проекти.

Други структури от данни, като купчини, купчини и дървета, са еднакво важни както за студенти, така и за професионалисти. Също така е много често интервюиращите да разпитват кандидатите за структурите на данните.

След като прочетете тази статия, сега трябва да имате добра представа как работят опашките и приоритетните опашки. Ако все още изглежда малко неясно, ще се справите с тях, когато натрупате повече опит с тяхното използване.

Купи срещу. Стекове: Какво ги отличава?

Чували сте за купчини и купчини, но кога трябва да използвате една върху друга?

Прочетете Напред

За автора