Привет, сегодня я покажу как сделать очередь на 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)
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; // Тут тоже }Для очередей с приоритетами обычно используют другие структуры данных. Однако ваш способ тоже подходит, если приоритетов строго определённое количество. Если же оно не известно, можно использовать следующие структуры данных: двоичная куча, биномиальная куча и другие кучи.
dvserg
30.05.2022 15:12+4По-хорошему там на calloc разориться можно. По сути идею инкапсуляции данных в объект queue свели к массиву ее мемберов. Смысл такого финта явно в недопонимании того, чего сам на(ш)кодил.
includedlibrary
30.05.2022 15:23callocдля поляdataможно один сделать:q->data = calloc (size_prio * size, sizeof (void *));Остальныеcallocнужны, потому что создаются size_prio очередей. И из первой, в которой есть элементы достаётся первый элемент.
Alexandroppolus
31.05.2022 14:55Однако ваш способ тоже подходит, если приоритетов строго определённое количество
желательно ещё и чтобы это количество было небольшим, порядка ln(N) - логарифм от количества элементов, иначе всё равно неэффективно.
xverizex Автор
02.06.2022 09:59Поменял немного код, теперь побыстрее будет работать. Сделал так, чтобы сразу знать с какого приоритета начинать вести поиск в очереди.
iig
30.05.2022 16:51+3Не знаю как мне приходят такие идеи
На собеседовании спросили разве что? ;)
и я не помню как другие реализуют очередь с приоритетом
Алгоритмы, которые можно вот так взять и изобрести за полчаса - уже изобретены в 70-х годах ;)
mpa4b
30.05.2022 18:07Результаты маллоков в C всё же принято проверять.
Ну и ещё, если такой кольцевой буфер делать строго в 2^n элементов, то можно обойтись совсем без count, а вместо size будет достаточно маски для младших битов. Далее разветвление: или иметь максимум ровно в 2^n элементов, тогда указатели low и high должны иметь n+1 незамаскированных бит, или иметь 2^n-1 элеметов, тогда low и high имеют n незамаскированных бит.
lamerok
30.05.2022 22:06+1Очередь с приоритетом обычно делается через кучу, которая является является инвариантом двоичного дерева. Т. Е. Достаточно просто двоичное дерево реализовать, дальше оно само.
An_private
Переоткрытие кольцевого буфера...
xverizex Автор
Но мы же статьи пишем не только о новых вещах. Если бы были статьи только о новом, то не было бы статей и переводов об уроках по opengl и т.д.
aamonster
Ага, и начинаем их со слов "ко мне пришла идея", чтобы все знали, кто эти вещи изобрёл :-D
amarao
Так тип данных DeQueue или RingBuffer? У них совершенно разная семантика, время доступа к элементам, требования по памяти и разное поведение при переполнении (кольцевого буффера).