Дефиниране на структурата на данните на опашката, нейните практически приложения, как да създадете опашка в JavaScript и времевата сложност на опашка.
Структурата на данните на опашката е една от най-често използваните структури в компютърните науки. Той е прост, ефективен и лесен за разбиране. В тази статия ще обсъдим какво е опашка, как работи и някои от приложенията, за които може да се използва. Ще предоставим и примери как да създадете опашка в JavaScript.
Какво е опашка?
Опашката е структура от данни, която позволява съхраняването на данни по начин първи влязъл, първи излязъл (FIFO). Тоест, първият елемент, който се добавя към опашката, ще бъде първият елемент, който се премахва. Това е в контраст със стека, който е структура от данни последен влязъл, първи излязъл (LIFO).
Защо опашките са полезни
Опашките често се използват в компютърните системи за съхраняване на данни, които трябва да бъдат обработени в определен ред. Например, когато нова задача влезе в системата, тя обикновено се добавя в края на опашка. След това задачите се обработват една по една в реда, в който са получени. Това гарантира, че всички задачи се обработват по справедлив и ефективен начин.
Практически приложения на опашките
Има много приложения на опашки. Някои често срещани приложения за демонстриране на тяхната гъвкавост и важност включват:
- Последователност на клавиатурата: Когато пишете на клавиатура, знаците се съхраняват в опашка, докато могат да бъдат обработени от компютъра.
- Принтери: Когато изпратите задание за печат на принтер, то обикновено се добавя в края на опашката. След това заданията за печат се обработват в реда, в който са получени.
- Планиране на задачи: Когато нови задачи постъпят в системата, те се добавят към опашка. След това задачите се обработват в реда, в който са получени. Това гарантира, че всички задачи се обработват по справедлив и ефективен начин.
Създаване на опашка и добавяне към опашка
В JavaScript можем да създадем опашка с помощта на масив. Следният пример създава опашка с три елемента:
Добавянето на елементи към опашката обикновено се извършва с помощта на push() method. Методът push() добавя елемент в края на масив. В горния пример добавихме три елемента към нашата опашка.
Премахване от опашка
В JavaScript можем да премахваме елементи от опашка с помощта на метода shift(). Методът shift() премахва първия елемент от масив. В примера по-долу ние премахваме първия елемент от нашата опашка и го съхраняваме в променлива:
В примера по-горе опашката е създадена чрез натискане на „първи“, „втори“ и „трети“ съответно в този ред. Следвайки принципа първи влязъл, първи излязъл на опашката, „първият“ е първият елемент, който трябва да бъде премахнат от опашката. Постигнахме това, като използвахме метода shift(), премахвайки „първо“ от началото на опашката.
Времева сложност
Обикновено едно от предимствата на използването на опашка е, че времевата сложност за добавяне и премахване на елементи е постоянна. Тоест, независимо от броя на елементите в опашката, ще отнеме същото време за добавяне или премахване на елемент, което обикновено е O(1).
В JavaScript обаче няма вградена структура от данни за опашка, която трябва да копираме функционалността на опашка с масив. Докато методът push(), който използвахме, за да добавим елемент към опашката, има времева сложност O(1), методът shift(), който използвахме, за да премахнем елемент от опашката, има времева сложност O(n). Това е така, защото когато изместим елемент от началото на масива, всички останали елементи в масива трябва да бъдат изместени над една позиция.
Заключение
В тази статия обсъдихме структурата на данните на опашката и някои от нейните практически приложения. Също така показахме как да създадем опашка в JavaScript и обсъдихме времевата сложност на опашка в JavaScript. Опашките са прости, ефективни и лесни за разбиране, което ги прави чудесен избор за много приложения.
Надявам се тази статия да изясни всяко объркване. Успех с вашите интервюта за програмиране!
Повече съдържание в PlainEnglish.io. Регистрирайте се за нашия безплатен седмичен бюлетин. Следвайте ни в Twitter, LinkedIn, YouTube и Discord . Интересувате ли се от Growth Hacking? Вижте Circuit.
