Власні структури даних: стек та черга

Hook: від програм до даних — коли контейнер диктує поведінку

Уявіть редактор тексту з функцією Undo (скасування останньої дії). Користувач послідовно виконує 5 операцій:

1. Видаляє слово "hello"
2. Вставляє речення "Goodbye world"
3. Змінює шрифт на жирний
4. Видаляє абзац
5. Вставляє зображення

Тепер він натискає Ctrl+Z (Undo). Яку операцію має скасувати система? Очевидно, останню — вставку зображення (операція №5). Натискає ще раз — скасовується видалення абзацу (№4). Ще раз — зміна шрифту (№3). Це не випадковість — це фундаментальна властивість стеку (stack): останній доданий елемент витягується першим (Last-In, First-Out, LIFO).

Тепер розглянемо чергу друку (print queue) в офісному принтері. Троє співробітників надсилають документи одночасно:

1. Олександр: звіт на 3 сторінки
2. Марія: презентація на 10 сторінок
3. Дмитро: договір на 2 сторінки

У якому порядку принтер обробить завдання? У порядку надходження: спершу звіт Олександра (перший у черзі), потім презентацію Марії, нарешті договір Дмитра. Це фундаментальна властивість черги (queue): перший доданий елемент витягується першим (First-In, First-Out, FIFO).

До цього моменту курсу ми багато працювали з масивами (int[], std::vector) — це універсальні контейнери з довільним доступом: можна читати і писати будь-який елемент за індексом. Але універсальність має ціну: коли ми моделюємо стек операцій Undo за допомогою звичайного масиву, нічого не заважає програмісту випадково звернутися до середини масиву, порушивши логіку LIFO. Коли ми моделюємо чергу друку через масив, немає механізму, що запобігає витяганню елементів не з того кінця.

Власні структури даних (custom data structures) розв'язують цю проблему: ми інкапсулюємо низькорівневий контейнер (масив) всередині класу та надаємо лише ті операції, які відповідають семантиці ADT. Стек надає лише push (додати зверху) та pop (витягнути зверху). Черга надає лише enqueue (додати в кінець) та dequeue (витягнути з початку). Архітектура класу гарантує коректність використання — помилкове звернення до середини стека стає синтаксично неможливим.

У цій лекції ми опануємо проєктування та реалізацію двох найфундаментальніших ADT комп'ютерних наук — стеку та черги — з нуля, застосовуючи всі інструменти ООП, що ми вивчили: інкапсуляцію, конструктори, деструктори, винятки та RAII.

Абстрактні типи даних: від інтерфейсу до реалізації

Що таке абстрактний тип даних?

Абстрактний тип даних (Abstract Data Type, ADT) — це математична модель структури даних, що визначає:

1. Множину значень, які може зберігати структура (наприклад, послідовність цілих чисел).
2. Множину операцій над цими значеннями (наприклад, push, pop, top).
3. Семантику (поведінку) кожної операції — що саме вона робить, які має передумови (preconditions) та постумови (postconditions).

Ключова властивість ADT — незалежність від реалізації. ADT описує що робить структура, а не як вона це робить на рівні пам'яті та процесора. Наприклад, стек можна реалізувати через:

• Динамічний масив (як ми зробимо у цій лекції).
• Зв'язаний список (linked list) — кожен елемент зберігає покажчик на наступний.
• Рекурсивну структуру на основі вкладених об'єктів.

Усі ці реалізації є коректними, якщо вони задовольняють семантику ADT: після push(x) виклик top() має повернути x, після pop() верхівка стека має змінитися на попередній елемент тощо.

Стек як ADT: інтерфейс та семантика

Стек (stack) — це лінійна структура даних, що дотримується дисципліни LIFO (Last-In, First-Out): останній доданий елемент завжди витягується першим. Уявіть стос тарілок: ви можете покласти нову тарілку лише зверху, і взяти тарілку — лише зверху. Доступ до середини чи дна стека неможливий без витягання всіх елементів зверху.

Обов'язкові операції стека:

Черга як ADT: інтерфейс та семантика

Черга (queue) — це лінійна структура даних, що дотримується дисципліни FIFO (First-In, First-Out): перший доданий елемент завжди витягується першим. Уявіть чергу людей у касі: хто прийшов раніше, той обслуговується раніше. Нові люди стають в кінець черги (rear / back), обслуговування відбувається з початку черги (front).

Обов'язкові операції черги:

Основна відмінність від стека: у стеку ми додаємо і витягаємо з одного кінця (верхівки), у черзі — додаємо з одного кінця (rear), а витягаємо з іншого (front). Це фундаментально змінює семантику: стек «забуває старі елементи останніми», черга «обробляє старі елементи першими».

Проєктування класу Stack: архітектура та інваріанти

Вибір внутрішнього контейнера

Для реалізації стека нам потрібен лінійний контейнер, що дозволяє ефективно додавати та видаляти елементи з одного кінця. Найпростіший вибір — динамічний масив (int* data), де ми підтримуємо:

• maxCapacity — поточна ємність масиву (кількість виділених слотів пам'яті).
• topIndex — індекс верхівки стека (індекс останнього доданого елемента).

Інваріант стека (умова, що завжди має бути істинною):

• Якщо стек порожній, topIndex == -1.
• Якщо стек містить n елементів, topIndex == n - 1 (індекс останнього елемента).
• Завжди topIndex < maxCapacity.

@startuml
skinparam style plain
skinparam backgroundColor #FFFFFF

package "Об'єкт Stack (на стеку виконання)" #F1F5F9 {
    rectangle "data: int*" as ptr #DBEAFE
    rectangle "maxCapacity: int = 10" as cap #E2E8F0
    rectangle "topIndex: int = 3" as top #E2E8F0
}

package "Динамічний масив (у купі)" #FEF3C7 {
    rectangle "[0] = 42" as e0 #DCFCE7
    rectangle "[1] = 17" as e1 #DCFCE7
    rectangle "[2] = 99" as e2 #DCFCE7
    rectangle "[3] = 5" as e3 #DCFCE7
    rectangle "[4] = ?" as e4 #F1F5F9
    rectangle "[5] = ?" as e5 #F1F5F9
    rectangle "..." as dots #F1F5F9
    rectangle "[9] = ?" as e9 #F1F5F9
}

ptr -down-> e0 : вказує на початок масиву
top .down.> e3 : індекс верхівки стека

note right of e3 #FEF3C7
  Верхівка стека (top)
  Останній доданий елемент: 5
end note

note right of e4 #F8FAFC
  Вільні слоти
  (не ініціалізовані)
end note

@enduml

Оголошення класу Stack

// Stack.h
#ifndef STACK_H
#define STACK_H

#include <stdexcept>  // std::out_of_range, std::overflow_error

class Stack
{
private:
    int* data;          // Динамічний масив для зберігання елементів
    int maxCapacity;    // Максимальна ємність стека
    int topIndex;       // Індекс верхнього елемента (-1, якщо стек порожній)

public:
    // Конструктор: створює стек заданої ємності
    explicit Stack(int capacity = 10);
    
    // Деструктор: звільняє динамічну пам'ять
    ~Stack();
    
    // Заборона копіювання (правило трьох — статті 59, 66)
    Stack(const Stack&) = delete;
    Stack& operator=(const Stack&) = delete;
    
    // Додати елемент на верхівку стека
    void push(int value);
    
    // Видалити елемент з верхівки стека
    void pop();
    
    // Отримати значення верхнього елемента
    int top() const;
    
    // Перевірити, чи стек порожній
    bool isEmpty() const;
    
    // Перевірити, чи стек повний
    bool isFull() const;
    
    // Отримати поточну кількість елементів
    int size() const;
    
    // Отримати ємність стека
    int capacity() const;
};

#endif

Реалізація конструктора та деструктора

// Stack.cpp
#include "Stack.h"

// Конструктор: виділяє пам'ять та ініціалізує стек порожнім
Stack::Stack(int capacity)
    : data(new int[capacity])  // Виділяємо масив у купі
    , maxCapacity(capacity)
    , topIndex(-1)             // -1 означає «стек порожній»
{
    if (capacity <= 0)
    {
        delete[] data;
        throw std::invalid_argument("Stack capacity must be positive");
    }
}

// Деструктор: звільняє динамічну пам'ять (ідіома RAII)
Stack::~Stack()
{
    delete[] data;
    // data, maxCapacity, topIndex автоматично знищені (це не покажчики)
}

Конструктор отримує бажану ємність стека (за замовчуванням 10 елементів) та виділяє масив у купі. Початкове значення topIndex = -1 сигналізує, що стек порожній — це спеціальне сигнальне значення (sentinel value), яке робить перевірку isEmpty() тривіальною.

Деструктор реалізує ідіому RAII (Resource Acquisition Is Initialization, стаття 54): ресурс (динамічна пам'ять) виділяється в конструкторі та гарантовано звільняється в деструкторі. Це запобігає витокам пам'яті навіть при генерації винятків.

Допоміжні методи: перевірка стану

// Перевірити, чи стек порожній
bool Stack::isEmpty() const
{
    return topIndex == -1;
}

// Перевірити, чи стек повний
bool Stack::isFull() const
{
    return topIndex == maxCapacity - 1;
}

// Отримати поточну кількість елементів
int Stack::size() const
{
    return topIndex + 1;  // Якщо topIndex == 3, у стеку 4 елементи (індекси 0, 1, 2, 3)
}

// Отримати ємність стека
int Stack::capacity() const
{
    return maxCapacity;
}

Ці методи є запитами (queries) — вони не змінюють стан об'єкта, тому позначені як const (стаття 57). Метод size() повертає topIndex + 1, оскільки індекси починаються з 0: якщо верхівка на індексі 3, у стеку 4 елементи (на позиціях 0, 1, 2, 3).

Реалізація операцій стека: push, pop, top

Операція push: додавання елемента

void Stack::push(int value)
{
    // Передумова: стек не повинен бути повним
    if (isFull())
    {
        throw std::overflow_error("Stack overflow: cannot push to full stack");
    }
    
    // Збільшуємо індекс верхівки та додаємо елемент
    ++topIndex;
    data[topIndex] = value;
    
    // Постумова: size() збільшився на 1, top() тепер повертає value
}

Логіка push проста:

1. Перевірка передумови: Якщо стек вже повний (topIndex == maxCapacity - 1), подальше додавання призведе до запису за межі масиву — це переповнення стека (stack overflow). Ми генеруємо виняток std::overflow_error (стаття 86) для сигналізації про порушення контракту.
2. Оновлення верхівки: Збільшуємо topIndex на 1 — тепер він вказує на наступний вільний слот.
3. Запис значення: Зберігаємо value у слот data[topIndex].

Операція pop: видалення елемента

void Stack::pop()
{
    // Передумова: стек не повинен бути порожнім
    if (isEmpty())
    {
        throw std::out_of_range("Stack underflow: cannot pop from empty stack");
    }
    
    // Зменшуємо індекс верхівки — елемент логічно видалено
    --topIndex;
    
    // Примітка: фізично елемент залишається в масиві, але стає недоступним
    // Постумова: size() зменшився на 1
}

Операція pop() не повертає видалений елемент — вона лише видаляє його. Якщо потрібно отримати значення перед видаленням, спершу викликають top(), потім pop(). Це розділення відповідальності є стандартом у дизайні ADT: операція pop виконує лише одну дію — видалення.

Чому ми не очищаємо фізично елемент? Після --topIndex елемент на позиції topIndex + 1 залишається в масиві, але стає логічно недоступним — наступний виклик push перезапише цей слот. Фізичне очищення (data[topIndex + 1] = 0) не дає жодних переваг для типів int, але ускладнює код. Для класів зі складними деструкторами (наприклад, std::string) очищення було б необхідним, але це тема лекцій про шаблони класів (стаття 82).

Операція top: отримання верхнього елемента

int Stack::top() const
{
    // Передумова: стек не повинен бути порожнім
    if (isEmpty())
    {
        throw std::out_of_range("Stack is empty: no top element");
    }
    
    // Повертаємо копію верхнього елемента (не посилання!)
    return data[topIndex];
}

Метод top() надає доступ для читання до верхнього елемента без його видалення. Це const-метод (стаття 57), що гарантує незмінність стану стека. Повертаємо копію значення, а не посилання, щоб запобігти зовнішній модифікації внутрішнього масиву.

Використання стека: практичні приклади

Приклад 1: Балансування дужок

Одне з класичних застосувань стека — перевірка балансування дужок у виразах. Вираз коректний, якщо:

• Кожна відкриваюча дужка (, [, { має відповідну закриваючу.
• Закриваючі дужки з'являються у правильному порядку (не можна закрити ], якщо остання відкрита ().

Приклади:

• "((()))" — коректно
• "([{}])" — коректно
• "(()" — некоректно (не вистачає закриваючої)
• "())" — некоректно (зайва закриваюча)
• "([)]" — некоректно (неправильний порядок)

#include "Stack.h"
#include <string>
#include <iostream>

bool isBalanced(const std::string& expression)
{
    Stack stack(expression.length());  // Максимум length() дужок
    
    for (char ch : expression)
    {
        // Якщо відкриваюча дужка — додаємо в стек
        if (ch == '(' || ch == '[' || ch == '{')
        {
            stack.push(ch);
        }
        // Якщо закриваюча — перевіряємо відповідність з верхівкою
        else if (ch == ')' || ch == ']' || ch == '}')
        {
            if (stack.isEmpty())
            {
                return false;  // Зайва закриваюча дужка
            }
            
            char topChar = stack.top();
            stack.pop();
            
            // Перевіряємо, чи відкриваюча відповідає закриваючій
            if ((ch == ')' && topChar != '(') ||
                (ch == ']' && topChar != '[') ||
                (ch == '}' && topChar != '{'))
            {
                return false;  // Неправильний тип дужки
            }
        }
        // Інші символи (букви, цифри) ігноруємо
    }
    
    // Вираз коректний, якщо стек порожній (всі дужки закриті)
    return stack.isEmpty();
}

int main()
{
    std::cout << std::boolalpha;  // Друкувати true/false замість 1/0
    std::cout << "\"(())\" balanced: " << isBalanced("(())") << '\n';
    std::cout << "\"([{}])\" balanced: " << isBalanced("([{}])") << '\n';
    std::cout << "\"(()\" balanced: " << isBalanced("(()") << '\n';
    std::cout << "\"([)]\" balanced: " << isBalanced("([)]") << '\n';
    
    return 0;
}

Чому стек ідеально підходить для цієї задачі? Коли ми зустрічаємо закриваючу дужку, нам потрібно перевірити відповідність з останньою незакритою відкриваючою дужкою — це саме семантика LIFO стека.

Приклад 2: Обернення рядка

Стек природним чином обертає порядок елементів: що додано першим, витягується останнім. Це властивість корисна для обернення послідовностей.

#include "Stack.h"
#include <string>
#include <iostream>

std::string reverseString(const std::string& str)
{
    Stack stack(str.length());
    
    // Додаємо всі символи в стек
    for (char ch : str)
    {
        stack.push(ch);
    }
    
    // Витягаємо символи у зворотному порядку
    std::string reversed;
    while (!stack.isEmpty())
    {
        reversed += static_cast<char>(stack.top());
        stack.pop();
    }
    
    return reversed;
}

int main()
{
    std::string original = "Hello, Stack!";
    std::string reversed = reverseString(original);
    
    std::cout << "Original: " << original << '\n';
    std::cout << "Reversed: " << reversed << '\n';
    
    return 0;
}

Проєктування класу Queue: кільцевий буфер

Наївна реалізація черги: проблема зсуву

Найпростіший спосіб реалізувати чергу — використати масив з двома індексами:

• frontIndex — індекс першого елемента (який буде витягнуто першим).
• rearIndex — індекс останнього елемента (куди додано останній елемент).

При додаванні елемента (enqueue) збільшуємо rearIndex. При видаленні (dequeue) збільшуємо frontIndex. Проблема: після кількох операцій frontIndex та rearIndex зміщуються до кінця масиву, навіть якщо початок масиву порожній.

@startuml
skinparam style plain
skinparam backgroundColor #FFFFFF

rectangle "Після 3 enqueue:" as label1 #F1F5F9
rectangle "[0]=A" as a1 #DCFCE7
rectangle "[1]=B" as b1 #DCFCE7
rectangle "[2]=C" as c1 #DCFCE7
rectangle "[3]=?" as d1 #F1F5F9
rectangle "[4]=?" as e1 #F1F5F9
note right of a1 : front = 0, rear = 2

rectangle "Після 2 dequeue:" as label2 #F1F5F9
rectangle "[0]=?" as a2 #F1F5F9
rectangle "[1]=?" as b2 #F1F5F9
rectangle "[2]=C" as c2 #DCFCE7
rectangle "[3]=?" as d2 #F1F5F9
rectangle "[4]=?" as e2 #F1F5F9
note right of c2 : front = 2, rear = 2

rectangle "Після 2 enqueue:" as label3 #F1F5F9
rectangle "[0]=?" as a3 #F1F5F9
rectangle "[1]=?" as b3 #F1F5F9
rectangle "[2]=C" as c3 #DCFCE7
rectangle "[3]=D" as d3 #DCFCE7
rectangle "[4]=E" as e3 #DCFCE7
note right of e3 : front = 2, rear = 4

rectangle "❌ Проблема:" as problem #FEF3C7
note bottom of problem
  Слоти [0] і [1] порожні, але rear = 4.
  Наступний enqueue вийде за межі масиву,
  хоча в черзі лише 3 елементи з 5 можливих!
end note

label1 -[hidden]down-> a1
label2 -[hidden]down-> a2
label3 -[hidden]down-> a3
@enduml

Наївне рішення — зсувати всі елементи після кожного dequeue, щоб frontIndex завжди був 0. Але це катастрофічно неефективно: кожне видалення потребує O(n) копіювань.

Кільцевий буфер: елегантне рішення

Кільцевий буфер (circular buffer / ring buffer) розв'язує проблему зсуву: коли індекс досягає кінця масиву, він обертається на початок. Ми розглядаємо масив як кільце, де після останнього слота йде перший.

Ключова ідея: Індекси frontIndex та rearIndex обчислюються за модулем розміру масиву:

rearIndex = (rearIndex + 1) % maxCapacity;
frontIndex = (frontIndex + 1) % maxCapacity;

Якщо maxCapacity = 5, послідовність індексів: 0 → 1 → 2 → 3 → 4 → 0 → 1 → ... (кільце).

@startuml
skinparam style plain
skinparam backgroundColor #FFFFFF

circle "Слот [0]" as s0 #DCFCE7
circle "Слот [1]" as s1 #E2E8F0
circle "Слот [2]" as s2 #E2E8F0
circle "Слот [3]" as s3 #DCFCE7
circle "Слот [4]" as s4 #DCFCE7

s0 -down-> s1
s1 -down-> s2
s2 -down-> s3
s3 -down-> s4
s4 -up-> s0 : обертання (wrap-around)

note right of s4 : rear = 4 (останній елемент)
note left of s1 : front = 1 (перший елемент)

note bottom of s2 #FEF3C7
  Елементи: [1, 3, 4]
  Індекси обертаються по колу.
  Слоти [0] та [2] вільні.
end note

@enduml

Оголошення класу Queue

// Queue.h
#ifndef QUEUE_H
#define QUEUE_H

#include <stdexcept>

class Queue
{
private:
    int* data;          // Динамічний масив (кільцевий буфер)
    int maxCapacity;    // Максимальна ємність черги
    int frontIndex;     // Індекс першого елемента
    int rearIndex;      // Індекс останнього елемента
    int count;          // Поточна кількість елементів

public:
    // Конструктор: створює чергу заданої ємності
    explicit Queue(int capacity = 10);
    
    // Деструктор: звільняє динамічну пам'ять
    ~Queue();
    
    // Заборона копіювання
    Queue(const Queue&) = delete;
    Queue& operator=(const Queue&) = delete;
    
    // Додати елемент в кінець черги
    void enqueue(int value);
    
    // Видалити елемент з початку черги
    void dequeue();
    
    // Отримати значення першого елемента
    int front() const;
    
    // Перевірити, чи черга порожня
    bool isEmpty() const;
    
    // Перевірити, чи черга повна
    bool isFull() const;
    
    // Отримати поточну кількість елементів
    int size() const;
    
    // Отримати ємність черги
    int capacity() const;
};

#endif

Важлива відмінність від стека: У черзі ми зберігаємо окреме поле count (кількість елементів), оскільки індекси frontIndex та rearIndex не дають прямої інформації про кількість елементів у кільцевому буфері. Наприклад, якщо frontIndex == rearIndex, це може означати як порожню чергу, так і повну (всі слоти зайняті, індекси збіглися після обертання).

Реалізація конструктора та допоміжних методів

// Queue.cpp
#include "Queue.h"

Queue::Queue(int capacity)
    : data(new int[capacity])
    , maxCapacity(capacity)
    , frontIndex(0)     // Перший елемент на індексі 0
    , rearIndex(-1)     // -1 означає "черга порожня"
    , count(0)
{
    if (capacity <= 0)
    {
        delete[] data;
        throw std::invalid_argument("Queue capacity must be positive");
    }
}

Queue::~Queue()
{
    delete[] data;
}

bool Queue::isEmpty() const
{
    return count == 0;
}

bool Queue::isFull() const
{
    return count == maxCapacity;
}

int Queue::size() const
{
    return count;
}

int Queue::capacity() const
{
    return maxCapacity;
}

Початкові значення: frontIndex = 0, rearIndex = -1, count = 0 сигналізують про порожню чергу. Після першого enqueue індекс rearIndex стане 0 (через (rearIndex + 1) % maxCapacity), і перший елемент буде на позиції 0.

Реалізація операцій черги: enqueue, dequeue, front

Операція enqueue: додавання елемента

void Queue::enqueue(int value)
{
    // Передумова: черга не повинна бути повною
    if (isFull())
    {
        throw std::overflow_error("Queue overflow: cannot enqueue to full queue");
    }
    
    // Обертаємо rear на наступну позицію (з урахуванням кільця)
    rearIndex = (rearIndex + 1) % maxCapacity;
    
    // Додаємо елемент на нову позицію rear
    data[rearIndex] = value;
    
    // Збільшуємо лічильник розміру
    ++count;
    
    // Постумова: size() збільшився на 1, елемент доданий в кінець
}

Ключовий момент: Оператор % (модуль) забезпечує обертання індекса. Якщо rearIndex == 4 і maxCapacity == 5, то (4 + 1) % 5 == 0 — індекс повертається на початок масиву. Якщо rearIndex == 2, то (2 + 1) % 5 == 3 — звичайне збільшення.

Відео нижче показує повний життєвий цикл enqueue на кільцевому буфері ємністю 6: три додавання, два видалення (звільняють слоти спереду), потім додавання зі wrap-around — (5 + 1) % 6 = 0 переписує слот 0 без жодного зсуву елементів — і нарешті спроба додати в повну чергу, яку контракт зупиняє через throw std::overflow_error.

Операція dequeue: видалення елемента

void Queue::dequeue()
{
    // Передумова: черга не повинна бути порожньою
    if (isEmpty())
    {
        throw std::out_of_range("Queue underflow: cannot dequeue from empty queue");
    }
    
    // Обертаємо front на наступну позицію (видаляємо перший елемент логічно)
    frontIndex = (frontIndex + 1) % maxCapacity;
    
    // Зменшуємо лічильник розміру
    --count;
    
    // Постумова: size() зменшився на 1, наступний елемент став першим
}

Аналогічно enqueue, ми обертаємо frontIndex через модуль. Фізично елемент залишається в масиві, але стає недоступним.

Операція front: отримання першого елемента

int Queue::front() const
{
    // Передумова: черга не повинна бути порожньою
    if (isEmpty())
    {
        throw std::out_of_range("Queue is empty: no front element");
    }
    
    // Повертаємо копію першого елемента
    return data[frontIndex];
}

Використання черги: практичні приклади

Приклад 1: Симуляція друку

Черга ідеально моделює системи обслуговування (queuing systems): принтер, каса в магазині, процесор комп'ютера.

#include "Queue.h"
#include <iostream>
#include <string>

struct PrintJob
{
    std::string documentName;
    int pages;
};

void simulatePrintQueue()
{
    Queue jobIds(5);  // Черга ID завдань (для простоти — int)
    
    std::cout << "=== Симуляція черги друку ===\n\n";
    
    // Додаємо завдання в чергу
    std::cout << "Надсилання завдань на друк:\n";
    try
    {
        jobIds.enqueue(101);  // Завдання №101
        std::cout << "  Додано завдання #101 (звіт, 3 стор.)\n";
        
        jobIds.enqueue(102);  // Завдання №102
        std::cout << "  Додано завдання #102 (презентація, 10 стор.)\n";
        
        jobIds.enqueue(103);  // Завдання №103
        std::cout << "  Додано завдання #103 (договір, 2 стор.)\n";
    }
    catch (const std::exception& e)
    {
        std::cerr << "Помилка: " << e.what() << '\n';
    }
    
    std::cout << "\nОбробка черги друку (FIFO):\n";
    
    // Обробляємо завдання в порядку надходження
    while (!jobIds.isEmpty())
    {
        int currentJob = jobIds.front();
        std::cout << "  Друкується завдання #" << currentJob << "...\n";
        jobIds.dequeue();
    }
    
    std::cout << "\nЧерга порожня. Всі завдання оброблені.\n";
}

int main()
{
    simulatePrintQueue();
    return 0;
}

Чому черга ідеально підходить? Завдання обробляються у порядку надходження — справедливе обслуговування (fair scheduling). Перший, хто надіслав документ, отримує результат першим.

Приклад 2: Обхід дерева в ширину (BFS)

Черга є фундаментальною структурою для алгоритму обходу графа в ширину (Breadth-First Search, BFS). Хоча ми ще не вивчали дерева та графи детально, концептуально BFS працює так:

1. Починаємо з кореневого вузла, додаємо його в чергу.
2. Витягаємо вузол з початку черги, обробляємо його.
3. Додаємо всіх його дітей (сусідів) в кінець черги.
4. Повторюємо, поки черга не стане порожньою.

#include "Queue.h"
#include <iostream>

// Спрощена структура бінарного дерева (для демонстрації концепції)
struct TreeNode
{
    int value;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val)
        : value(val), left(nullptr), right(nullptr)
    {
    }
};

void breadthFirstTraversal(TreeNode* root)
{
    if (root == nullptr)
    {
        return;
    }
    
    Queue queue(100);  // Черга покажчиків (для простоти зберігаємо як int — адреси)
    
    // Додаємо корінь в чергу
    queue.enqueue(reinterpret_cast<int>(root));
    
    std::cout << "BFS traversal: ";
    
    while (!queue.isEmpty())
    {
        // Витягаємо вузол з початку черги
        TreeNode* current = reinterpret_cast<TreeNode*>(queue.front());
        queue.dequeue();
        
        // Обробляємо поточний вузол
        std::cout << current->value << " ";
        
        // Додаємо дітей в чергу (якщо вони існують)
        if (current->left != nullptr)
        {
            queue.enqueue(reinterpret_cast<int>(current->left));
        }
        if (current->right != nullptr)
        {
            queue.enqueue(reinterpret_cast<int>(current->right));
        }
    }
    
    std::cout << '\n';
}

int main()
{
    // Створюємо просте дерево:
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    breadthFirstTraversal(root);  // Виведе: 1 2 3 4 5 (по рівнях)
    
    // Звільнення пам'яті (спрощено)
    delete root->left->right;
    delete root->left->left;
    delete root->left;
    delete root->right;
    delete root;
    
    return 0;
}

Порівняння Stack та Queue: коли використовувати що?

Обмеження поточної реалізації та шляхи розвитку

Наші класи Stack та Queue є навчальними реалізаціями — вони демонструють фундаментальні концепції ADT, але мають обмеження порівняно з промисловими контейнерами (std::stack, std::queue, стаття 95). Розглянемо ключові напрямки вдосконалення:

1. Фіксована ємність vs автоматичне зростання

Поточна реалізація: Ємність задається в конструкторі та не змінюється. Якщо стек/черга переповнюється, генерується виняток.

Промислове рішення: std::stack автоматично збільшує ємність при переповненні (подвоює розмір буфера). Це усуває обмеження на кількість елементів, але має ціну: реалокація — затратна операція O(n).

Як реалізувати: Додайте метод resize() (аналогічно статті 69), який виділяє новий масив подвоєного розміру, копіює елементи та звільняє старий буфер.

2. Підтримка довільних типів через шаблони

Поточна реалізація: Зберігаємо лише int. Для std::string, double чи користувацьких класів потрібна окрема реалізація.

Промислове рішення: std::stack<T> та std::queue<T> — це шаблони класів (стаття 82), що працюють з будь-яким типом T.

Як реалізувати: Перепишіть клас як шаблон:

template<typename T>
class Stack
{
private:
    T* data;  // Замість int* data
    // ... решта без змін
};

Шаблони будуть детально розглянуті у статтях 81–84.

3. Ітератори для зручного обходу

Поточна реалізація: Щоб обійти всі елементи стека, потрібно витягувати їх через pop(), знищуючи стек.

Промислове рішення: STL-контейнери надають ітератори (стаття 87) — об'єкти, що дозволяють обходити елементи без модифікації контейнера:

for (auto it = stack.begin(); it != stack.end(); ++it)
{
    std::cout << *it << '\n';  // Читання без видалення
}

4. Move-семантика для ефективного переміщення

Поточна реалізація: Ми заборонили копіювання через = delete. Якщо потрібно передати стек у функцію, доводиться передавати покажчик або посилання.

Промислове рішення: C++11 надає move-семантику (статті 96–99): об'єкт можна перемістити без копіювання даних — просто передається покажчик на буфер. Це дозволяє повертати контейнери з функцій ефективно.

Stack createFilledStack()
{
    Stack s(100);
    s.push(1);
    s.push(2);
    return s;  // Move, а не копіювання!
}

Резюме: від контейнерів до дисципліни доступу

У цій лекції ми зробили фундаментальний крок від «коробки для зберігання даних» (масиву) до абстрактних типів даних — структур, що визначають не лише зберігання, а й правила доступу до елементів. Стек та черга демонструють потужність інкапсуляції: обмежуючи інтерфейс лише необхідними операціями, ми робимо код безпечнішим, зрозумілішим та стійкішим до помилок.

Ключові концепції:

• ADT (Abstract Data Type): математична модель контейнера з визначеними операціями та семантикою, незалежна від реалізації.
• Stack (LIFO): останній доданий елемент витягується першим. Операції: push, pop, top. Застосування: Undo/Redo, рекурсія, балансування дужок, DFS.
• Queue (FIFO): перший доданий елемент витягується першим. Операції: enqueue, dequeue, front. Застосування: системи обслуговування, BFS, буферизація.
• Кільцевий буфер: техніка реалізації черги з фіксованою ємністю через обертання індексів за модулем розміру.
• Обробка винятків: порушення передумов операцій (витягання з порожнього контейнера, додавання до повного) сигналізується через винятки std::out_of_range та std::overflow_error.

Практичні завдання

#include "Stack.h"
#include <string>
#include <cctype>  // std::tolower, std::isalpha
#include <iostream>

bool isPalindrome(const std::string& str)
{
    // Створюємо стек достатньої ємності
    Stack stack(str.length());
    
    // Фаза 1: Додаємо лише літери (малі) в стек
    std::string cleaned;
    for (char ch : str)
    {
        if (std::isalpha(ch))
        {
            char lower = std::tolower(ch);
            stack.push(lower);
            cleaned += lower;
        }
    }
    
    // Фаза 2: Порівнюємо cleaned з порядком зі стека
    for (char ch : cleaned)
    {
        if (ch != stack.top())
        {
            return false;
        }
        stack.pop();
    }
    
    return true;
}

int main()
{
    std::cout << std::boolalpha;
    std::cout << "\"racecar\": " << isPalindrome("racecar") << '\n';
    std::cout << "\"A man a plan a canal Panama\": " 
              << isPalindrome("A man a plan a canal Panama") << '\n';
    std::cout << "\"hello\": " << isPalindrome("hello") << '\n';
    
    return 0;
}

1
10
11
100
101

#include "Queue.h"
#include <iostream>
#include <string>

// Для простоти зберігаємо рядки як числові коди символів (хак)
// У реальному коді використовували б Queue<std::string> через шаблони

void generateBinaryNumbers(int n)
{
    if (n <= 0)
    {
        return;
    }
    
    // Початок: додаємо "1" (кодуємо рядок через суму ASCII-кодів — хак)
    Queue queue(n * 2);  // Ємність достатня для всіх проміжних значень
    
    std::string current = "1";
    std::cout << current << '\n';
    
    queue.enqueue(1);  // Код "1" — просто символ '1'
    int count = 1;
    
    while (count < n)
    {
        // Витягаємо поточне бінарне число (як код)
        int code = queue.front();
        queue.dequeue();
        
        // Генеруємо наступні два числа: додаємо "0" та "1"
        std::string s = (code == 1) ? "1" : std::to_string(code);
        
        std::string next0 = s + "0";
        std::string next1 = s + "1";
        
        std::cout << next0 << '\n';
        ++count;
        if (count < n)
        {
            std::cout << next1 << '\n';
            ++count;
        }
        
        // Додаємо в чергу для наступних генерацій (хак: числові коди)
        queue.enqueue(std::stoi(next0));
        if (count < n)
        {
            queue.enqueue(std::stoi(next1));
        }
    }
}

int main()
{
    std::cout << "Перші 10 бінарних чисел:\n";
    generateBinaryNumbers(10);
    
    return 0;
}

Ця стаття завершує серію з фундаментальних принципів ООП та відкриває двері до світу складних структур даних: зв'язаних списків, дерев, хеш-таблиць та графів. У наступних лекціях ми продовжимо будувати власні контейнери, а потім вивчимо, як стандартна бібліотека C++ реалізує ці концепції професійно та ефективно.