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

CKTIS / C

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

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

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

Синтаксис

Queue q = {0};
bool enqueue(Queue *q, int value);
bool dequeue(Queue *q, int *out);

/* Advance a valid index; CAPACITY must be positive. */
index = (index + 1) % CAPACITY;

FIFO опашка (first in, first out, първи влязъл, първи излязъл) премахва най-стария елемент, който още е в опашката. FIFO определя реда, а кръговият буфер е един начин за реализацията му. Queue, enqueue и dequeue са дефинирани в примера и не са част от стандартната библиотека на C.

Queue q = {0}; инициализира празна опашка. head е индексът на най-стария елемент, когато опашката не е празна, а tail е индексът за следващия запис, когато тя не е пълна. И двата индекса са от 0 до CAPACITY - 1. size брои заетите позиции, от 0 до CAPACITY. Математически tail ≡ head + size (mod CAPACITY), така че само head == tail не различава празна опашка от пълна; size ги различава.

Ако има място, enqueue записва стойността на позиция tail, премества tail напред и увеличава size. Ако опашката не е празна, dequeue копира стойността от позиция head в *out, премества head напред и намалява size. За преместването се използва (index + 1) % CAPACITY: % дава остатъка от делението, така че след последния индекс отново идва 0. CAPACITY трябва да е положителен; нулев делител при % води до неопределено поведение.

И двете функции връщат true при успех и false, когато операцията е отказана, защото опашката е съответно пълна или празна. Отказът не променя опашката, а при dequeue не променя и *out. q трябва да сочи към инициализирана опашка, чийто живот не е приключил, а out — към отделен, все още съществуващ обект от тип int, в който може да се записва. Всяка операция отнема O(1) време, а масивът заема O(CAPACITY) памет. Реализацията не заделя динамично памет и не синхронизира нишки. Примерът предполага хоствана среда и не изисква възможности, специфични за C23; поддръжката на режим ISO C23 зависи от реализацията.

Примери

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

enum { CAPACITY = 3 };

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

static size_t next_index(size_t index)
{
    return (index + 1) % CAPACITY;
}

static bool enqueue(Queue *q, int value)
{
    if (q->size == CAPACITY) {
        return false;
    }
    q->data[q->tail] = value;
    q->tail = next_index(q->tail);
    ++q->size;
    return true;
}

static bool dequeue(Queue *q, int *out)
{
    if (q->size == 0) {
        return false;
    }
    *out = q->data[q->head];
    q->head = next_index(q->head);
    --q->size;
    return true;
}

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");

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

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

Резултат

full
10
20
30
40
empty

След три записа `tail` се връща на `0`. Опитът за добавяне на `99` отпечатва `full`, без да презаписва `10`. След премахването на `10` стойността `40` заема отново позиция `0`, но излиза след `20` и `30`. Неуспешният опит за извличане от празната опашка прекратява цикъла; програмата отпечатва `empty`.

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

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

Източници