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

от Уикипедия, свободната енциклопедия

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

Структурата опашка и поведението на нейните елементи произхождат от ежедневната човешка дейност. Например опашка от хора, чакащи на каса за билети. Опашката има начало и край. Новодошлите хора застават последни на опашката и изчакват докато постепенно се придвижат към началото. Когато стигнат до самото начало на опашката си купуват билет и напускат опашката. Други примери за опашка са документи, чакащи да бъдат отпечатани или ескалатор превозващ хора. По този начин опашката изпълнява функцията на буфер.

Статична реализация[редактиране | редактиране на кода]

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

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

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

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

Динамична реализация[редактиране | редактиране на кода]

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

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

Допустими операции с опашки[редактиране | редактиране на кода]

  • Създаване на празна опашка – опашка която не съдържа елементи.
  • Проверка дали опашката е празна
  • Добавяне на елемент – само след края на опашката.
  • Отстраняване на елемент – само от началото (ако опашката не е празна).
  • Достъп до елемент – възможен е достъп само до началото на опашката (ако не е празна).

Примери за използване на опашка[редактиране | редактиране на кода]

Пример за употреба на опашка в C#

using System;
using System.Collections.Generic;

class QueueExample
{
    static void Main()
    {
        Queue<int> numbersQueue = new Queue<int>();      // инициализация на опашка

        // Пример1 – Добавяне и извличане на елементи от опашка
        for (int i = 0; i < 10; i++)
        {
            numbersQueue.Enqueue(i);       // void метода Enqueue, приема обект от типа на опашката (в случая int) като параметър
        }

        while (numbersQueue.Count > 0)
        {
            Console.WriteLine(numbersQueue.Dequeue());   // метода Dequeue връща следващото число
        }

        // Пример 2
        for (int i = 0; i < 10; i++)
        {
            numbersQueue.Enqueue(i);
        }

        while (numbersQueue.Peek() != 5)      // Този цикъл извлича елементи от опашката докато следващия елемент е различен от 5
        {
            Console.WriteLine(numbersQueue.Dequeue());
        }

        // Пример 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() {
            // Пример 1
            var queue = new Array();
            for (var i = 0; i < 5; i++) {         // добавяне на елементи в опашката
                queue.push(i);
            }

            while (queue.length > 0) {           // извличане на елементи от опашката
                alert(queue.shift());
            }

            // Пример 2
            for (var i = 0; i < 10; i++) {
                queue.push("string" + i);
            }

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

Пример за употреба на опашка в C++

    #include <stdio.h>
    #include <stdlib.h>

    #define M 100

    typedef float ElementType;

    struct Queue
    {
        int r, f;
        ElementType QueueArray[M];
    };

    void pushq(struct Queue *q, ElementType x)
    {
        if((q->r + 1) % M == q->f)
        {
            printf ("Препълване! ");
            exit(1);
        }
        q->r = (q->r + 1) % M;
        q->QueueArray[q->r] = x;
    }
    ElementType popq(struct Queue *q)
    {
        if(q->r == q->f)
        {
            printf("Празна опашка! ");
            exit(1);
        }
        q->f = (q->f + 1) % M;
        return q->QueueArray[q->f];
    }

    void main()
    {
        struct Queue mem = {0, 0}; //създаване на празна опашка
        ElementType y = 3.14f;

        int i;
        for(i = 1; i <= 99; i++)
            pushq(&mem, y+=1.1f);

        for(i = 1; i <= 99; i++)
            printf("%.2f ", popq(&mem));
    }

Пример за употреба на опашка в PHP

<?php
class MoviesList extends SplQueue
{
}

$movies = new MoviesList(); //Създаване на опашката

$movies ->enqueue('The Godfather'); //Добавяне на елементи
$movies ->enqueue('The Shawshank Redemption');
$movies ->enqueue('The Dark Knight');

echo $movies ->dequeue() . "n"; // Изважда 'The Godfather'
echo $movies ->dequeue() . "n"; // Изважда 'The Shawshank Redemption'
echo $movies ->bottom() . "n"; // Изважда 'The Dark Knight'

Източници[редактиране | редактиране на кода]