Опашка (абстрактен тип данни)

Файл:QUEUE-FIFO.jpg

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

Опашка в програмирането е вид абстрактна структура от данни и е представител на абстрактните типове данни (АТД). Опашките спадат към линейните (списъчни) структури от данни, заедно със списъците и стековете. Опашката представлява крайно, линейно множество от елементи, при което елементи се добавят само най-отзад и се извличат само най-отпред. Абстрактната структура опашка изпълнява условието "първият влязъл първи излиза" (FIFO: First-In-First-Out). Това означава, че след като е добавен един елемент в края на опашката, той ще може да бъде извлечен (премахнат), чак когато бъдат премахнати всички елементи преди него и то в реда, в който са добавени. Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат принтирани или ескалатор превозващ хора.

Статична реализация

Циклично движение на опашка в масив.

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

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

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

Примери за използване на опашка

Пример за употреба на опашка в C# using System; using System.Collections.Generic;

class QueueExample {

   static void Main()
   {
       Queue<int> numbersQueue = new Queue<int>();

       // Example 1
       for (int i = 0; i < 10; i++)
       {
           numbersQueue.Enqueue(i);
       }

       while (numbersQueue.Count > 0)
       {
           Console.WriteLine(numbersQueue.Dequeue());
       }

       // Example 2
       for (int i = 0; i < 10; i++)
       {
           numbersQueue.Enqueue(i);
       }

       while (numbersQueue.Peek() != 5)
       {
           Console.WriteLine(numbersQueue.Dequeue());
       }

       // Example 3
       Queue<string> stringQueue = new Queue<string>();
       for (int i = 0; i < 10; i++)
       {
           stringQueue.Enqueue("string" + i.ToString());
       }
       while (stringQueue.Count > 0)
       {
           Console.WriteLine("Press any key to see next element");
           Console.ReadKey();
           Console.WriteLine("Next element: " + stringQueue.Dequeue());
       }  
   }

}

Пример за употреба на опашка в JavaScript <body>

   <button onclick="startScript()">Test Script</button>
   <script type="text/javascript">
       function startScript() {
           // Example 1
           var queue = new Array();
           for (var i = 0; i < 5; i++) {
               queue.push(i);
           }

           while (queue.length > 0) {
               alert(queue.shift());
           }

           // Example 2
           for (var i = 0; i < 10; i++) {
               queue.push("string" + i);
           }

           while (queue.length > 0) {
               alert(queue.shift());
           }
       }
   </script>

</body>