Объясните такие структуры данных, как стек и очередь.cplus-33

Стек и очередь - это фундаментальные абстрактные типы данных (АТД), которые широко используются в программировании. Они различаются принципами доступа к элементам.

1. Стек

Определение:
Структура данных, работающая по принципу LIFO (Last In, First Out - "последним пришел, первым вышел").

Основные операции:

• push - добавление элемента на вершину стека
• pop - удаление элемента с вершины стека
• peek/top - просмотр верхнего элемента без удаления
• isEmpty - проверка на пустоту

#include <stack>
std::stack<int> s;

s.push(10);  // [10]
s.push(20);  // [10, 20]
int top = s.top(); // 20
s.pop();     // [10]

Реализация:

Стек можно реализовать на массиве или односвязном списке:

class ArrayStack {
    int* data;
    int capacity;
    int topIndex;
public:
    void push(int item) {
        if (topIndex == capacity - 1) resize();
        data[++topIndex] = item;
    }
    int pop() {
        if (isEmpty()) throw std::runtime_error("Stack underflow");
        return data[topIndex--];
    }
    // ... другие методы
};

Применение:

• Вызов функций (стек вызовов)
• Отмена действий (undo/redo)
• Парсинг выражений (польская нотация)
• Алгоритмы обхода графов (DFS)

2. Очередь

Определение:
Структура данных, работающая по принципу FIFO (First In, First Out - "первым пришел, первым вышел").

Основные операции:

• enqueue - добавление элемента в конец очереди
• dequeue - удаление элемента из начала очереди
• front - получение первого элемента
• isEmpty - проверка на пустоту

#include <queue>
std::queue<int> q;

q.push(10);  // [10]
q.push(20);  // [10, 20]
int front = q.front(); // 10
q.pop();     // [20]

Реализация:

Очередь можно реализовать на массиве (кольцевом буфере) или связном списке:

class ListQueue {
    struct Node {
        int data;
        Node* next;
    };
    Node* head;
    Node* tail;
public:
    void enqueue(int item) {
        Node* newNode = new Node{item, nullptr};
        if (isEmpty()) head = tail = newNode;
        else tail = tail->next = newNode;
    }
    int dequeue() {
        if (isEmpty()) throw std::runtime_error("Queue underflow");
        int item = head->data;
        Node* temp = head;
        head = head->next;
        delete temp;
        return item;
    }
    // ... другие методы
};

Разновидности очередей:

1. Дек (Deque) - двусторонняя очередь
2. Приоритетная очередь - элементы извлекаются по приоритету
3. Круговая очередь - реализация на массиве фиксированного размера

Применение:

• Обработка задач (планировщики)
• Буферизация ввода/вывода
• Алгоритмы обхода графов (BFS)
• Системы сообщений

Сравнение стека и очереди

Характеристика	Стек	Очередь
Принцип работы	LIFO	FIFO
Операции	push/pop	enqueue/dequeue
Сложность операций	O(1)	O(1)
Типичное применение	Вызов функций	Обработка задач

Резюмируем

• Стек - LIFO структура, где элементы добавляются и удаляются с одного конца
• Очередь - FIFO структура, где элементы добавляются в конец, а удаляются из начала
• Обе структуры имеют O(1) сложность основных операций
• Выбор между стеком и очередью зависит от требуемой семантики доступа к данным
• В C++ доступны готовые реализации (std::stack, std::queue) в STL