Привет, сегодня поговорим про очереди, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое очереди, очередь, циклическая очередь , настоятельно рекомендую прочитать все из категории Структуры данных.

очередь — это линейный список информации, работа с которой происходит по принципу "первым пришел — первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO . Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.

Представление очереди FIFO (first in, first out)

Примеры:

• Очередь писем для отправки пользователям.

• Обработка загрузки файлов (ставится в очередь и поочередно загружается).

Очереди очень часто встречаются в реальной жизни, например, около банков или ресторанов быстрого обслуживания. Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"— "сохранять", "retrieve" — "получать"). Функцияqstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В табл. 22.1 показано действие последовательности таких операций.

Как известно, программы состоят из двух частей — алгоритмов и структур данных. В хорошей программе эти составляющие эффективно дополняют друг друга. Выбор и реализация структуры данных насколько же важны, как и процедуры для обработки данных. Способ организации и доступа к информации обычно определяется природой программируемой задачи. Таким образом, для программиста важно иметь в своем распоряжении приемы, подходящие для различных ситуаций.

Степень привязки типа данных к своему машинному представлению находится в обратной зависимости от его абстракции. Другими словами, чем более абстрактными становятся типы данных, тем больше концептуальное представление о способе хранения этих данных отличается от реального, фактического способа их хранения в памяти компьютера Простые типы, например, char или int, тесно связаны со своим машинным представлением. Например, машинное представление целочисленного значения хорошо аппроксимирует соответствующую концепцию программирования. По мере своего усложнения типы данных становятся концептуально менее похожими на свои машинные эквиваленты. Так, действительные числа с плавающей точкой более абстрактны, чем целые числа. Фактическое представление типа float в машине весьма приблизительно соответствует представлению среднего программиста о действительном числе. Еще более абстрактной является структура, принадлежащая к составным типам данных.

На следующем уровне абстракции сугубо физические аспекты данных отходят на второй план вследствие введения механизма доступа(data engine) к данным, то есть механизма сохранения и получения информации. По существу, физические данные связываются с механизмом доступа, который управляет работой с данными из программы. Именно механизмам доступа к данным и посвящена эта глава.

Существует четыре механизма доступа:

• Очередь (queue)
• Стек (stack)
• Связанный список (linked list)
• Двоичное дерево (binary tree)

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

• Очереди
• циклическая очередь
• Стеки
• Связанные списки
• Односвязные списки
• Двусвязные списки
• Пример списка рассылки
• Двоичные деревья

Другие названия: магазин, стековая память, магазинная память, память магазинного типа, запоминающее устройство магазинного типа, стековое запоминающее устройство.

Другие названия: цепной список, список с использованием указателей, список со ссылками, список на указателях.

Другие названия: дерево двоичного поиска.

Виды очередей

В этой статье вы познакомитесь с различными видами очередей. Всего существует 4 типа очередей. Коротко и с картинками о каждой.

<div style="box-sizing: inherit; color: rgb(74, 74, 74); font-family: BlinkMacSystemFont, -apple-system, " segoe="" ui",="" roboto,="" oxygen,="" ubuntu,="" cantarell,="" "fira="" sans",="" "droid="" "helvetica="" neue",="" helvetica,="" arial,="" sans-serif;="" font-size:="" 16px;"="">

Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Об этом говорит сайт https://intellect.icu . Поэтому после извлечения всех элементов очередь будет пуста.

В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач — симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.

Чтобы проиллюстрировать работу очереди, мы напишем простую программу планирования встреч. Эта программа позволяет сохранять информацию о некотором количестве встреч; потом по мере прохождения каждой встречи она удаляется из списка. Для упрощения описание встреч ограничено 255 символами, а количество встреч — произвольным числом 100.

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

#define MAX 100

char *p[MAX];
int spos = 0;
int rpos = 0;

/* Сохранение встречи. */
void qstore(char *q)
{
  if(spos==MAX) {
    printf("Список переполнен\n");
    return;
  }
  p[spos] = q;
  spos++;
}

/* Получение встречи. */
char *qretrieve()
{
  if(rpos==spos) {
    printf("Встреч больше нет.\n");
    return '\0';
  }
  rpos++;
  return p[rpos-1];
}

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

Функция qstore() помещает описания новых встреч в конец списка и проверяет, не переполнен ли список. Функция qretrieve()извлекает встречи из очереди, если таковые имеются. При назначении встреч увеличивается значение переменной spos, а по мере их прохождения увеличивается значение переменной rpos. По существу, rpos "догоняет" spos в очереди. На рис 22.1 показано, что может происходить в памяти при выполнении программы. Если rpos и spos равны, назначенные события отсутствуют. Даже несмотря на то, что функция qretrieve() не уничтожает хранящуюся в очереди информацию физически, эту информацию можно считать уничтоженной, так как повторно получить доступ к ней невозможно.

Рис. 22.1. Индекс выборки "догоняет" индекс вставки

	Начальное сосотояние очереди

  ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
  ↑rpos

	qstore('A')

      ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
  ↑rpos

	qstore('B')

          ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
| A | B |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
  ↑rpos

	qretrive()

          ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
|   | B |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
      ↑rpos

	qretrive()

          ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
          ↑rpos

	qstore('A')

              ↓spos
+---+---+---+---+---+---+---+---+---+---+---+
|   |   | C |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+---+
          ↑rpos

Текст программы простого планировщика встреч целиком приведен ниже. Вы можете доработать эту программу по своему усмотрению.

/* Мини-планировщик событий */

#include 
#include 
#include 
#include 

#define MAX 100

char *p[MAX], *qretrieve(void);
int spos = 0;
int rpos = 0;
void enter(void), qstore(char *q), review(void), delete_ap(void);

int main(void)
{
  char s[80];
  register int t;

  for(t=0; t < MAX; ++t) p[t] = NULL; /* иницилизировать массив
                                         пустыми указателями */

  for(;;) {
    printf("Ввести (E), Список (L), Удалить (R), Выход (Q): ");
    gets(s);
    *s = toupper(*s);

    switch(*s) {
      case 'E':
        enter();
        break;
      case 'L':
        review();
        break;
      case 'R':
        delete_ap();
        break;
      case 'Q':
        exit(0);
    }
  }
  return 0;
}

/* Вставка в очередь новой встречи. */
void enter(void)
{
  char s[256], *p;

  do {
    printf("Введите встречу %d: ", spos+1);
    gets(s);
    if(*s==0) break; /* запись не была произведена */
    p = (char *) malloc(strlen(s)+1);
    if(!p) {
      printf("Не хватает памяти.\n");
      return;
    }
    strcpy(p, s);
    if(*s) qstore(p);
  } while(*s);
}

/* Просмотр содержимого очереди. */
void review(void)
{
  register int t;

  for(t=rpos; t < spos; ++t)
    printf("%d. %s\n", t+1, p[t]);
}

/* Удаление встречи из очереди. */
void delete_ap(void)
{
  char *p;

  if((p=qretrieve())==NULL) return;
  printf("%s\n", p);
}

/* Вставка встречи. */
void qstore(char *q)
{
  if(spos==MAX) {
    printf("List Full\n");
    return;
  }
  p[spos] = q;
  spos++;
}

/* Извлечение встречи. */
char *qretrieve(void)
{
  if(rpos==spos) {
    printf("Встречь больше нет.\n");
    return NULL;
  }
  rpos++;
  return p[rpos-1];
}

Этот принцип имеет и другие названия: "первым пришел — первым обслужен", "в порядке поступления", "первым пришел — первым вышел", "обратного магазинного типа".

Циклическая очередь

При изучении предыдущего примера программы планирования встреч, вероятно, вам в голову мог прийти следующий способ ее улучшения: при достижении конца массива, в котором хранится очередь, можно не останавливать программу, а устанавливать индексы вставки (spos) и извлечения (rpos) так, чтобы они указывали на начало массива. Это позволит помещать в очередь любое количество элементов при условии их своевременного извлечения. Такая реализация очереди называется циклической очередью, поскольку массив используется так, будто он представляет собой не линейный список, а кольцо.

Чтобы организовать в программе-планировщике циклическую очередь, функции qstore() и qretrieve() необходимо переписать следующим образом:

void qstore(char *q)
{
  /* Очередь переполняется, когда spos на единицу
     меньше rpos, либо когда spos указывает
     на конец массива, а rpos - на начало.
  */
  if(spos+1==rpos || (spos+1==MAX && !rpos)) {
    printf("Список полон\n");
    return;
  }

  p[spos] = q;
  spos++;
  if(spos==MAX) spos = 0; /* установить на начало */
}

char *qretrieve(void)
{
  if(rpos==MAX) rpos = 0; /* установить на начало */
  if(rpos==spos) {
    printf("Встреч больше нет.\n");
    return NULL;
  }
  rpos++;
  return p[rpos-1];
}

В данной версии программы очередь переполняется, когда индекс записи находится непосредственно перед индексом извлечения; в противном случае еще есть место для вставки события. Очередь пуста, когда rpos равняется spos.

Вероятно, чаще всего циклические очереди применяются в операционных системах для хранения информации, учитываемой и записываемой в дисковые файлы или на консоль. Циклические очереди также используются в программах обработки реального времени, которые должны продолжать обрабатывать информацию, буферизируя при этом запросы на ввод/вывод. Многие текстовые процессоры используют этот прием во время переформатирования абзаца или выравнивания строки. Вводимый текст не отображается на экране до окончания процесса. Для этого прикладная программа должна проверять нажатие клавиш во время выполнения другой задачи. Если какая-либо клавиша была нажата, введенный символ быстро помещается в очередь, и процесс продолжается. После его завершения символы извлекаются из очереди.

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

Чтобы программа работала, как описано выше, в ней необходимо использовать две функции, не определенные в стандартном языке С:_kbhit() и _getch(). Функция _kbhit() возвращает значение ИСТИНА, если на клавиатуре была нажата клавиша; в противном случае она возвращает ЛОЖЬ. Функция _getch() считывает введенный символ, но не дублирует его на экране. В стандарте языка С не предусмотрены функции для проверки состояния клавиатуры или считывания символов без отображения на экране, поскольку эти функции зависят от операционной системы. Тем не менее, в большинстве библиотек компиляторов есть функции, выполняющие данные задачи. Приведенная здесь небольшая программа компилируется с помощью компилятора Microsoft.

/* Пример циклической очереди в качестве буфера клавиатуры. */
#include 
#include 
#include 

#define MAX 80

char buf[MAX+1];
int spos = 0;
int rpos = 0;

void qstore(char q);
char qretrieve(void);

int main(void)
{
  register char ch;
  int t;

  buf[80] = '\0';

  /* Принимать вводимые символы до нажатия . */
  for(ch=' ',t=0; t<32000 && ch!='\r'; ++t) {
    if(_kbhit()) {
      ch = _getch();
      qstore(ch);
    }
    printf("%d ", t);
    if(ch == '\r') {
      /* Вывести на экран содержимое буфера клавиатуры
         и освободить буфер. */
      printf("\n");
      while((ch=qretrieve()) != '\0') printf("%c", ch);
      printf("\n");
    }
  }
  return 0;
}

/* Занесение символа в очередь. */
void qstore(char q)
{
  if(spos+1==rpos || (spos+1==MAX && !rpos)) {
    printf("Список полон\n");
    return;
  }
  buf[spos] = q;
  spos++;
  if(spos==MAX) spos = 0; /* установить на начало */
}

/* Получение символа из очереди. */
char qretrieve(void)
{
  if(rpos==MAX) rpos = 0; /* установить на начало */
  if(rpos==spos) return '\0';

  rpos++;
  return buf[rpos-1];
}

Способы реализации очереди

Существует несколько способов реализации очереди в языках программирования.

Массив

Первый способ представляет очередь в виде массива и двух целочисленных переменных start и end.

Обычно start указывает на голову очереди, end — на элемент, который заполнится, когда в очередь войдет новый элемент. При добавлении элемента в очередь в q[end] записывается новый элемент очереди, а end уменьшается на единицу. Если значение end становится меньше 1, то мы как бы циклически обходим массив, и значение переменной становится равным n. Извлечение элемента из очереди производится аналогично: после извлечения элемента q[start] из очереди переменная start уменьшается на 1. С такими алгоритмами одна ячейка из n всегда будет незанятой (так как очередь с n элементами невозможно отличить от пустой), что компенсируется простотой алгоритмов.

Преимущества данного метода: возможна незначительная экономия памяти по сравнению со вторым способом; проще в разработке.

Недостатки: максимальное количество элементов в очереди ограничено размером массива. При его переполнении требуется перевыделение памяти и копирование всех элементов в новый массив.

Связный список

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

Преимущества данного метода: размер очереди ограничен лишь объемом памяти.

Недостатки: сложнее в разработке; требуется больше памяти; при работе с такой очередью память сильнее фрагментируется; работа с очередью несколько медленнее.

Реализация на двух стеках

Методы очереди могут быть реализованы на основе двух стеков S1 и S2, как показано ниже:

Процедура enqueue(x):
    S1.push(x)

Функция dequeue():
    если S2 пуст:
        если S1 пуст:
            сообщить об ошибке: очередь пуста

        пока S1 не пуст:
            S2.push(S1.pop())

    вернуть S2.pop()

Такой способ реализации наиболее удобен в качестве основы для построения персистентной очереди

Очереди в различных языках программирования

Практически во всех развитых языках программирования реализованы очереди. В CLI для этого предусмотрен класс System.Collections.Queue с методами Enqueue и Dequeue. В STL также присутствует класс queue<>, определенный в заголовочном файле queue. В нем используется та же терминология (push и pop), что и в стеках.

Сравнительная таблица очереди с другими основными структурами данных:

Характеристика	Очередь (Queue)	Стек (Stack)	Связанный список (Linked List)	Массив (Array)	Дек (Deque)	Куча (Heap)
Принцип работы	FIFO (первый вошел — первый вышел)	LIFO (последний вошел — первый вышел)	Элементы связаны указателями	Индексы фиксированы	Доступ к обоим концам	Дерево, где родитель >= (max heap) или <= (min heap) дочерних элементов
Добавление элементов	В конец (enqueue)	В конец (push)	В начало или конец	В любую позицию	В начало или конец	В корень (с балансировкой)
Удаление элементов	Из начала (dequeue)	Из конца (pop)	В любой позиции (требует обхода)	В любой позиции (но требует сдвига)	В начало и конец	Из корня (с перестановкой)
Доступ к элементам	Только к первому (head)	Только к последнему (top)	Последовательный (через ссылки)	Прямой доступ по индексу	В начало и конец	Только к корню (наибольший или наименьший элемент)
Время работы (среднее)	O(1) (добавление/удаление)	O(1) (добавление/удаление)	O(1) (добавление в начало/конец)	O(1) (доступ), O(n) (вставка/удаление)	O(1) (операции с концами)	O(log n) (добавление, удаление, доступ к корню)
Где используется	Фоновые задачи, управление потоками, BFS-алгоритмы	Рекурсия, отмена действий (Ctrl+Z)	Динамические структуры, обход графов	Статические структуры, быстрый доступ	Буферы, парсеры, обработка данных	Очередь с приоритетами, алгоритмы Дейкстры и Хаффмана, хранение классов

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

Куча особенно полезна, когда нужно быстро находить наибольший или наименьший элемент

Применение очередей

Очередь в программировании используется, как и в реальной жизни, когда нужно совершить какие-то действия в порядке их поступления, выполнив их последовательно. Примером может служить организация событий в Windows. Когда пользователь оказывает какое-то действие на приложение, то в приложении не вызывается соответствующая процедура (ведь в этот момент приложение может совершать другие действия), а ему присылается сообщение, содержащее информацию о совершенном действии, это сообщение ставится в очередь, и только когда будут обработаны сообщения, пришедшие ранее, приложение выполнит необходимое действие.

Клавиатурный буфер BIOS организован в виде кольцевого массива, обычно длиной в 16 машинных слов, и двух указателей: на следующий элемент в нем и на первый незанятый элемент.

Очереди в веб-программировании используются для обработки задач асинхронно, распределения нагрузки и повышения производительности. Они помогают избежать долгих задержек в обработке запросов, позволяя выполнять сложные или ресурсоемкие операции в фоне.

Основные сценарии применения очередей:

1. Фоновая обработка задач

   • Отправка email-уведомлений

   • Генерация отчетов

   • Обработка изображений или видео

2. Балансировка нагрузки

   • Равномерное распределение нагрузки на сервер

   • Устранение пиковых нагрузок (например, при массовых запросах)

3. Повышение отказоустойчивости

   • Если сервер падает, задача не теряется, а обрабатывается позже

   • Возможность повторного выполнения задачи при сбоях

4. Обработка вебхуков и событий

   • Интеграция с внешними API (например, платежные системы)

   • Реализация event-driven архитектуры

5. Чат-боты и уведомления в реальном времени

   • Очередь сообщений для пользователей

   • Очередь событий для обработки данных в реальном времени

Популярные инструменты для очередей

• Redis (RQ, Celery, BullMQ) – быстрая и простая очередь на основе Redis

• RabbitMQ – продвинутая система очередей на основе AMQP

• Kafka – мощная распределенная очередь для обработки больших потоков данных

• AWS SQS – облачное решение для очередей

В веб-разработке очереди помогают сделать приложения более отзывчивыми, масштабируемыми и стабильными.

Вау!! 😲 Ты еще не читал? Это зря!

• статические структуры данных , вектор структура данных ,
• дерево , обход дерева ,
• структура данных и алгоритм ,
• массив , массивы ,
• абстрактный тип данных , abstract data type ,
• динамические структуры данных , связные списки ,
• тесты по алгоритмам и структурам данных ,

• список , односвязные списки ,
• дерево , обход дерева ,
• кольцевой буфер , кольцевой буфер ,
• двухсторонняя очередь ,
• приоритетная очередь , очередь с приоритетом ,
• дек
• теория массового обслуживания ,
• стек , стеки ,
• Конвейер (Pipeline)

На этом все! Теперь вы знаете все про очереди, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое очереди, очередь, циклическая очередь и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Структуры данных