Опашка

Опашката е линейна структура от данни, която работи на принципа FIFO (first in first out). Опашката отговаря точно на представата за реална опашка. Операции: * Enqueue (или push) - добавя елемент в края на опашката * Dequeue (или pop) - премахва първия добавен елемент в опашката * Front - връща първия елемент в опашката

Опционални операции към интерфейса: * empty() - Връща дали опашката е празна или не * size() - Връща размера на опашката

В STL имаме готова реализация на опашка. Тя се намира в библиотеката \ и се създава чрез std::queue\. Пример:

#include<iostream>
#include<queue>

int main() {
    std::queue<int> q;

    q.push(1);
    q.push(2);
    q.push(3);
    q.push(4);

    std::cout << q.front();             // Извежда 1
    q.pop()                             // Премахва 1 от опашката
    std::cout << q.front();             // Извежда 2
    q.pop();                            // Премахва 2 от опашката
    q.pop();                            // Премахва 3 от опашката
}

Приложения

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

Начини за реализация

Свързани компоненти

Представяме елемента на опашката по следния начин:

template<class T>
struct QueueNode {
    T data;
    QueueNode<T>* next;
}

В класа представящ опашка пазим два указателя, head и tail:

template<class T>
class LinkedQueue {
    QueueNode<T>* head;                 // Представлява първия елемент, който е добавен.
    QueueNode<T>* tail;                 // Представлява последния елемент, който е добавен.
}

При такова представяне как биха изглеждали алгоритмите за добавяне и премахване?

Чрез масив

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

При такова представяне как биха изглеждали алгоритмите за добавяне и премахване? Дали след като запълним последната клетка на масива повече няма да можем да добавим елемент в опашката?

Декове

Декът или deque (от double ended queue) е линейна структура от данни, за която можем да си мислим като опашка, позволяваща добавяне и премахване на елементи и от двете страни.

Операции: * push_front(x) - Добавя x в началото * push_back(x) - Добавя х в края * pop_back() - Премахва последния елемент * pop_front() - Премахва първия елемент

A deque ("double ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.

Стандартната библиотека ни предлага реализация на дек. Тази реализация обаче трябва да се използва внимателно. Примерно, std::deque ни позволява достъп на произволен елемент в колекцията. Това, дори да изглежда като функционалност, която не бихме отказали, често може да доведе до различен тип грешки.

Пример:

#include<deque>

int main() {
    std::deque<int> dq;

    dq.push_front(1);
    dq.push_back(2);

    dq[0] = 10; 
    // Позволява промяна, но доста често такава промяна е безсмислена.
    // Наложи ли ви се да правите такава промяна
    // вероятно използвате грешната структура от данни.
    dq[3] = 1;
    // Какво става когато такъв елемент няма?
    // Отговорът е зависи - недефинирано поведение (undefined behaviour).
}

Неща, които използвам в решението на задачите

Статични масиви и std::array

Всички знаем, че статичният масив е бърза и удобна структура от данни. STL ни предлага готова реализация на статичен масив. Тя се намира в библиотеката \. Пример:

#include<array>

int main() {
    std::array<int, 10> arr;
    arr[0] = 42;
}

В случая arr се държи като нормален статичен масив, но идва с допълнителни помощни функции и поддържа логика за итератори.

Нетипови параметри

Нетиповите параметри често се използват за определяне на някакви максимуми, минимуми или константи свързани с класа. Примерно, нека имаме следния код:

const size_t MAX_SIZE = 100;

template<class T>
class staticArray {
    T data[MAX_SIZE];
}

Това върши работа до момента в който не ни потрябват два различни варианта на staticArray - един с максимум елемента 100 а втория с максимум 50. Този проблем се решава чрез нетипови параметри по следния начин:

template<class T, size_t maxSize>
class staticArray {
    T data[maxSize];
}

Сега много лесно мога да си направя два статични масива с различна горна граница:

int main() {
    staticArray<int, 50> fst;
    staticArray<int, 100> snd;
}

Тук компилаторът няма да ни се скара, понеже maxSize задължително трябва да е константа. Едно хубаво свойство на нетиповите параметри е, че staticArray<T, 50> и staticArray<T, 100> са два различни типа.

Задачи

Задача първа

Да се напише функция, която генерира всички двоични числа от 1 до n, използвайки опашка.

Пример:

n = 10 ➡ 1 10 11 100 101 110 111 1000 1001 1010

Задача втора

Конче стои върху шахматна дъска NxN. За начална и крайна позиция да се изведе с колко най - малко хода можем да стигнем от началната до крайната.

Пример:

{(0, 0), (2, 1)} -> 1

{(0, 0), (7, 7)} -> 6

Задача трета - Sliding window maximum

Даден е масив от цели числа. Представяме си, че имаме прозорец с дължина k който се движи отляво надясно. Единственото което можем да видим са числата в прозореца. Да се изведе максимумът на всеки такъв прозорец.

Пример:

Вход: [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output: [3, 3, 5, 5, 6, 7]

Обяснение:

[1 3 -1] -3 5 3 6 7 => 3

1 [3 -1 -3] 5 3 6 7 => 3

1 3 [-1 -3 5] 3 6 7 => 5

1 3 -1 [-3 5 3] 6 7 => 5

1 3 -1 -3 [5 3 6] 7 => 6

1 3 -1 -3 5 [3 6 7] => 7

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

Алтернативни решения на задачи 1 и 2 както и още задачи за упражнение можете да намерите на: https://github.com/ivanahristova/data-structures-fmi/tree/main/sem04