Опашка

Queue

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

Автор: Александър Георгиев

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

Какво е опашка?

!	Такъв ред на вкарване и изкарване на елементи на английски се нарича FIFO (first in, first out).

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

Приложение

Тази структура данни се ползва в един от най-разпространените графови алгоритми - Търсене в Ширина - като това я прави и една от най-често ползваните. Тя ни трябва в случаите, когато искаме да обработваме дадени събития или обекти в реда, в който са възникнали. Допълнително ползваме опашка като част от по-сложни алгоритми (например Топологично Сортиране) и структури данни (например Квадратична Опашка).

Поддържани типове

Тъй като елементите се пазят в реда, в който постъпват в структурата (и по-специално, не се пазят сортирани), за тях няма изискване какви да са. Могат да са стандартни типове (например int или double), STL-ски структури (например string), дефинирани от вас структури, а също и други шаблонни класове - включително други опашки!

Имплементация

На теория най-добрият начин да пазим елементите в опашката е чрез свързан списък - тъй като нямаме индексиране освен в първия и последния елемент, то листът би ни дал именно това. На практика, обаче, тъй като заделянето на памет всеки път, когато искаме да добавим нов елемент, създава забележим overhead. Затова често се ползва Динамичен Масив, като така се жертва малко допълнителна памет в полза на скорост. Това е tradeoff, който много често ще срещнете не само в състезателното програмиране, а и като цяло в информатиката.

За да симулираме опашка в магазин ни е нужно да можем да добавяме елементи в края, достъп до елемента в началото и премахване на елемента в началото. Оказва се, че има начин, по който можем да имплементираме и трите в O(1). Супер - така всичко ще е максимално бързо! Можем да имплементираме тези операции ползвайки Свързан Списък, което е една от най-честите имплементации. Друг често-ползван вариант е да се ползва циклична опашка, но тя е малко по-сложна и е по-чест кандидат при имплементацията на Двустранна Опашка (също наричана "Дек"), която ще разгледаме в съответната тема.

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

Данни

Тъй като ще ползваме Свързан Списък за да имплементираме опашката, трябва да дефинираме структурата на всяко "звено" от списъка.

typedef
 int
 DataType;

struct Element {
    DataType data;
    Element *
prev,
 *
next;
    Element(const
 DataType& value) {
        data =
 value;
        prev =
 next =
 nullptr;
    }
};

Структура

Самата опашка се нуждае от съвсем малко неща:

Указатели към началото и края на списъка, в който се пазят данните
Броя елементи в опашката

Второто нещо даже не е задължително, но обикновено се прави за по-бързо питане колко елементи има в нея.

struct Queue {
    int
 size;
    Element *
head,
 *
tail;
    Queue() {
        size =
 0
;
        head =
 tail =
 nullptr;
    }
};

empty()

Проверката дали опашката е празна става тривиално, проверявайки дали броят елементи в нея е нула:

bool
 empty(Queue& q) {
    return
 q.size =
=
 0
;
}

push(value)

Добавянето на нов елемент със стойност value в края на опашката става за О(1) и може да се направи по следния начин:

void
 push(Queue&
 q,
 const
 DataType& value) {
    Element*
 element =
 new
 Element(value);
    if
 (q.size =
=
 0) {
        q.head =
 q.tail =
 element;
    } else {
        q.tail =
 q.tail-
>
next =
 element;
    }
    q.size+
+
;
}

pop()

Премахването на най-предния елемент от опашката също става за O(1) и може да се направи ето така:

void
 pop(Queue& q) {
    assert(q.size >
 0
);
    if
 (q.size =
=
 1) {
        delete
 q.head;
        q.head =
 q.tail =
 nullptr;
    } else {
      Element*
 element =
 q.head;
      q.head =
 q.head-
>
next;
      delete
 element;
    }
    q.size-
-
;
}

front()

Достъпът до първия (най-предния) елемент от опашката отново става за O(1), и става учудващо лесно:

DataType&
 front(Queue& q) {
    assert(q.size >
 0
);
    return
 q.head-
>
data;
}

clear()

Изчистването на опашката е еквивалентно на изчистването на свързания списък:

void
 clear(Queue& q) {
    while
 (q.head !
= nullptr) {
        Element*
 element =
 q.head;
        q.head =
 q.head-
>
next;
        delete
 element;
    }
    q.size =
 0
;
    q.head =
 q.tail =
 nullptr;
}

Цялостна имплементация

Цялостна имплементация и тестове: Queue.h | QueueTester.cpp

Примерна задача

За Коледа Ели получи малко сладко зайче, след което тя стана върл фен на зайчетата. Сега всеки ден тя може да си купи ново зайче, да изяде едно от зайчетата, които има, или да клонира всички тях, получавайки два пъти повече зайчета в края на деня. Ели иска да има N зайчета. За колко най-малко дни тя може да постигне това?

Например:

Ако N е 1, отговорът би бил 0 (нищо за правене, тя вече има 1).
Ако N е 2, отговорът би бил 1 (тя би могла или да купи ново зайче, или да клонира текущото си).
Ако N е 7, отговорът би бил 4 (добавя 1 в първия ден, клонира двете втория, клонира четирите третия и убива едно в четвъртия).
Ако N е 19, отговорът би бил 6: добавя (стават 2), клонира (стават 4), добавя (стават 5), клонира (стават 10), клонира (стават 20), изважда (стават 19).

В по-абстрактен вариант, тази задача е следната. В началото започваме с числото 1. На всяка операция можем да извадим 1 от текущото ни число, да прибавим 1, или да умножим числото ни по 2. Искаме да получим N с минимален брой операции.

Реално можем да пазим опашка с двойки от тип (int, string): кое число може да постигне момичето с дадена последователност и самата последователност (примерно стрингът "+*+**-" би бил последователността, която ползвахме за да постигнем 19). Започваме с опашка с един единствен елемент - двойката (1, ""). На всяка стъпка вадим първия елемент от опашката, пробваме всяка от трите операции върху числото от него и пъхаме трите "продължения" в края на опашката. Можете да забележите, че дължината на стринговете (тоест броя операции) не намалява от началото към края на опашката, а само (потенциално) се увеличава. Така първия елемент, който срещнем с число N ще е постигнат именно с най-малкия възможен брой операции.

Гореописаната задача и алгоритъм е вариант на Търсене в Ширина.

Допълнителни материали

За да предложите корекция, селектирайте думата или текста, който искате да бъде променен,
натиснете Enter и изпратете Вашето предложение.

Страницата е посетена 10871 пъти.