База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / C

FIFO опашка с кръгов буфер

Реализирайте FIFO опашка с фиксиран капацитет в масив чрез два индекса и брояч, за да използвате отново освободените позиции без преместване на елементи.

Версия: ISO C23; implementation support may vary

Синтаксис

#include <stddef.h>

enum { CAPACITY = 3 }; /* Positive, fixed capacity for this example. */
typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

/* Initialize with Queue q = {0}; then pass &q. */
static int enqueue(Queue *q, int value);
static int dequeue(Queue *q, int *out);
/* Both return 1 on success or 0 on full/empty, respectively. */

FIFO означава, че от елементите, които още са в опашката, първо се изважда най-рано добавеният. Кръговият буфер запазва този ред в масив с фиксиран капацитет: след последната позиция индексът се връща на нула, без елементите да се местят. Това е модел за реализация, а не тип от стандартната библиотека на C. Примерът не използва възможности, въведени едва в C23; поддръжката на C23 зависи от реализацията.

При тази конвенция head сочи следващия елемент за четене, когато опашката не е празна, tail сочи следващата позиция за запис, когато не е пълна, а size е броят на елементите. При CAPACITY > 0 двата индекса са в [0, CAPACITY), а size е в [0, CAPACITY]. Математически tail е равно на (head + size) mod CAPACITY. И трите полета започват от нула. head == tail е вярно както за празна, така и за пълна опашка; size различава двете състояния. Могат да се използват всички позиции.

enqueue отказва запис при size == CAPACITY, без да презаписва нищо. Иначе записва на индекс tail, придвижва го напред и увеличава size. dequeue отказва четене при size == 0; иначе копира стойността от индекс head в *out, придвижва head напред и намалява size. И двете функции връщат 1 при успех и 0 при отказ; отказът не променя опашката или евентуалната изходна променлива. Изваждането не изтрива съдържанието на позицията. Изразът (i + 1) % CAPACITY използва остатъка от целочисленото деление, за да върне валиден индекс от последната позиция на нула. Капацитетът не е задължително да е степен на две; делителят не може да е нула.

Всяка операция отнема време O(1), а масивът заема O(CAPACITY) памет. Подайте указател към инициализирана опашка, чийто срок на живот не е приключил; out трябва да сочи отделен обект от тип int, в който може да се записва. Реализацията не синхронизира достъпа: ако няколко нишки използват опашката и поне една я променя, е нужна външна синхронизация.

Примери

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

enum { CAPACITY = 3 };

typedef struct {
    int data[CAPACITY];
    size_t head, tail, size;
} Queue;

static int enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY)
        return 0;
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % CAPACITY;
    ++q->size;
    return 1;
}

static int dequeue(Queue *q, int *out)
{
    if (q->size == 0)
        return 0;
    *out = q->data[q->head];
    q->head = (q->head + 1) % CAPACITY;
    --q->size;
    return 1;
}

int main(void)
{
    Queue q = {0};
    int value;

    if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30))
        return EXIT_FAILURE;
    if (enqueue(&q, 99))
        return EXIT_FAILURE;
    puts("full: rejected 99");

    if (!dequeue(&q, &value))
        return EXIT_FAILURE;
    printf("dequeued: %d\n", value);
    if (!enqueue(&q, 40))
        return EXIT_FAILURE;

    while (dequeue(&q, &value))
        printf("dequeued: %d\n", value);
    puts("empty: nothing to dequeue");
    return EXIT_SUCCESS;
}

Резултат

full: rejected 99
dequeued: 10
dequeued: 20
dequeued: 30
dequeued: 40
empty: nothing to dequeue

След добавяне на `10`, `20` и `30` опашката отказва `99`. Изваждането на `10` освобождава позиция `0` за `40`. Въпреки мястото си в масива, `40` излиза след `20` и `30`. При последния опит за изваждане опашката е празна.

Свързани уроци

  • C · Урок 86 · Напреднало · Версия: 3

Източници