Stacks, Queues & Rings

Stacks reverse order; queues preserve it

A stack removes the last item pushed (LIFO); a queue removes the oldest (FIFO). Both can use fixed arrays. The distinction is the retrieval rule, not whether memory was allocated dynamically. A stack is useful for unfinished nested work; a queue models arrivals waiting for service.

Push A,B,C. A stack pops C,B,A; a queue pops A,B,C. A bracket checker pushes opening brackets and requires each closing bracket to match the most recent opening bracket, which explains why a stack fits.

What should a bounded stack do when push finds count==capacity?

Return failure without writing beyond storage or increasing count. Underflow needs the symmetric check before decrementing or reading. The caller—not the stack—chooses whether to drop, retry or report the event.

Ring layout is not chronological order

A circular queue reuses positions modulo capacity. Read and write indices refer to physical storage, while the logical sequence begins at read and wraps. Choose one full/empty convention and use it consistently: count, a reserved slot, or monotonic counters with a proven range.

Capacity 4: push A,B,C; pop A; push D,E. Physical storage is [E,B,C,D] but logical order is [B,C,D,E]. A loop over physical indices 0..3 would scramble arrival order.

With the reserved-slot convention, how many records fit in an eight-slot array?

Seven. The unused slot distinguishes full from empty. This is a representation choice, not a universal property of every ring queue.

A deque can maintain candidates, not just all items

A deque supports insertion/removal at both ends. For a sliding maximum, keep candidate indices in decreasing value order: remove expired indices from the front and smaller obsolete candidates from the back. A later larger value dominates an earlier smaller one because it also remains in the window longer.

For window size 3 over [4,2,5,1], arrival 5 removes 2 then 4 from the candidate back; both lose to 5. The candidate deque then holds index 2. When 1 arrives, keep it behind 5 as a possible future maximum.

Why is the monotonic deque linear overall even though one arrival can remove several entries?

Every index enters once and leaves at most once, giving O(n) total deque work. One individual update can still be O(window size), so amortised constant work is not a per-call latency guarantee.

Save work until a consumer is ready

A queue removes the oldest item first. A ring queue reuses slots after their contents have been consumed.

Imagine an interrupt receiving bytes while the main loop processes them. The producer writes the next free slot; the consumer reads the oldest occupied slot. When a position reaches the end of the array it wraps to zero.

For a first implementation, keep read, write and count. count=0 means empty; count=4 means full. Pushing into a full ring must follow a documented policy. Rejecting the new byte is simple and preserves unread data.

This implementation assumes one execution context or external synchronization. If an interrupt and main loop both modify count, an interrupted update can lose a change. Single-producer/single-consumer designs often give each side its own index, but publishing a slot safely still depends on the C memory model and target.

Follow the worked example

• Start read=write=count=0.
• Push 10,20,30: slots [10,20,30,_], write=3, count=3.
• Pop 10: read=1, count=2.
• Push 40 then 50: slots [50,20,30,40], write=1, count=4. Read order is 20,30,40,50.

Connect the steps to code

#include <stdbool.h>
unsigned q[4], write_pos = 0, count = 0;
bool push(unsigned x) {
    if (count == 4) return false;
    q[write_pos] = x;
    write_pos = (write_pos + 1u) % 4u;
    ++count;
    return true;
}

• Writing the payload happens before declaring another occupied slot.
• The modulo wraps the physical index; it does not create more capacity.
• Pair this with a pop routine that advances its own read position and decrements count; serialize calls in this introductory version.

Check your understanding

Can write==read alone distinguish a full queue from an empty one?

No. Both can have equal indices. Use count, a reserved slot, or another explicit convention.

Lists, Pools & Arenas next separates object location from logical order.

Easy - Byte Ring Buffer

The buffer between a UART receive interrupt and the main loop. This is the single most common data structure in all of firmware.

Implement init, push, and pop for a fixed-capacity byte ring using the sacrifice-one-slot convention. Test wraparound and full/empty states.

Bounded byte ring with explicit full status

Single-context or externally serialized ring. Capacity includes one reserved slot; push never overwrites unread data.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t *data;
    size_t capacity;
    size_t head;
    size_t tail;
} byte_ring_t;

bool ring_init(byte_ring_t *r, uint8_t *storage, size_t capacity) {
    if (r == NULL || storage == NULL || capacity < 2u) return false;
    *r = (byte_ring_t){ .data=storage, .capacity=capacity, .head=0u, .tail=0u };
    return true;
}

bool ring_push(byte_ring_t *r, uint8_t value) {
    size_t next = r->head + 1u;
    if (next == r->capacity) next = 0u;
    if (next == r->tail) return false;
    r->data[r->head] = value;
    r->head = next;
    return true;
}

bool ring_pop(byte_ring_t *r, uint8_t *out) {
    if (out == NULL || r->tail == r->head) return false;
    *out = r->data[r->tail];
    if (++r->tail == r->capacity) r->tail = 0u;
    return true;
}

• head names the next write slot and tail names the next read slot.
• head==tail is empty; next(head)==tail is full.
• Write data before moving head; read data before moving tail.

Cases the tests must cover

• capacity two
• fill then reject
• wrap head and tail
• FIFO order
• pop empty

How it gets written wrong

• This version is not automatically thread/ISR safe.
• Never add a shared count without synchronization.

Hard - ISR-to-Main SPSC Queue

Every ISR-to-main-loop handoff on a single-core MCU, and the standard lock-free structure between two RTOS tasks of different priority.

Implement a power-of-two single-producer/single-consumer queue with C11 acquire/release atomics and no shared count field.

C11 SPSC event queue

Exactly one producer calls push and one consumer calls pop. Capacity is a power of two and one slot is reserved.

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef uint32_t event_t;
typedef struct {
    event_t *data;
    size_t mask;
    _Atomic size_t head;
    _Atomic size_t tail;
} spsc_t;

bool spsc_init(spsc_t *q, event_t *storage, size_t capacity) {
    if (q == NULL || storage == NULL || capacity < 2u ||
        (capacity & (capacity - 1u)) != 0u) return false;
    q->data=storage; q->mask=capacity-1u;
    atomic_init(&q->head,0u); atomic_init(&q->tail,0u);
    return true;
}

bool spsc_push(spsc_t *q, event_t value) {
    size_t head=atomic_load_explicit(&q->head,memory_order_relaxed);
    size_t next=(head+1u)&q->mask;
    if (next==atomic_load_explicit(&q->tail,memory_order_acquire)) return false;
    q->data[head]=value;
    atomic_store_explicit(&q->head,next,memory_order_release);
    return true;
}

bool spsc_pop(spsc_t *q, event_t *out) {
    size_t tail=atomic_load_explicit(&q->tail,memory_order_relaxed);
    if (out==NULL || tail==atomic_load_explicit(&q->head,memory_order_acquire)) return false;
    *out=q->data[tail];
    atomic_store_explicit(&q->tail,(tail+1u)&q->mask,memory_order_release);
    return true;
}

• Single-writer ownership avoids atomic RMW on the indices.
• Release publishes the preceding slot write; acquire observes it before the slot read.
• The mask replaces modulus only because capacity is validated as a power of two.

Cases the tests must cover

• publish/consume one event
• wrap repeatedly
• full reject preserves data
• FIFO sequence
• stress with one producer and one consumer

How it gets written wrong

• Not MPSC or MPMC.
• C atomics may not be lock-free for every type/target; verify toolchain and ISR rules.

Medium - Three-Level Event Queue

An event dispatcher that must service a fault before a telemetry update, without letting telemetry starve entirely.

Maintain three fixed FIFO queues and always pop the oldest event from the highest non-empty priority without starving low priority forever.

Three-priority FIFO with aging anti-starvation

push enqueues into one of three fixed FIFOs by priority; pop returns the oldest event from the highest non-empty priority, but after AGING_LIMIT consecutive high-priority pops one lower-priority event is served to bound starvation. Rejects push to a full FIFO.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t kind; uint32_t payload; } event_t;
enum { PRIO_HIGH = 0, PRIO_MED = 1, PRIO_LOW = 2, PRIO_LEVELS = 3 };
#define EV_CAP 8u
#define AGING_LIMIT 4u   /* max consecutive higher-priority pops before demotion */

typedef struct {
    event_t buf[PRIO_LEVELS][EV_CAP];
    size_t head[PRIO_LEVELS], tail[PRIO_LEVELS], count[PRIO_LEVELS];
    unsigned served_high;   /* consecutive pops from above-lowest levels */
} event_q_t;

void event_q_init(event_q_t *q) {
    *q = (event_q_t){ 0 };
}

bool event_push(event_q_t *q, event_t event, unsigned prio) {
    if (q == NULL || prio >= PRIO_LEVELS) return false;
    if (q->count[prio] == EV_CAP) return false;      /* this level is full */
    q->buf[prio][q->head[prio]] = event;
    q->head[prio] = (q->head[prio] + 1u) % EV_CAP;
    q->count[prio]++;
    return true;
}

bool event_pop(event_q_t *q, event_t *event) {
    if (q == NULL || event == NULL) return false;
    /* Choose the highest non-empty level, unless aging forces a
       lower-level event through to bound its wait. */
    int level = -1;
    for (int p = PRIO_HIGH; p <= PRIO_LOW; p++) {
        if (q->count[p] > 0u) { level = p; break; }
    }
    if (level < 0) return false;                     /* all empty */
    for (int p = level + 1; p <= PRIO_LOW; p++) {
        if (q->served_high >= AGING_LIMIT && q->count[p] > 0u) {
            level = p;                               /* serve the starved level */
            break;
        }
    }
    *event = q->buf[level][q->tail[level]];
    q->tail[level] = (q->tail[level] + 1u) % EV_CAP;
    q->count[level]--;
    if (level == PRIO_HIGH) q->served_high++;
    else q->served_high = 0u;
    return true;
}

• Strict priority (always drain HIGH first) is simple but starves LOW forever under sustained high load. Aging fixes it with one counter: after AGING_LIMIT consecutive high-priority services, one low-priority event jumps the queue.
• Per-level FIFO order is preserved — aging only decides which level serves next, never reorders within a level, so same-priority events stay causal.
• All state lives in fixed arrays: three rings of EV_CAP with head/tail/count. No allocation, deterministic worst-case memory, and pop is O(levels) = O(3) = O(1) in practice.
• The served_high counter resets whenever a lower level is served, so aging credits recharge naturally during idle mix rather than accumulating debt.
• Tuning AGING_LIMIT is a product decision: 0 is strict round-robin-ish demotion, infinity is pure strict priority. Measure with your real event mix.

Cases the tests must cover

• Interleaved pushes pop all HIGH first, then MED, then LOW
• Sustained HIGH load: every AGING_LIMIT+1 pops, one LOW event escapes
• Same-priority events pop in push order (FIFO per level)
• Push to a full level returns false while other levels still accept
• Pop from empty queue returns false

How it gets written wrong

• Pure strict priority with no aging — the field failure mode is a low-priority log queue that never drains during a storm of high-priority alarms.
• Reordering within a priority level to implement aging; it breaks causality for same-level events.
• Using one shared ring with per-event priority and scanning for the best: O(n) pops and unbounded latency jitter.

Medium - Tiny Integer Expression Evaluator

Evaluating a configuration expression or a scripted threshold on-device: a rule engine for alarms, a calculator in a debug shell, a small formula in a config file.

Evaluate decimal integers with +, -, *, parentheses, and unary minus using fixed-size caller-provided stacks. Reject malformed input and overflow.

Two-stack integer expression evaluator

Evaluates decimal integers with + - * parentheses and unary minus, using caller-provided value/operator stacks of depth cap. Returns EVAL_OK, EVAL_SYNTAX (malformed), EVAL_OVERFLOW (int32 range), or EVAL_DEPTH (stacks too small). No allocation, no recursion.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum { EVAL_OK, EVAL_SYNTAX, EVAL_OVERFLOW, EVAL_DEPTH } eval_status_t;

static int prec(char op) { return op == '*' ? 2 : 1; }  /* + and - share 1 */

static bool apply(int32_t *vals, size_t *nv, char *ops, size_t *no) {
    if (*no == 0u || *nv < 2u) return false;
    char op = ops[--(*no)];
    int32_t b = vals[--(*nv)];
    int32_t a = vals[--(*nv)];
    int64_t r;                                   /* evaluate wide, then range-check */
    if (op == '+') r = (int64_t)a + b;
    else if (op == '-') r = (int64_t)a - b;
    else r = (int64_t)a * b;
    if (r > INT32_MAX || r < INT32_MIN) return false;
    vals[(*nv)++] = (int32_t)r;
    return true;
}

eval_status_t eval(const char *expr, int32_t *result,
                   int32_t *values, char *ops, size_t cap) {
    if (expr == NULL || result == NULL || values == NULL || ops == NULL)
        return EVAL_SYNTAX;
    size_t nv = 0u, no = 0u;
    bool want_operand = true;                    /* unary minus only legal here */
    for (const char *p = expr; ; p++) {
        char c = *p;
        if (c == ' ') continue;
        if (c >= '0' && c <= '9') {
            if (!want_operand) return EVAL_SYNTAX;   /* "2 3" is malformed */
            int64_t v = 0;
            while (*p >= '0' && *p <= '9') {
                v = v * 10 + (*p - '0');
                if (v > INT32_MAX) return EVAL_OVERFLOW;
                p++;
            }
            p--;
            if (nv == cap) return EVAL_DEPTH;
            values[nv++] = (int32_t)v;
            want_operand = false;
            continue;
        }
        if (c == '-' && want_operand) {          /* unary minus: 0 - x */
            if (nv == cap || no == cap) return EVAL_DEPTH;
            values[nv++] = 0;
            ops[no++] = '-';
            continue;                            /* still want the operand */
        }
        if (c == '(') {
            if (no == cap) return EVAL_DEPTH;
            ops[no++] = c;
            want_operand = true;
            continue;
        }
        if (c == ')') {
            while (no > 0u && ops[no - 1u] != '(') {
                if (!apply(values, &nv, ops, &no)) return EVAL_SYNTAX;
            }
            if (no == 0u) return EVAL_SYNTAX;    /* unmatched ')' */
            no--;                                /* discard '(' */
            want_operand = false;
            continue;
        }
        if (c == '+' || c == '-' || c == '*') {
            if (want_operand) return EVAL_SYNTAX;
            while (no > 0u && ops[no - 1u] != '(' &&
                   prec(ops[no - 1u]) >= prec(c)) {
                if (!apply(values, &nv, ops, &no)) return EVAL_OVERFLOW;
            }
            if (no == cap) return EVAL_DEPTH;
            ops[no++] = c;
            want_operand = true;
            continue;
        }
        if (c == '\0') break;
        return EVAL_SYNTAX;                      /* unknown character */
    }
    if (want_operand) return EVAL_SYNTAX;        /* expression ended after an op */
    while (no > 0u) {
        if (ops[no - 1u] == '(') return EVAL_SYNTAX;   /* unmatched '(' */
        if (!apply(values, &nv, ops, &no)) return EVAL_OVERFLOW;
    }
    if (nv != 1u) return EVAL_SYNTAX;
    *result = values[0];
    return EVAL_OK;
}

• Dijkstra's shunting-yard idea with two stacks: numbers go on the value stack, operators wait on the operator stack. Before pushing a new operator, apply every waiting operator of equal-or-higher precedence — that is what makes 2+3*4 evaluate the multiply first.
• Parentheses are just fence posts on the operator stack: '(' blocks reduction until the matching ')' flushes everything above it, turning a sub-expression into a single value.
• Unary minus is the classic edge case. The want_operand flag tracks whether a value or an operator is expected next; a '-' seen while wanting an operand becomes '0 -' so it reuses the binary machinery.
• All arithmetic runs in int64_t and is range-checked before narrowing — signed overflow in C is undefined behavior, so you must detect it before it happens, not test for it afterwards.
• Caller-provided stacks with a depth limit make this safe for an RTOS shell: worst-case memory is known at compile time and EVAL_DEPTH fails the command instead of corrupting a stack.

Cases the tests must cover

• "2+3*4" = 14, "(2+3)*4" = 20 (precedence and parens)
• "-3 + 5" = 2, "-(3+2)*2" = -10 (unary minus)
• "2000000000+2000000000" → EVAL_OVERFLOW
• "2 +", "(2+3", "2 3" → EVAL_SYNTAX
• Deeply nested parens beyond cap → EVAL_DEPTH, no memory corruption

How it gets written wrong

• Reducing with > instead of >= precedence: a-b-c then evaluates as a-(b-c).
• Treating every '-' as binary — expressions like '3*-2' then misparse.
• Applying operators in wrong operand order (b - a instead of a - b): subtraction and division are not commutative.
• Testing for overflow after a 32-bit multiply already wrapped; that is UB, not a detectable condition.

Easy - Ring Watermark Telemetry

Sizing a buffer from evidence rather than guesswork: recording the deepest the ring ever got so the next build can right-size it.

Extend a ring buffer to track high-water occupancy and total rejected pushes without changing push/pop complexity.

Ring buffer with high-water and drop telemetry

Monitored push records the highest occupancy ever seen and counts every rejected push. Both counters are readable for diagnostics; push/pop stay O(1) and never overwrite unread data.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t *data;
    size_t capacity;      /* usable slots are capacity - 1 (sacrifice slot) */
    size_t head;          /* next write */
    size_t tail;          /* next read */
    size_t high_water;    /* max occupancy ever observed */
    uint32_t dropped;     /* pushes rejected because the ring was full */
} monitored_ring_t;

static size_t ring_used(const monitored_ring_t *rb) {
    /* head >= tail unless wrapped; subtraction under mod capacity handles both */
    return (rb->head + rb->capacity - rb->tail) % rb->capacity;
}

bool monitored_push(monitored_ring_t *rb, uint8_t byte) {
    if (rb == NULL) return false;
    size_t next = (rb->head + 1u) % rb->capacity;
    if (next == rb->tail) {       /* full: one slot is sacrificed to tell full from empty */
        rb->dropped++;
        return false;
    }
    rb->data[rb->head] = byte;
    rb->head = next;
    size_t used = ring_used(rb);
    if (used > rb->high_water) {  /* new worst case: record for sizing analysis */
        rb->high_water = used;
    }
    return true;
}

• Production firmware question number one: 'did my buffer ever almost overflow?' The high-water mark answers it without a debugger — after a field trial you read one counter and know whether the ring was sized right.
• The drop counter converts silent data loss into observable telemetry. A rising dropped count in a cloud dashboard is the difference between discovering a bug and shipping it.
• Both updates ride along inside the existing push path: one subtraction for occupancy and one compare. Complexity stays O(1) because no history is kept, only extremes.
• Occupancy uses modular subtraction, which reads correctly whether or not head has wrapped past tail — the standard trick for sacrifice-one-slot rings.
• If the producer is an ISR and the counters are read from a task, make them _Atomic or snapshot them with interrupts masked; a torn 32-bit read on a Cortex-M0 sends garbage to your dashboard.

Cases the tests must cover

• Fill to capacity-1: high_water equals capacity-1, no drops
• Push into a full ring: returns false, dropped increments, data unchanged
• Pop everything then push again: high_water retains the historic peak
• Wraparound traffic keeps occupancy correct across the wrap boundary
• dropped saturates (or wraps by contract) after 2^32-1 rejections — pick one and test it

How it gets written wrong

• Updating high_water with the pre-push occupancy — you never record the final slot being used.
• Counting drops but not recording the peak; each answers a different sizing question and both are nearly free.
• Computing occupancy as head - tail without the modular fix, which underflows to a huge size_t after wrap.

Medium - Bounded Double-Ended Queue

A window that must be trimmed from both ends: the monotonic deque behind a sliding maximum, or a scroll-back buffer with eviction at both ends.

Implement push and pop at both ends of a fixed ring without moving elements. Keep a count field so full and empty are unambiguous, and reject overflow and underflow.

Fixed double-ended queue

All four operations are O(1) and return false on overflow/underflow. A count field, not head==tail, defines empty and full.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t buf[8]; size_t head; size_t count; } deque_t;
/* head = index of the front element; count removes full/empty ambiguity. */

static void deque_init(deque_t *d) { d->head = 0U; d->count = 0U; }

bool deque_push_back(deque_t *d, uint8_t v)
{
    size_t tail;
    if (d->count == sizeof d->buf) return false;
    tail = (d->head + d->count) % sizeof d->buf;
    d->buf[tail] = v;
    ++d->count;
    return true;
}

bool deque_push_front(deque_t *d, uint8_t v)
{
    if (d->count == sizeof d->buf) return false;
    d->head = (d->head + sizeof d->buf - 1U) % sizeof d->buf;
    d->buf[d->head] = v;
    ++d->count;
    return true;
}

bool deque_pop_front(deque_t *d, uint8_t *out)
{
    if ((out == NULL) || (d->count == 0U)) return false;
    *out = d->buf[d->head];
    d->head = (d->head + 1U) % sizeof d->buf;
    --d->count;
    return true;
}

bool deque_pop_back(deque_t *d, uint8_t *out)
{
    if ((out == NULL) || (d->count == 0U)) return false;
    *out = d->buf[(d->head + d->count - 1U) % sizeof d->buf];
    --d->count;
    return true;
}

int main(void)
{
    deque_t d;
    uint8_t v = 0U;
    deque_init(&d);
    assert(deque_push_back(&d, 1U) && deque_push_back(&d, 2U));
    assert(deque_push_front(&d, 0U));                  /* 0 1 2 */
    assert(deque_pop_back(&d, &v) && v == 2U);
    assert(deque_pop_front(&d, &v) && v == 0U);
    assert(deque_pop_front(&d, &v) && v == 1U);
    assert(!deque_pop_front(&d, &v));                  /* underflow */
    return 0;
}

• head + count addresses the back without storing a second index.
• push_front wraps by adding capacity-1 instead of subtracting: no unsigned underflow.
• count==capacity is the full test; head==tail would sacrifice a slot.

Cases the tests must cover

• back/front push then both pop directions
• underflow rejected
• wraparound after several cycles
• full rejected
• count field disambiguates full from empty

How it gets written wrong

• Decrementing an unsigned head at 0 wraps to SIZE_MAX; add (cap-1) instead.
• Modulo works for any capacity; mask tricks need power-of-two.

Medium - Stack with O(1) Minimum

Tracking the minimum of the currently active set - the lowest deadline among running timers, the coldest reading in an active window - with pushes and pops.

Support push, pop, and current-minimum in O(1) using two caller-provided arrays. Report overflow and underflow; minimum on an empty stack must be rejected.

O(1) minimum stack

push/pop/min are O(1) and report false on overflow/underflow. min on an empty stack is rejected, never a sentinel.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { int32_t data[8]; int32_t mins[8]; size_t top; } minstack_t;

static void ms_init(minstack_t *s) { s->top = 0U; }

bool minstack_push(minstack_t *s, int32_t v)
{
    if (s->top == 8U) return false;
    s->data[s->top] = v;
    s->mins[s->top] = ((s->top == 0U) || (v < s->mins[s->top - 1U]))
        ? v : s->mins[s->top - 1U];
    ++s->top;
    return true;
}

bool minstack_pop(minstack_t *s, int32_t *out)
{
    if ((out == NULL) || (s->top == 0U)) return false;
    --s->top;
    *out = s->data[s->top];
    return true;
}

bool minstack_min(const minstack_t *s, int32_t *out)
{
    if ((out == NULL) || (s->top == 0U)) return false;
    *out = s->mins[s->top - 1U];
    return true;
}

int main(void)
{
    minstack_t s;
    int32_t v = 0;
    ms_init(&s);
    assert(!minstack_min(&s, &v));                     /* empty: rejected */
    assert(minstack_push(&s, 5) && minstack_push(&s, 3) && minstack_push(&s, 7));
    assert(minstack_min(&s, &v) && v == 3);
    assert(minstack_pop(&s, &v) && v == 7);
    assert(minstack_min(&s, &v) && v == 3);
    assert(minstack_pop(&s, &v) && v == 3);
    assert(minstack_min(&s, &v) && v == 5);            /* min restored after pop */
    return 0;
}

• mins[i] is the minimum of data[0..i]: one extra word per slot buys O(1) minimum.
• Pop needs no fix-up because both stacks shrink together.
• The empty-min case is an API error, not a magic INT32_MAX return.

Cases the tests must cover

• min falls then restores after pops
• empty min rejected
• overflow at capacity rejected
• duplicate minima survive one pop
• pop returns the removed value

How it gets written wrong

• Tracking one 'current min' variable cannot restore the previous min on pop.
• A sentinel minimum collides with a legitimate INT32_MAX sample.

Medium - FIFO from Two Fixed Stacks

Building FIFO behaviour where only LIFO storage is convenient - reversing a captured trace for playback, or adapting a stack-shaped scratch region into a queue.

Build a FIFO queue from two fixed-capacity LIFO stacks, moving elements only when the output stack is empty. Keep push O(1) and pop amortized O(1).

FIFO from two fixed stacks

push is O(1); pop is O(1) amortized because elements move to the output stack only when it is empty. Both report false on full/empty.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t in[4]; uint8_t out[4]; size_t in_n; size_t out_n; } tsqueue_t;

static void tq_init(tsqueue_t *q) { q->in_n = 0U; q->out_n = 0U; }

bool tsqueue_push(tsqueue_t *q, uint8_t v)
{
    if (q->in_n == sizeof q->in) return false;
    q->in[q->in_n++] = v;
    return true;
}

bool tsqueue_pop(tsqueue_t *q, uint8_t *out_v)
{
    if (out_v == NULL) return false;
    if (q->out_n == 0U) {
        while (q->in_n > 0U) q->out[q->out_n++] = q->in[--q->in_n];   /* one move per element */
    }
    if (q->out_n == 0U) return false;
    *out_v = q->out[--q->out_n];
    return true;
}

int main(void)
{
    tsqueue_t q;
    uint8_t v = 0U;
    tq_init(&q);
    assert(tsqueue_push(&q, 1U) && tsqueue_push(&q, 2U));
    assert(tsqueue_pop(&q, &v) && v == 1U);
    assert(tsqueue_push(&q, 3U));
    assert(tsqueue_pop(&q, &v) && v == 2U);
    assert(tsqueue_pop(&q, &v) && v == 3U);
    assert(!tsqueue_pop(&q, &v));
    return 0;
}

• Reversing the in-stack into the out-stack puts the oldest element on top.
• Each element is moved at most once: n pops cost O(n) total, i.e. amortized O(1).
• Full capacity is in+out split; a mixed state can report full with physical room left.

Cases the tests must cover

• FIFO order preserved across interleaved push/pop
• empty pop rejected
• elements migrate lazily, not per push
• full input stack rejects push
• migration happens only when output stack empties

How it gets written wrong

• Moving elements on every push makes push O(n).
• A single pop after k pushes is O(k): amortized, not worst-case.

More in Embedded DSA

• Sorting Under ConstraintLearn nine sorting algorithms with record-by-record traces: insertion, selection, bubble, Shell, merge, quick, heap, counting and radix. Compare stability, temporary storage and input-dependent work, then solve the C11 firmware exercises.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasFollow packet storage through allocation, use and release. Compare fixed-block pools, linked lists and arenas, including exhaustion, lifetime and allocation trade-offs.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Heaps & SchedulingInsert and remove deadlines in a binary min-heap, then study scheduling and wrapping tick counters. Heaps and timer wheels are different timer-management structures.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.