Статична опашка (реализация с масив)

Статична опашка (реализация с масив)

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

Свързана опашка (динамична реализация)

Динамичната реализация на опашката много прилича на тази на свързания списък. Елементите отново съдържат две части – обекта и указател към предишния елемент:

22. Хеш таблици.Идея, функции, избор на оптимална функция

Реализацията с хеш-таблица има важното предимство, че времето за достъп до стойност от речника, при правилно използване, теоретично не зависи от броя на елементите в него.
За сравнение да вземем списък с елементи, които са подредени в случаен ред. Искаме да проверим дали даден елемент се намира в него. В най-лошия случай, трябва да проверим всеки един елемент от него, за да дадем категоричен отговор на въпроса "съдържа ли списъкът елемента или не". Очевидно е, че броят на тези сравнения зависи (линейно) от броят на елементите в списъка.