Hàng đợi vòng

/* Không quay vòng: chỉ số chỉ tăng, chạm biên là hết */
q->data[q->rear++] = v;

/* Quay vòng: chỉ số quay lại 0 sau khi vượt quá cuối mảng */
q->data[(q->front + q->size) % QMAX] = v;

#ifndef CQUEUE_H
#define CQUEUE_H

#include <stddef.h>

#define QMAX 8

/* Bất biến:
     1. 0 <= front < QMAX
     2. 0 <= size <= QMAX
     3. Phần tử thứ i tính từ đầu nằm ở data[(front + i) % QMAX]  */
typedef struct {
    int    data[QMAX];
    size_t front;
    size_t size;
} CQueue;

void   cq_khoi_tao(CQueue *q);
int    cq_rong(const CQueue *q);
int    cq_day(const CQueue *q);
size_t cq_so_phan_tu(const CQueue *q);
int    cq_enqueue(CQueue *q, int v);
int    cq_dequeue(CQueue *q, int *out);
int    cq_xem_dau(const CQueue *q, int *out);
void   cq_in(const CQueue *q);

#endif

#include <stdio.h>

#include "cqueue.h"

void cq_khoi_tao(CQueue *q)
{
    q->front = 0;
    q->size  = 0;
}

int cq_rong(const CQueue *q) { return q->size == 0; }
int cq_day (const CQueue *q) { return q->size == QMAX; }

size_t cq_so_phan_tu(const CQueue *q) { return q->size; }

/* Thêm vào đuôi. O(1). Trả về 0 nếu ổn, -1 nếu đầy. */
int cq_enqueue(CQueue *q, int v)
{
    if (q->size == QMAX) return -1;

    q->data[(q->front + q->size) % QMAX] = v;
    ++q->size;

    return 0;
}

/* Lấy ở đầu. O(1). Trả về 0 nếu ổn, -1 nếu rỗng. */
int cq_dequeue(CQueue *q, int *out)
{
    if (q->size == 0) return -1;

    if (out != NULL) *out = q->data[q->front];

    q->front = (q->front + 1) % QMAX;
    --q->size;

    return 0;
}

int cq_xem_dau(const CQueue *q, int *out)
{
    if (q->size == 0) return -1;

    if (out != NULL) *out = q->data[q->front];

    return 0;
}

/* In cả trạng thái bên trong để thấy chỉ số quay vòng. */
void cq_in(const CQueue *q)
{
    printf("front=%zu size=%zu  [", q->front, q->size);

    for (size_t i = 0; i < q->size; ++i) {
        printf("%d", q->data[(q->front + i) % QMAX]);

        if (i + 1 < q->size) printf(", ");
    }

    printf("]  o nho: ");

    for (size_t k = 0; k < QMAX; ++k) {
        int dang_dung = 0;

        for (size_t i = 0; i < q->size; ++i)
            if ((q->front + i) % QMAX == k) dang_dung = 1;

        if (dang_dung) printf("%d ", q->data[k]);
        else           printf(". ");
    }

    printf("\n");
}

#include <stdio.h>

#include "cqueue.h"

int main(void)
{
    CQueue q;
    int    v;

    cq_khoi_tao(&q);

    for (int i = 1; i <= 6; ++i) cq_enqueue(&q, i * 10);

    cq_in(&q);

    for (int i = 0; i < 5; ++i) cq_dequeue(&q, &v);

    cq_in(&q);

    /* Thêm tiếp, chỉ số sẽ quay vòng qua đầu mảng */
    for (int i = 1; i <= 6; ++i) cq_enqueue(&q, i * 100);

    cq_in(&q);

    printf("day chua : %d\n", cq_day(&q));
    printf("them nua : %d\n", cq_enqueue(&q, 999));

    printf("lay het  : ");

    while (cq_dequeue(&q, &v) == 0) printf("%d ", v);

    printf("\n");
    cq_in(&q);

    return 0;
}

/* Với N là lũy thừa của 2:
     x % N  ==  x & (N - 1)      khi x không âm

   Ví dụ N = 8, tức N - 1 = 7 = 0b111:
     13 % 8 = 5      13 & 7 = 0b1101 & 0b0111 = 0b101 = 5
     16 % 8 = 0      16 & 7 = 0b10000 & 0b00111 = 0        */

#define QMAX      8
#define QMASK     (QMAX - 1)

_Static_assert((QMAX & QMASK) == 0, "QMAX phai la luy thua cua 2");

int cq_enqueue(CQueue *q, int v)
{
    if (q->size == QMAX) return -1;

    q->data[(q->front + q->size) & QMASK] = v;
    ++q->size;

    return 0;
}

#include <stdint.h>

#define RX_SIZE  256
#define RX_MASK  (RX_SIZE - 1)

_Static_assert((RX_SIZE & RX_MASK) == 0, "RX_SIZE phai la luy thua cua 2");

/* Một bên ghi, một bên đọc. Với đúng một người ghi và đúng một người đọc,
   cấu trúc này an toàn mà KHÔNG cần khóa, nếu hai chỉ số là nguyên tử. */
static volatile uint8_t  rx_dem[RX_SIZE];
static volatile uint16_t rx_ghi;      /* chỉ trình xử lý ngắt sửa */
static volatile uint16_t rx_doc;      /* chỉ vòng lặp chính sửa */

/* Gọi từ trình xử lý ngắt. Trả về 0 nếu chứa được, -1 nếu đầy. */
int rx_them(uint8_t b)
{
    uint16_t ke = (uint16_t)((rx_ghi + 1) & RX_MASK);

    if (ke == rx_doc) return -1;      /* đầy, hy sinh một ô để phân biệt */

    rx_dem[rx_ghi] = b;
    rx_ghi         = ke;              /* cập nhật SAU khi ghi dữ liệu */

    return 0;
}

/* Gọi từ vòng lặp chính. Trả về 0 nếu lấy được, -1 nếu rỗng. */
int rx_lay(uint8_t *ra)
{
    if (rx_doc == rx_ghi) return -1;  /* rỗng */

    *ra    = rx_dem[rx_doc];
    rx_doc = (uint16_t)((rx_doc + 1) & RX_MASK);

    return 0;
}

/* Với nhật ký, đầy không nên là lỗi. Ghi đè bản ghi cũ nhất
   hợp lý hơn, vì thông tin gần đây quan trọng hơn thông tin cũ. */
void log_them(CQueue *q, int v)
{
    if (q->size == QMAX) {
        q->data[q->front] = v;                    /* ghi đè ô cũ nhất */
        q->front          = (q->front + 1) % QMAX; /* đẩy front lên */
    } else {
        q->data[(q->front + q->size) % QMAX] = v;
        ++q->size;
    }
}