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