Уикипедия

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

Опашката (на английски: 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'

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

Взето от „https://bg.wikipedia.org/w/index.php?title=Опашка_(абстрактен_тип_данни)&oldid=12039808“.