Реализация очереди на C

Привет, сегодня я покажу как сделать очередь на 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;
}

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

Не знаю как мне приходят такие идеи и я не помню как другие реализуют очередь с приоритетом, но моя реализация будет такая. Можно ещё дополнить этот код таким же кодом, чтобы учитывались только заполненные очереди с приоритетом и не приходилось проходить каждый i в цикле в поиске - есть ли в этой очереди какое-то количество элементов.

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

#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;
};

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;
}

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

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

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

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

}

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

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

			return a;
		}
	}

	if (found == 0) {
		printf ("queue is empty\n");
	}

	return a;
}

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++) {
		printf ("%d: %d\n", i, queue_get (q));
	}
}