Очередь

Очередь - динамическая структура данных, основанная на принципе FIFO (First In - First Out) (Первым пришёл — первым ушёл). В очереди элементы добавляются в конец и извлекаются из начала.

Очередь можно представить в виде связанного списка или массива. В реализации на связанном списке, каждый элемент очереди содержит данные и указатель на следующий элемент. Голова очереди указывает на первый элемент, а хвост указывает на последний элемент. При добавлении нового элемента, он становится новым хвостом, а при извлечении элемента, голова сдвигается на элемент за головой.

Основные операции, которые можно выполнять с очередью, включают добавление элемента в конец очереди (enqueue), извлечение элемента из начала очереди (dequeue) и получение элемента из начала очереди без его удаления (front).

Преимущества очереди:

Порядок элементов: Очередь сохраняет порядок элементов в соответствии с их добавлением. Это означает, что элементы, добавленные раньше, будут извлекаться раньше, что может быть полезно во многих сценариях.
Простота использования: Очередь имеет простой интерфейс, состоящий из основных операций добавления и удаления элементов. Это делает ее легкой в использовании и понимании.
Эффективность при работе с большими объемами данных: Очередь может быть эффективной при обработке больших объемов данных, так как добавление и удаление элементов происходит за $O (1)$ .

Недостатки очереди:

Ограниченный доступ: В очереди доступны только операции добавления в конец (enqueue) и удаления из начала (dequeue). Это означает, что доступ к элементам в середине очереди или изменение уже добавленных элементов может быть затруднено.
Ограниченная емкость: Очередь может иметь ограниченную емкость, что означает, что при достижении максимального количества элементов добавление новых элементов может стать проблемой.
Неэффективность при поиске: Очередь не предоставляет эффективные операции поиска или обновления элементов. Если требуется выполнить поиск или обновление элемента, может потребоваться обход всей очереди.

Реализация стека

Сперва нам необходимо создать структуру Node, которая представляет узел очереди. Она будет иметь поля: data типа int для хранения данных (ключа) и указатель next на тип Node.

struct Node {
  int data;
  Node* next;

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

Теперь создадим функцию enqueue, которая будет добавлять новый элемент в конец очереди.

void enqueue(int data) {
  Node* newNode =
      new Node(data);  // Создание нового узла с переданным значением data
  if (isEmpty()) {     // Проверка, пуста ли очередь
    head = tail = newNode;  // Если очередь пуста, устанавливаем голову и хвост
                            // на новый узел
  } else {
    tail->next =
        newNode;  // Устанавливаем указатель next текущего хвоста на новый узел
    tail = newNode;  // Обновляем хвост очереди на новый узел
  }
}

Далее создадим функцию dequeue, которая будет удалять элемент из начала очереди.

void dequeue() {
  if (isEmpty()) {  // проверяем, пуста ли очередь
    std::cout << "Очередь пуста."
              << "\n";  // если очередь пуста, то выводим сообщение об ошибке и
                        // вовзвращаемся из функции
    return;
  }
  Node* temp = head;  // Создаем временный указатель и устанавливаем его на
                      // голову очереди
  head = head->next;  // Сдвигаем голову на следующий элемент
  delete temp;  // Удаляем предыдущий первый элемент
  if (head == nullptr) {
    tail =
        nullptr;  // Если после удаления головы очередь пуста, обнуляем и хвост
  }
}

Теперь создадим функцию front, которая будет возвращать значение элемента в начале очереди без его удаления, если очередь пуста, то выведется сообщение "очередь пуста".

int front() {
  if (isEmpty()) {
    std::cout << "Queue is empty."
              << "\n";
    return -1;
  }
  return head->data;  // возвращаем значение данных в головном узле
}

bool isEmpty() {
  return head ==
         nullptr;  // возвращаем true, если голова равна nullptr, иначе falsе
}

Код полностью

#include <iostream>

class Queue {
 private:
  struct Node {
    int data;
    Node* next;

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

  Node* head;  // указатель на голову очереди
  Node* tail;  // указатель на хвост очереди

 public:
  Queue()
      : head(nullptr),
        tail(nullptr) {
  }  // Конструктор  Queue()  инициализирует указатели  head  и  tail  значением
     // nullptr , чтобы указать, что очередь пустая

  ~Queue() {
    while (!isEmpty()) {
      dequeue();  // Деструктор  ~Queue()  освобождает память, выделенную для
                  // каждого узла в очереди, путем последовательного вызова
                  // функции  dequeue()  до тех пор, пока очередь не станет
                  // пустой
    }
  }

  void enqueue(int data) {
    Node* newNode = new Node(data);
    if (isEmpty()) {
      head = tail = newNode;
    } else {
      tail->next = newNode;
      tail = newNode;
    }
  }

  void dequeue() {
    if (isEmpty()) {
      std::cout << "Queue is empty." << std::endl;
      return;
    }
    Node* temp = head;
    head = head->next;
    delete temp;
    if (head == nullptr) {
      tail = nullptr;
    }
  }

  int front() {
    if (isEmpty()) {
      std::cout << "Queue is empty." << std::endl;
      return -1;
    }
    return head->data;
  }

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

int main() {
  Queue queue;
  for (int i = 0; i < 3; i++) {
    queue.enqueue(i);  // добавляем числа от 0 до 2
  }

  std::cout << "Первый элемеент:  " << queue.front() << "\n";

  queue.dequeue();  // извлекаем элемент из очереди

  std::cout << "Первый элемент: " << queue.front() << "\n";

  queue.dequeue();  // извлекаем элемент из очереди
  queue.dequeue();  // извлекаем элемент из очереди

  if (queue.isEmpty()) {  // проверяем, пуста ли очередь
    std::cout << "Очередь пуста.";
  }
}

Примеры применения очереди:

Обработка задач: Очередь может использоваться для управления задачами, которые должны быть выполнены в определенном порядке. Например, в операционных системах очередь может использоваться для планирования процессов или потоков выполнения.
Буферизация данных: Очередь может использоваться для временного хранения данных, пока они не будут обработаны. Например, в сетевых приложениях очередь может использоваться для буферизации пакетов данных перед их обработкой или передачей.
Работа с событиями: Очередь может использоваться для управления событиями или сообщениями. Например, в системах обработки событий очередь может использоваться для хранения и обработки событий в порядке их поступления.
Реализация алгоритмов: Очередь может быть использована в реализации различных алгоритмов, таких как обходы графов (например, поиск в ширину), алгоритмы поиска или обработки данных.
Управление ресурсами: Очередь может использоваться для управления доступом к ресурсам, чтобы обеспечить справедливое распределение ресурсов между процессами или потоками.
Моделирование и симуляция: Очередь может использоваться для моделирования и симуляции различных систем или процессов, где требуется учет времени и порядка событий.

Это лишь некоторые примеры применения очереди. Фактически, очередь может быть полезной во многих сценариях, где требуется управление элементами в порядке их добавления и извлечения.