Концепцията за опашка
FIFO опашка (First - In - First - Out - "първи влязъл - първи излязъл") е такъв последователен списък с променлива дължина, в който включването на елементи се извършва само от едната страна на списъка (тази страна често се нарича край или опашка на опашката), а изключването е от другата (наречена началото или главата на опашката). Опашките за гишета и каси са типичен домакински пример за FIFO опашка.
Основните операции на опашката са същите като на стека - включване, изключване, оразмеряване, изчистване, недеструктивно четене.
Ориз. 13.1. Представяне на опашка с масив
Очевидно с течение на времето крайният указател ще достигне горната граница на областта на паметта, разпределена за опашката, когато елементът бъде включен следващия път. Ако обаче операциите на включване се редуват с операциите на изключване на елементи, тогава има свободно място в началната част на паметта, разпределена за опашката. За да може мястото, заето от изключените елементи, да се използва повторно, опашката се затваря в пръстен: указателите (към началото и към края), след като достигнат края на разпределената област на паметта, преминават към нейното начало. Тази опашка в паметта се наричапръстена опашка.
Разбира се, възможни са и други опции за организация: например, когато крайният указател достигне горната граница на паметта, преместете всички непразни елементи на опашката в началото на областта на паметта, но и тази, и другите опции изискват преместване на елементи на опашката в паметта и са по-малко ефективни от опашката с пръстени.
Първоначално началният и крайният указател сочат към началото на областта на паметта. Равенството на тези два указателя (каквато и да е тяхната стойност) езнак за празна опашка. Ако в процеса на работа с пръстеновидна опашка броят на операциите за включване надвишава броя на операциите за изключване, тогава може да възникне ситуация, при която крайният указател "наваксва" началния указател. Това е ситуация на пълна опашка, но ако в тази ситуация указателите са равни, тази ситуация ще бъде неразличима от ситуацията на празна опашка. За да се направи разлика между тези две ситуации, опашката за пръстен трябва да остави "празнина" от свободни елементи между крайния указател и началния указател. Когато тази "празнина" се намали до един елемент, опашката се счита за пълна и по-нататъшните опити за запис в нея се блокират. Изчистването на опашката се свежда до записване на една и съща (в общия случай не непременно първоначалната) стойност и в двата указателя. Определянето на размера се състои в изчисляване на разликата на указателите, като се вземе предвид кръговият характер на опашката.
Dec е специален вид опашка. Dec (от английски deq - двустранна опашка, т.е. опашка с два края) е такъв последователен списък, в който както включването, така и изключването на елементи могат да се извършват от всеки от двата края на списъка. Специален случай на колода е двойка с ограничен вход и двойка с ограничен изход. Логическата и физическа структура на deque е подобна на логическата и физическа структура на пръстен FIFO опашка. Във връзка с тестето обаче е препоръчително да се говори не за началото и края, а за левия и десния край.
Операции на палуби:
- включване на елемента отдясно;
- включване на елемента отляво;
- изключване на елемента отдясно;
- изключване на елемента отляво;
Физическата структура на deque в статична памет е идентична с тази на опашката за пръстени. Динамичната реализация е очевидно обединение на стек и опашка.
Задачи, изискващи структура на палубата,се срещат в компютрите и програмирането много по-рядко от задачите, реализирани в структура на стек или опашка. По правило цялата организация на палубата се извършва от програмиста без специални инструменти за поддръжка на системата.
Пример за deque може да бъде, например, определен терминал, в който се въвеждат команди, всяка от които отнема известно време за изпълнение. Ако въведете следващата команда, без да изчакате предишната да завърши, тя ще се постави на опашка и ще започне да се изпълнява веднага щом терминалът се освободи. Това е FIFO опашка. Ако въведем допълнителна операция за отмяна на последната въведена команда, тогава получаваме Dec.