Очередь (Queue) - это абстрактная структура для работы с последовательностью данных, обслуживание которых происходит в соответствии с дисциплиной FIFO (FIRST IN, FIRST OUT - первым пришел, первым обслужен). Согласно принципу FIFO новые данные добавляются (записываются) в хвост очереди, а наличные данные извлекаются (считываются) из головы очереди. Извлекать данные из очереди и добавлять их в очередь можно неоднократно, пока очередь не пуста и не переполнена, соответственно.
Состояние очереди характеризуется парой указателей: tail - указатель на хвост (конец) очереди и head - указатель на голову (начало) очереди. При изменении содержания очереди за счет чтения или записи данных меняется состояние очереди и соответственно, значение указателей на ее голову или хвост. Новые данные записываются в ячейку очереди, адрес которой определяет значение указателя tail. После этого значение tail изменяется так, чтобы указывать на следующую свободную ячейку очереди. Чтение существующих данных происходит из ячейки, адрес которой определяет указатель head. После этого значение head изменяется так, чтобы указывать на следующий занятый элемент очереди.
Для хранения данных в очереди выделяется специальный буфер qbuf (queue bufer). В простейшем случае буфер очереди реализуется одномерным массивом элементов, длина которого априори устанавливает предельный размер очереди qsize (queue size), задаваемый при создании очереди. Такая организация очереди называется очередью с линейным фиксированным буфером (Line Queue).
Указатели на хвост и голову очереди интерпретируются в ней как целочисленные индексы массива, представляющего буфер очереди. Они могут изменяться в пределах от 0 до (qsize-1). В начальном состоянии очередь пуста и оба указателя имеют нулевое значение (tail=head=0).
Логическую структуру очереди с линейным фиксированным буфером, где размещены 5 элементов # иллюстрирует следующая диаграмма:

Рис. 1.  Логическая структура очереди с линейным фиксированным буфером

Рассмотренный линейный вариант очереди с фиксированным линейным буфером имеет ограниченное применение, т. к. для корректной работы значение указателя головы очереди не должно превышать значения указателя на хвост очереди (head<=tail). Это условие не позволяет добавлять новые элементы, когда хвост очереди исчерпан (tile=qsize), даже если в начале буфера очереди имеются свободные ячейки, после извлечения головных элементов (head>0). Это тупиковое состояние переполнения очереди с линейным фиксированным буфером показано на следующем рисунке, где 8 элементов # занимают конечные ячейки буфера очереди, а в его начале имеются 2 свободные ячейки:

Рис. 2.  Переполнение очереди с линейным фиксированным буфером

Чтобы иметь возможность использовать свободные ячейки в начале буфера очереди, которые образовались после чтения головных элементов, нужно применять более совершенную организацию очереди, известную как очередь с кольцевым фиксированным буфером (RingQueue). Кольцевой фиксированный буфер следует рассматривать как замкнутый линейный буфер qbuf, который после заполнения его до конца может заполняться сначала, если там имеются свободные ячейки. Чтобы превратить линейный буфер в кольцевой достаточно интерпретировать указатели головы и хвоста очереди как целочисленные индексы массива qbuf, взятые по модулю размера буфера очереди (qsize).

head mod qsize и tail mod qsize,

соответственно. Операция mod здесь интерпретируется как вычисление остатка целочисленного деления head и tail на qsize. Таким образом, любой из указателей обнуляется, когда его значение становится равным qsize, т. е. выходит за границы массива буфера очереди, например:

  IF head = qsize THEN head <- 0; 
 и IF tail = qsize THEN tail <- 0. 

Жесткое условие корректности непустой очереди с линейным фиксированным буфером (head<tail) в очереди с кольцевым буфером становится необязательным, т. е. состояние, когда указатель хвоста опережает указатель головы очереди (tail<head) также является разрешенным. Оба разрешенных состояния очереди с фиксированным кольцевым буфером показаны на следующем рисунке:

Рис. 3.  Состояния очереди с кольцевым буфером

Для работы с очередью используются 2 классических примитива: ENQUEUE и DEQUEUE, которые обеспечивают добавление (запись) данных в очередь и извлечение (чтение) данных из очереди, соответственно. В очереди с кольцевым буфером они имеют реализацию рассмотренную ниже.
Примитив DEQUEUE возвращает элемент из головы очереди и увеличивает на 1 значение указателя head. Если значение head при этом выходит за границу буфера очереди, то head следует обнулить. Псевдокод примитива DEQUEUE выражают следующие операторы:

  W <- qbuf [head]; 
  head <- head+1 mod qsize; 
  return W; 

где W обозначает элемент данных, извлекаемый из очереди.
Примитив ENQUEUE загружает новый элемент в хвост очереди и увеличивает на 1 значение указателя tail. Если значение tail при этом выходит за границу буфера очереди, то tail следует обнулить. Псевдокод примитива ENQUEUE выражают следующие операторы:

  qbuf [tail] <- V; 
  tail <- tail+1 mod qsize; 
  return; 

где V обозначает элемент данных, извлекаемый из очереди.
Для очереди с фиксированным кольцевым буфером процедура извлечения (чтения) данных необязательно является деструктивной операцией, т. е. извлеченные элементы не уничтожаются в буфере очереди до записи на их место новых данных. Процедура добавления (записи) данных имеет деструктивный эффект, модифицируя содержание буфера очереди. Рассмотренные примитивы DEQUEUE и ENQUEUE обеспечивают корректную обработку очереди с фиксированным кольцевым буфером, когда он не пуст и не переполнен соответственно. Для корректной обработки этих критических ситуаций нужно установить соотношение указателей, при которых кольцевой буфер будет пуст или переполнен.
Критическим состоянием при чтении данных является пустая очередь, где все ячейки свободны. Формальным условием пустой очереди является равенство обоих указателей:

    tail = head 

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

   head = tail+1  mod  qsize

Если выполняется это соотношение, нельзя добавлять элементы в очередь, несмотря на то, что имеется 1 свободная ячейка, на которую указывает текущее значение tail. Иначе критерием переполнения очереди было бы равенство tail=head, которое является истинным также для пустой очереди. Чтобы иметь возможность отличать оба критических состояния очереди с кольцевым буфером, в нем должно содержаться от 0 до (qsize-1) значащих элементов при не менее, чем одной свободной ячейке. Указанную проверку переполнения можно использовать в сочетании с примитивом ENQUEUE, чтобы избежать потери значимости при попытке записи данных, когда исчерпан лимит свободных ячеек.