Design Pattern: Proxy и Структури от Данни Stack и Queue

▶⚡ Накратко

За Изпита

🎯Учебни Цели

След края на тази лекция вие ще можете да:

✓Опишете Proxy Design Pattern и неговите случаи на употреба
✓Обяснете структурите от данни stack и queue, включително техните основни операции
✓Имплементирайте stack и queue в C++ с масиви, свързани списъци и STL
✓Анализирайте как stack и queue функционират като adapter patterns в C++
✓Приложете proxy и adapter принципи в практически програмни сценарии

1. Въведение и Мотивация

💡Защо са важни Design Patterns?

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

Днес ще разгледаме:

Proxy Pattern - за контролиран достъп до обекти
Stack & Queue - фундаментални структури от данни
Adapter Pattern - как STL използва адаптери за stack и queue

Защо Design Patterns подобряват поддръжката?

✅Ползи от Design Patterns

Предоставят общ речник за разработчиците (напр. "Нека използваме Proxy тук")
Водят до по-структуриран, разбираем и разширяем код
Въплъщават принципи като Open/Closed Principle (отворен за разширение, затворен за модификация)
Намаляват бъговете чрез използване на добре тествани подходи

2. Преговор: C++ OOP и Концепции за Памет

2.1. Ключови OOP Характеристики

ℹ️Основни OOP Концепции в C++

Класове: Чертежи за обекти, капсулиращи данни (член променливи) и поведение (член методи).

class Car {
private:
    string brand;
public:
    void setBrand(string b) { brand = b; }
    string getBrand() { return brand; }
};

Интерфейси (Абстрактни класове): C++ използва абстрактни класове с чисто виртуални функции (= 0) за дефиниране на контракти.

class Drawable {
public:
    virtual void draw() = 0; // Чисто виртуална функция
};

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

class Car : public Vehicle {
    // Car наследява от Vehicle
};

2.2. Показалци и Динамично Управление на Паметта

Показалци (Pointers)

Променливи, съхраняващи адреси на памет
Необходими за работа с динамично заделена памет

int x = 10;
int* ptr = &x;
cout << *ptr; // 10

Динамична Памет

new: Заделя памет в heap
delete: Освобождава заделена памет

int* arr = new int[5];
// ... използване ...
delete[] arr;

⚠️Внимание с Паметта!

Динамичната памет е критична за структури от данни като свързани списъци, които трябва да растат или свиват по време на изпълнение. Винаги освобождавайте паметта, която сте заделили!

3. Proxy Design Pattern

3.1. Дефиниция и Намерение

ℹ️Какво е Proxy Pattern?

Proxy Pattern предоставя заместител или placeholder за друг обект, за да контролира достъпа до него.

Намерение: Да добави ниво на индиректност между клиент и реалния обект, позволявайки допълнителна логика без да променя кода на клиента или основната функционалност на реалния обект.

3.2. Основни Роли в Proxy Pattern

// Subject Interface
class Image {
public:
    virtual void display() = 0;
    virtual ~Image() = default;
};

// RealSubject
class RealImage : public Image {
private:
    string filename;
    void loadFromDisk() {
        cout << "Loading " << filename << endl;
    }
public:
    RealImage(string file) : filename(file) {
        loadFromDisk();
    }
    void display() override {
        cout << "Displaying " << filename << endl;
    }
};

// Proxy
class ProxyImage : public Image {
private:
    string filename;
    RealImage* realImage;
public:
    ProxyImage(string file) : filename(file), realImage(nullptr) {}

    void display() override {
        if (realImage == nullptr) {
            realImage = new RealImage(filename); // Lazy loading
        }
        realImage->display();
    }

    ~ProxyImage() { delete realImage; }
};

1. Subject

Интерфейс

Дефинира общите операции за реалния обект и proxy

2. RealSubject

Реален Обект

Компонентът, който извършва основната работа

3. Proxy

Заместител

Обвива RealSubject и добавя допълнителна логика

3.3. Видове Proxies

Цел: Отлага създаването на обекти или зареждането на скъпи ресурси до момента, когато са абсолютно необходими (lazy initialization).

Пример: Зареждане на голям файл с изображение само когато се показва на екрана, а не при стартиране на програмата.

// Примерът по-горе с ProxyImage е Virtual Proxy

Цел: Действа като локален представител на обект, намиращ се в различно адресно пространство (напр. на отдалечен сървър).

Пример: Локален proxy обект управлява мрежовата комуникация с реална услуга на отдалечен сървър.

Цел: Контролира достъпа до реалния обект въз основа на разрешения, автентикация или роли.

Пример: Proxy за база данни проверява потребителските credentials преди да позволи изпълнението на заявки.

Цел: Добавя допълнителна функционалност като кеширане на резултати, логване на извиквания на методи или управление на жизнения цикъл на обекти.

Пример: Caching proxy за уеб API съхранява предишни отговори, за да избегне излишни мрежови заявки.

3.4. Предимства и Ограничения

✅ Предимства

Контролиран достъп до обекти
Подобрена производителност (виртуални proxies)
Повишена сигурност (protection proxies)
Прозрачност за клиента
Разделяне на отговорностите

⚠️ Ограничения

Повишена сложност на кода
Леко забавяне от допълнително извикване
Поддръжка при промени в интерфейса

4. Структури от Данни: Stack и Queue

4.1. Stack - LIFO Принцип

ℹ️Дефиниция на Stack

Stack е линейна структура от данни, която следва принципа LIFO (Last-In, First-Out).

Аналогия: Стек от чинии - можете да добавяте или премахвате само от върха.

Основни Операции (всички O(1)):

// Основни операции на Stack
push(element)  // Добавя елемент на върха
pop()          // Премахва и връща горния елемент
top()          // Връща горния елемент без да го премахва
isEmpty()      // Проверява дали стекът е празен
size()         // Връща броя елементи

💡Типични Приложения на Stack

Function Call Stack: Управление на извиквания на функции и локални променливи
Undo/Redo функционалност: Съхраняване на състояния за връщане назад
Expression Evaluation: Парсване на математически изрази (напр. infix към postfix)
Backtracking алгоритми: Depth-First Search (DFS) често използва stack

4.2. Queue - FIFO Принцип

ℹ️Дефиниция на Queue

Queue е линейна структура от данни, която следва принципа FIFO (First-In, First-Out).

Аналогия: Опашка от хора, чакащи за обслужване - първият в опашката е първият обслужен.

Основни Операции (всички O(1)):

// Основни операции на Queue
enqueue(element) // Добавя елемент в края на опашката
dequeue()        // Премахва и връща предния елемент
front()          // Връща предния елемент без да го премахва
isEmpty()        // Проверява дали опашката е празна
size()           // Връща броя елементи

💡Типични Приложения на Queue

Task Scheduling: Управление на процеси или задачи, чакащи за CPU време
Printer Queues: Обработка на задачи за печат в реда на пристигане
Buffering: Синхронизиране на потока от данни между различни части на системата
Breadth-First Search (BFS): Обхождане на графи ниво по ниво

4.3. Stack vs Queue: Кога Да Използвате Кой

Stack (LIFO)

Използвайте когато:

Трябва да достъпвате елементи в обратен ред
Имплементирате undo/redo
Парсирате изрази с скоби
Използвате DFS

Достъп: Последно добавеният елемент се достъпва пръв

Queue (FIFO)

Използвайте когато:

Трябва да обработвате елементи в реда на пристигане
Имплементирате fair scheduling
Буфериране на данни
Използвате BFS

Достъп: Първо добавеният елемент се достъпва пръв

5. C++ Имплементации на Stack и Queue

5.1. Array-Based Stack

ℹ️Концепция

Използва динамичен масив и integer индекс (top) за проследяване на върха на стека.

Предимства: Прост, cache-friendly (непрекъсната памет) Недостатъци: Фиксиран капацитет (ако не се resize-ва динамично)

class ArrayStack {
private:
    int* arr;
    int top;
    int capacity;

public:
    ArrayStack(int cap) : capacity(cap), top(-1) {
        arr = new int[capacity];
    }

    void push(int x) {
        if (top >= capacity - 1) {
            cout << "Stack overflow!" << endl;
            return;
        }
        arr[++top] = x;
    }

    int pop() {
        if (top < 0) {
            cout << "Stack underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

    int peek() {
        if (top < 0) return -1;
        return arr[top];
    }

    bool isEmpty() { return top == -1; }

    ~ArrayStack() { delete[] arr; }
};

5.2. Circular Array-Based Queue

ℹ️Концепция

Масив, където "краят" се свързва обратно към "началото", за да се използва пространството ефективно. Използва front и rear показалци.

Ключова техника: Модулна аритметика % capacity за циркулярното поведение

class CircularQueue {
private:
    int* buffer;
    int front, rear, size, capacity;

public:
    CircularQueue(int cap) : capacity(cap), size(0), front(0), rear(-1) {
        buffer = new int[capacity];
    }

    void enqueue(int x) {
        if (size == capacity) {
            cout << "Queue is full!" << endl;
            return;
        }
        rear = (rear + 1) % capacity; // Wrap-around
        buffer[rear] = x;
        size++;
    }

    int dequeue() {
        if (size == 0) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        int x = buffer[front];
        front = (front + 1) % capacity; // Wrap-around
        size--;
        return x;
    }

    int getFront() {
        if (size == 0) return -1;
        return buffer[front];
    }

    bool isEmpty() { return size == 0; }

    ~CircularQueue() { delete[] buffer; }
};

✅Защо Циркулярна?

Циркулярната опашка предотвратява изхабяването на пространство. Без циркулярност, при много enqueue/dequeue операции, задната част на масива би останала неизползвана.

5.3. Linked List-Based Stack

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

class LinkedListStack {
private:
    Node* top;

public:
    LinkedListStack() : top(nullptr) {}

    void push(int x) {
        Node* newNode = new Node(x);
        newNode->next = top;
        top = newNode;
    }

    int pop() {
        if (top == nullptr) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        int data = top->data;
        Node* temp = top;
        top = top->next;
        delete temp;
        return data;
    }

    int peek() {
        if (top == nullptr) return -1;
        return top->data;
    }

    bool isEmpty() { return top == nullptr; }

    ~LinkedListStack() {
        while (top != nullptr) {
            Node* temp = top;
            top = top->next;
            delete temp;
        }
    }
};

✅ Предимства

Динамичен размер
Никакъв фиксиран капацитет
Гъвкавост

⚠️ Недостатъци

Допълнителна памет за показалци
Не е cache-friendly
Възлите могат да са разпръснати в паметта

5.4. Linked List-Based Queue

class LinkedListQueue {
private:
    Node* front;
    Node* rear;

public:
    LinkedListQueue() : front(nullptr), rear(nullptr) {}

    void enqueue(int x) {
        Node* newNode = new Node(x);
        if (rear == nullptr) {
            front = rear = newNode;
            return;
        }
        rear->next = newNode;
        rear = newNode;
    }

    int dequeue() {
        if (front == nullptr) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        int data = front->data;
        Node* temp = front;
        front = front->next;
        if (front == nullptr) rear = nullptr; // Queue became empty
        delete temp;
        return data;
    }

    int getFront() {
        if (front == nullptr) return -1;
        return front->data;
    }

    bool isEmpty() { return front == nullptr; }

    ~LinkedListQueue() {
        while (front != nullptr) {
            Node* temp = front;
            front = front->next;
            delete temp;
        }
    }
};

⚠️Внимание при Front и Rear

Внимателно управлявайте показалците front и rear, особено за първия и последния елемент! При dequeue на последния елемент, и двата показалеца трябва да станат nullptr.

6. STL Stack и Queue: Adapter Pattern в Действие

6.1. Какво е Container Adapter?

ℹ️Container Adapters в C++ STL

std::stack и std::queue са container adapters - те не имплементират структурата от данни от нулата, а обвиват съществуващ контейнер и предоставят ограничен интерфейс.

По подразбиране използват std::deque, но можете да зададете различен контейнер!

6.2. Използване на std::stack

#include <stack>
#include <iostream>

int main() {
    std::stack<int> s; // Използва std::deque по подразбиране

    s.push(10);
    s.push(20);
    s.push(30);

    std::cout << "Top: " << s.top() << std::endl; // 30
    s.pop();
    std::cout << "Top: " << s.top() << std::endl; // 20
    std::cout << "Size: " << s.size() << std::endl; // 2

    return 0;
}

Избор на основен контейнер:

std::stack<int, std::vector<int>> s_vec;  // Използва vector
std::stack<int, std::list<int>> s_list;    // Използва list

6.3. Използване на std::queue

#include <queue>
#include <iostream>

int main() {
    std::queue<int> q; // Използва std::deque по подразбиране

    q.push(100);
    q.push(200);
    q.push(300);

    std::cout << "Front: " << q.front() << std::endl; // 100
    q.pop();
    std::cout << "Front: " << q.front() << std::endl; // 200
    std::cout << "Size: " << q.size() << std::endl; // 2

    return 0;
}

Избор на основен контейнер:

std::queue<int, std::list<int>> q_list; // Използва list

6.4. Предимства на STL Container Adapters

✅Защо да Използваме STL?

Опростена имплементация: Не управлявате показалци, масиви или памет ръчно
Добре тествани и оптимизирани: Robust, ефективен код
Гъвкавост: Можете да зададете основния контейнер
Time Complexity гаранции: O(1) за основни операции
Error handling: Вградени проверки за чести проблеми
Съвместимост с Adapter Pattern: Адаптират general-purpose контейнер за специфичен интерфейс

7. Adapter Pattern: Stack и Queue като Примери

7.1. Разбиране на Adapter Pattern

ℹ️Какво е Adapter Pattern?

Adapter Pattern е структурен design pattern, който позволява на два несъвместими интерфейса да работят заедно.

Аналогия: Универсален адаптер за захранване. Той не променя щепсела на лаптопа, нито контакта; просто ги прави съвместими.

Роли:

Target: Интерфейсът, който клиентът очаква
Adaptee: Съществуващият клас с несъвместим интерфейс
Adapter: Класът, който имплементира Target интерфейса и обвива инстанция на Adaptee

7.2. std::stack и std::queue като Adapters

Target Interface

std::stack: push(), pop(), top()

std::queue: push(), pop(), front()

Adaptee

Основен sequence контейнер:

std::deque
std::vector
std::list

Тези имат general методи като push_back(), pop_back(), push_front(), pop_front()

Как работи адаптирането:

// std::stack делегира към adaptee
template<typename T, typename Container = std::deque<T>>
class stack {
private:
    Container c; // Adaptee
public:
    void push(const T& x) { c.push_back(x); }  // Делегира към adaptee
    void pop() { c.pop_back(); }               // Делегира към adaptee
    T& top() { return c.back(); }              // Делегира към adaptee
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

💡Защо този подход?

Енкапсулация, гъвкавост, преизползваемост, използване на производителността. Получавате специфичното поведение (LIFO/FIFO), използвайки най-ефективния основен контейнер за вашите нужди.

8. Case Studies и Code Walkthroughs

8.1. Case Study 1: Virtual Proxy за Зареждане на Изображения

#include <iostream>
#include <string>
using namespace std;

// Subject Interface
class Image {
public:
    virtual void display() = 0;
    virtual ~Image() = default;
};

// RealSubject
class RealImage : public Image {
private:
    string filename;

    void loadFromDisk() {
        cout << "Loading " << filename << " from disk..." << endl;
        // Симулация на бавно зареждане
    }

public:
    RealImage(string file) : filename(file) {
        loadFromDisk();
    }

    void display() override {
        cout << "Displaying " << filename << endl;
    }
};

// Proxy
class ProxyImage : public Image {
private:
    string filename;
    RealImage* realImage;

public:
    ProxyImage(string file) : filename(file), realImage(nullptr) {}

    void display() override {
        if (realImage == nullptr) {
            realImage = new RealImage(filename); // Lazy loading
        }
        realImage->display();
    }

    ~ProxyImage() {
        delete realImage;
    }
};

int main() {
    Image* image = new ProxyImage("large_photo.jpg");
    cout << "Application started. Image object created, but not loaded.\n";

    // Потребителят кликва, за да види изображението...
    cout << "\nUser clicks to view image:\n";
    image->display(); // Реалното изображение се зарежда САМО ТУК

    cout << "\nUser views image again:\n";
    image->display(); // Реалното изображение се преизползва

    delete image;
    return 0;
}

Забележка: "Loading image..." се появява само веднъж, при първото извикване на display(). Това показва lazy initialization!

8.2. Case Study 2: Сравнение Linked-List Stack vs STL Stack

❌

Manual Linked-List Stack

Предимства:

Пълен контрол
Дълбоко разбиране на паметта

Недостатъци:

Ръчно управление на паметта
Boilerplate код
Потенциал за memory leaks

✅

STL Stack

Предимства:

Безопасен, оптимизиран
По-малко код
Използва Adapter pattern
Автоматично управление на паметта

Недостатъци:

По-малко прозрачно относно имплементацията

✅Кога Да Използвате Кой?

Почти винаги използвайте STL за production код! Пишете ръчна имплементация само за учене или специфични low-level нужди.

9. Резюме и Ключови Изводи

ℹ️Резюме

Proxy Pattern:

Действа като surrogate за контролиране на достъпа до RealSubject
Полезен за lazy loading, сигурност, кеширане, логване, remote access
Добавя индиректност, но поддържа консистентен Subject интерфейс

Stack Data Structure:

LIFO (Last-In, First-Out). Операции: push, pop, top
Необходим за function calls, undo/redo, expression evaluation

Queue Data Structure:

FIFO (First-In, First-Out). Операции: enqueue, dequeue, front
Необходим за task scheduling, buffering, BFS

C++ Имплементации:

Могат да бъдат построени ръчно с масиви (циркулярни за queues) или свързани списъци
STL std::stack и std::queue са мощни container adapters

Adapter Pattern:

Позволява на несъвместими интерфейси да работят заедно
std::stack и std::queue адаптират general-purpose контейнери (като std::deque) за предоставяне на специфични LIFO/FIFO интерфейси

✅Добри Практики

Използвайте STL контейнери, когато е възможно - те са тествани и оптимизирани
Разберете trade-offs между различните имплементации
Винаги освобождавайте динамично заделена памет
Използвайте design patterns за по-чист и по-поддържаем код
Изберете подходящата структура от данни според ordering requirements (LIFO vs FIFO)

10. Практически Задачи

Сценарий: Имате DocumentService с метод readDocument(string docId). Създайте SecurityProxy, който проверява дали текущият потребител има разрешение преди да извика readDocument.

Задача: Дефинирайте IDocumentService интерфейс, класа RealDocumentService и класа SecurityProxy.

Предизвикателство: Имплементирайте CircularQueue клас в C++ с методи enqueue(), dequeue(), getFront(), getSize() и isEmpty().

Фокус: Правилно управление на front, rear, size и модулната аритметика за wrap-around.

За всеки сценарий решете дали Stack или Queue е най-подходящ:

Управление на web browser history (back button)
Обработка на входящи съобщения от external система
Оценяване на аритметични изрази със скоби
Задачи, чакащи за single CPU core по fair начин
Съхранение на посетени nodes в Depth-First Search
Print jobs, изпратени към shared network printer

Отговори: 1-Stack, 2-Queue, 3-Stack, 4-Queue, 5-Stack, 6-Queue

Допълнителни Ресурси

Stack и Queue Туториали

Implement Queue using Stacks - GeeksforGeeks - Имплементация на Queue със Stack
Stacks and Queues in C++ - Code of Code - Основи и приложения
Stacks and Queues - CMU CS - Академична лекция
Stack and Queue C++ Programs - GeeksforGeeks - Практически задачи

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

Master Stack and Queue Implementation in C++ - Видео туториал
Stacks and Queues in C++ - CodeSignal - С примери
Implementing Stack, Queue, and Deque - Python и C++

Приложения и Патърни

Stacks & Queues: Concepts and Interview Questions - За интервюта
Understanding Stacks and Queues - Medium - Реални примери

C++ STL

std::stack Reference - Официална документация
std::queue Reference - Официална документация
Stacks and Queues - Princeton - Study guide

Практика

Implement Stack using Queue - Обратната задача

▶⚡ Накратко

🎯Учебни Цели

1. Въведение и Мотивация​

Защо Design Patterns подобряват поддръжката?​

2. Преговор: C++ OOP и Концепции за Памет​

2.1. Ключови OOP Характеристики​

2.2. Показалци и Динамично Управление на Паметта​

Показалци (Pointers)

Динамична Памет

3. Proxy Design Pattern​

3.1. Дефиниция и Намерение​

3.2. Основни Роли в Proxy Pattern​

1. Subject

2. RealSubject

3. Proxy

3.3. Видове Proxies​

3.4. Предимства и Ограничения​

✅ Предимства

⚠️ Ограничения

4. Структури от Данни: Stack и Queue​

4.1. Stack - LIFO Принцип​

4.2. Queue - FIFO Принцип​

4.3. Stack vs Queue: Кога Да Използвате Кой​

Stack (LIFO)

Queue (FIFO)

5. C++ Имплементации на Stack и Queue​

5.1. Array-Based Stack​

5.2. Circular Array-Based Queue​

5.3. Linked List-Based Stack​

✅ Предимства

⚠️ Недостатъци

5.4. Linked List-Based Queue​

6. STL Stack и Queue: Adapter Pattern в Действие​

6.1. Какво е Container Adapter?​

6.2. Използване на std::stack​

6.3. Използване на std::queue​

6.4. Предимства на STL Container Adapters​

7. Adapter Pattern: Stack и Queue като Примери​

7.1. Разбиране на Adapter Pattern​

7.2. std::stack и std::queue като Adapters​

Target Interface

Adaptee

8. Case Studies и Code Walkthroughs​

8.1. Case Study 1: Virtual Proxy за Зареждане на Изображения​

8.2. Case Study 2: Сравнение Linked-List Stack vs STL Stack​

Manual Linked-List Stack

STL Stack

9. Резюме и Ключови Изводи​

Proxy Pattern:​

Stack Data Structure:​

Queue Data Structure:​

C++ Имплементации:​

Adapter Pattern:​

10. Практически Задачи​

Допълнителни Ресурси​

Stack и Queue Туториали​

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

Приложения и Патърни​

C++ STL​

Практика​

1. Въведение и Мотивация

Защо Design Patterns подобряват поддръжката?

2. Преговор: C++ OOP и Концепции за Памет

2.1. Ключови OOP Характеристики

2.2. Показалци и Динамично Управление на Паметта

3. Proxy Design Pattern

3.1. Дефиниция и Намерение

3.2. Основни Роли в Proxy Pattern

3.3. Видове Proxies

3.4. Предимства и Ограничения

4. Структури от Данни: Stack и Queue

4.1. Stack - LIFO Принцип

4.2. Queue - FIFO Принцип

4.3. Stack vs Queue: Кога Да Използвате Кой

5. C++ Имплементации на Stack и Queue

5.1. Array-Based Stack

5.2. Circular Array-Based Queue

5.3. Linked List-Based Stack

5.4. Linked List-Based Queue

6. STL Stack и Queue: Adapter Pattern в Действие

6.1. Какво е Container Adapter?

6.2. Използване на std::stack

6.3. Използване на std::queue

6.4. Предимства на STL Container Adapters

7. Adapter Pattern: Stack и Queue като Примери

7.1. Разбиране на Adapter Pattern

7.2. std::stack и std::queue като Adapters

8. Case Studies и Code Walkthroughs

8.1. Case Study 1: Virtual Proxy за Зареждане на Изображения

8.2. Case Study 2: Сравнение Linked-List Stack vs STL Stack

9. Резюме и Ключови Изводи

Proxy Pattern:

Stack Data Structure:

Queue Data Structure:

C++ Имплементации:

Adapter Pattern:

10. Практически Задачи

Допълнителни Ресурси

Stack и Queue Туториали

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

Приложения и Патърни

C++ STL

Практика