</>EmbeddedInterview

Implement a queue using an array (circular queue) and using a linked list.

Easy"Coding: Linked Lists, Stacks & Queues"
#include <stdbool.h>
#include <stdlib.h>

/* circular array queue with an explicit count (no wasted slot) */
#define Q_CAP 8
typedef struct { int buf[Q_CAP]; unsigned head, count; } cqueue_t;

bool cq_push(cqueue_t *q, int v)
{
    if (q->count == Q_CAP) return false;                  /* full */
    q->buf[(q->head + q->count) % Q_CAP] = v;
    q->count++;
    return true;
}

bool cq_pop(cqueue_t *q, int *v)
{
    if (q->count == 0) return false;                      /* empty */
    *v = q->buf[q->head];
    q->head = (q->head + 1) % Q_CAP;
    q->count--;
    return true;
}

/* linked-list queue: enqueue at tail, dequeue at head */
typedef struct qn { int v; struct qn *next; } qn_t;
typedef struct { qn_t *head, *tail; } lqueue_t;

bool lq_push(lqueue_t *q, int v)
{
    qn_t *n = malloc(sizeof *n);
    if (!n) return false;
    n->v = v; n->next = NULL;
    if (q->tail) q->tail->next = n; else q->head = n;
    q->tail = n;
    return true;
}

bool lq_pop(lqueue_t *q, int *v)
{
    if (!q->head) return false;
    qn_t *n = q->head;
    *v = n->v;
    q->head = n->next;
    if (!q->head) q->tail = NULL;                         /* queue became empty */
    free(n);
    return true;
}

Points: in the circular queue, indexes wrap with % (or & (CAP-1) if CAP is a power of two); tracking count distinguishes full from empty (the alternative is leaving one slot empty). The linked-list version must reset tail when the queue empties. For an ISR producer and a task consumer, use the lock-free SPSC ring buffer in the embedded coding topic instead.