Опашка (абстрактен тип данни): Разлика между версии

Статичната опашка се реализира с помощта на [[Масив (програмиране)|масив]]. В даден момент началото и краят на опашката сочат към определени индекси от масива. Когато се добавя нов елемент той се поставя на индекса след края на опашката и краят вече сочи към новия елемент. Когато се премахва началото на опашката, елементът на началния индекс се изтрива и началото започва да сочи към следващия индекс. По този начин с добавяне и извличане на елементи от опашката тя се движи към края на масива. В даден момент краят на опашката достига до последния индекс на масива и се оказва, че размерът на масива не е достатъчен въпреки, че опашката не запълва всичките му елементи. За да се реши този проблем при следващото добавяне на елемент в края на опашката, той се поставя на началния индекс на масива. По този начин се свързват началото и края на масива, и опашката може да обикаля безкрайно в него. Ако дължината на опашката (броя на елементите в нея) стане равна на предварително заделения брой на елементи в масива няма да могат да бъдат добавяни нови елементи. Това налага копиране на опашката в нов масив с по-голям размер.

== Динамична реализация ==

При динамичната реализация на опашката елементите не се намират в последователни адреси на паметта, както е при реализацията с масиви. При динамичните структури всеки елемент от опашката съдържа две части - обект и указател към предишния елемент (предишно добавен в опашката). По този начин се образува свързан списък. Известен е адресът на първия елемент в опашката, а адресите на всички останали елементи не са достъпни директно. Достъпът до тях се осъществява като се премине през указателите на всички предшестващи елементи. Последния елемент в опашката има указател, който не сочи към друг елемент, докато не се добави нов елемент накрая. Тогава указателят на елементът, който досега е бил последен започва да сочи към новия елемент. Указателят на новия елемент не сочи наникъде, докато не бъде добавен нов елемент и т.н. В началото на опашката е елементът, който вече може да бъде извлечен. Към този елемент няма насочен указател.

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