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

Сама очередь состоит из такой структуры.

struct queue {
        uint8_t *data;  // указатель на данные
        int low;        // указатель на нижнюю границу
        int high;       // указатель на верхнюю границу
        int count;      // количество элементов в очереди
        int max;        // максимальное количество элементов
};

Инициализируем очередь.

struct queue *init (size_t size)
{
        struct queue * q = calloc (1, sizeof (struct queue));
        q->data = calloc (size, sizeof (uint8_t));
        q->low = q->high = size - 1;
        q->max = size;

        return q;
}

Добавляем в очередь.

void queue_add (struct queue *q, uint8_t a)
{

        if (q->count == q->max) {
                fprintf (stderr, "not enough queue size\n");
                return;
        }

        q->data[q->low--] = a;
        q->count++;

        if (q->low < 0) {
                q->low = q->max - 1;
        }

}

Удаляем из очереди.

uint8_t queue_get (struct queue *q)
{
        uint8_t a = q->data[q->high--];
        q->count--;

        if (q->high < 0) {
                q->high = q->max - 1;
        }

        return a;
}

Алгоритм до того простой, что из него можно сделать очередь с приоритетом, подправив структуру и функции. Приведу сразу весь код очереди с приоритетом и проверкой результата.

Не знаю как мне приходят такие идеи и я не помню как другие реализуют очередь с приоритетом, но моя реализация будет такая.

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

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

struct queue {
	uint8_t **data;
	int *low;
	int *high;
	int *count;
	int *max;
	int max_prio;
	int min_prio;
};

struct queue *init (size_t size, int size_prio)
{
	struct queue * q = calloc (1, sizeof (struct queue));
	q->max_prio = size_prio;

	q->data = calloc (size_prio, sizeof (void *));
	q->low = calloc (size, sizeof (int));
	q->high = calloc (size, sizeof (int));
	q->max = calloc (size, sizeof (int));
	q->count = calloc (size, sizeof (int));

	for (int i = 0; i < size_prio; i++) {
		q->data[i] = calloc (size, sizeof (uint8_t));
		q->low[i] = q->high[i] = size - 1;
		q->max[i] = size;
	}

	return q;
}

int queue_add (struct queue *q, uint8_t a, int prio)
{

	if (q->min_prio > prio) q->min_prio = prio;

	if (q->count[prio] == q->max[prio]) {
		fprintf (stderr, "not enough queue size\n");
		return -1;
	}

	q->data[prio][q->low[prio]--] = a;
	q->count[prio]++;

	if (q->low[prio] < 0) {
		q->low[prio] = q->max[prio] - 1;
	}

	return 0;
}

int queue_get (struct queue *q, uint8_t *val)
{
	uint8_t a = 0;
	for (int i = q->min_prio; i < q->max_prio; i++) {
		if (q->count[i] > 0) {
			a = q->data[i][q->high[i]--];
			q->count[i]--;

			if (q->high[i] < 0) {
				q->high[i] = q->max[i] - 1;
			}

			q->min_prio = i;

			*val = a;
			return 0;
		}
	}

	printf ("queue is empty\n");
	return -1;
}

int main (int argc, char **argv)
{
	struct queue *q = init (10, 4);

	queue_add (q, 2, 3);
	queue_add (q, 10, 1);
	queue_add (q, 15, 1);
	queue_add (q, 20, 0);

	for (int i = 0; i < 4; i++) {
		uint8_t d;
		int ret = queue_get (q, &d);
		printf ("%d: %d\n", i, d);
	}
}

Комментарии (15)


  1. An_private
    30.05.2022 14:57
    +11

    Переоткрытие кольцевого буфера...


    1. xverizex Автор
      30.05.2022 15:00
      -7

      Но мы же статьи пишем не только о новых вещах. Если бы были статьи только о новом, то не было бы статей и переводов об уроках по opengl и т.д.


      1. aamonster
        30.05.2022 15:04
        +14

        Ага, и начинаем их со слов "ко мне пришла идея", чтобы все знали, кто эти вещи изобрёл :-D


    1. amarao
      30.05.2022 16:49

      Так тип данных DeQueue или RingBuffer? У них совершенно разная семантика, время доступа к элементам, требования по памяти и разное поведение при переполнении (кольцевого буффера).


  1. dvserg
    30.05.2022 15:02
    -1

    del


  1. includedlibrary
    30.05.2022 15:02
    +5

    По-хорошему размеры лучше делать не интами, а size_t. Из queue_add возвращать результат, по которому можно узнать, произошла ли ошибка. Например, можно bool возвращать. Ещё такой момент - создам я очередь, добавлю в неё элемент, тогда q->high будет равен нулю. Однако, в queue_get есть такая строчка: `uint8_t a = q->data[q->high--];, которая сразу приведёт к неверному результату. Плюс неплохо было сделать функцию для освобождения памяти, которую использует очередь

    Upd: Сразу не заметил, что вы использовали двойное присваивание `q->low = q->high = size-1`

    Upd 2: Очередь с приоритетом страдает от тех же ошибок, что и без приоритета. Плюс ещё парочка замечаний:

    queue_get должен явно сигнализировать, что очередь пуста, а не только в консоль об этом писать.

    	for (int i = 0; i < size_prio; i++) {
    		q->data[i] = calloc (size, sizeof (uint8_t));
    		q->low[i] = q->high[i] = size - 1; // А если size_prio > size?
    		q->max[i] = size; // Тут тоже
    	}

    Для очередей с приоритетами обычно используют другие структуры данных. Однако ваш способ тоже подходит, если приоритетов строго определённое количество. Если же оно не известно, можно использовать следующие структуры данных: двоичная куча, биномиальная куча и другие кучи.


    1. dvserg
      30.05.2022 15:12
      +4

      По-хорошему там на calloc разориться можно. По сути идею инкапсуляции данных в объект queue свели к массиву ее мемберов. Смысл такого финта явно в недопонимании того, чего сам на(ш)кодил.


      1. includedlibrary
        30.05.2022 15:23

        calloc для поля data можно один сделать: q->data = calloc (size_prio * size, sizeof (void *)); Остальные calloc нужны, потому что создаются size_prio очередей. И из первой, в которой есть элементы достаётся первый элемент.


    1. Alexandroppolus
      31.05.2022 14:55

      Однако ваш способ тоже подходит, если приоритетов строго определённое количество

      желательно ещё и чтобы это количество было небольшим, порядка ln(N) - логарифм от количества элементов, иначе всё равно неэффективно.


    1. xverizex Автор
      02.06.2022 09:59

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


  1. GarryC
    30.05.2022 15:38

    "Мда, ничего не скажешь, а остальное вы уже видели..."


  1. iig
    30.05.2022 16:51
    +3

    Не знаю как мне приходят такие идеи

    На собеседовании спросили разве что? ;)

    и я не помню как другие реализуют очередь с приоритетом

    Алгоритмы, которые можно вот так взять и изобрести за полчаса - уже изобретены в 70-х годах ;)


  1. mpa4b
    30.05.2022 18:07

    Результаты маллоков в C всё же принято проверять.

    Ну и ещё, если такой кольцевой буфер делать строго в 2^n элементов, то можно обойтись совсем без count, а вместо size будет достаточно маски для младших битов. Далее разветвление: или иметь максимум ровно в 2^n элементов, тогда указатели low и high должны иметь n+1 незамаскированных бит, или иметь 2^n-1 элеметов, тогда low и high имеют n незамаскированных бит.


  1. e-zig
    30.05.2022 18:44
    +1

    Тоже баловался таким, на плюсах только.

    https://github.com/e-zig/RwCBuf


  1. lamerok
    30.05.2022 22:06
    +1

    Очередь с приоритетом обычно делается через кучу, которая является является инвариантом двоичного дерева. Т. Е. Достаточно просто двоичное дерево реализовать, дальше оно само.