Embedded DSA Interview Questions: Stack and Queue (Q124–Q153)

Part 4 of the seven-part Embedded Firmware DSA Interview Guide — 30 questions answered at full depth for embedded, firmware and senior technical roles.

This is the highest value pair of sections in the whole bank for a firmware screen. Stack and queue interview questions for embedded roles are really questions about ring buffers, ISR to task handoff, and stack overflow detection, and that is how all thirty answers below are framed.

---

Stack and queue interview questions for embedded roles

• Q124. How do you implement a stack, and what does it cost?
• Q125. Why is an array stack the right choice in firmware?
• Q126. How do you implement a stack with a linked list?
• Q127. How do you check whether brackets are balanced?
• Q128. How does the shunting yard algorithm convert infix to postfix?
• Q129. How do you evaluate a postfix expression?
• Q130. What is stack overflow, and which meaning is being asked?
• Q131. What is stack underflow and how do you guard against it?
• Q132. Why must the function call stack be a stack?
• Q133. How do you evaluate an arbitrary expression end to end?
• Q134. How do you implement browser back and forward with stacks?
• Q135. How do you implement undo and redo?
• Q136. How do you write depth first search without recursion?
• Q137. How do you detect stack overflow on an embedded target?
• Q138. How do you monitor task stack usage in an RTOS?
• Q139. How do you implement a queue, and why is the naive version wrong?
• Q140. How does a circular queue tell full from empty?
• Q141. What is a deque and how do you implement one?
• Q142. What is a priority queue and how is it implemented?
• Q143. How do you implement a queue with a linked list?
• Q144. How do you implement a queue with an array?
• Q145. How do you build a queue from two stacks?
• Q146. Why use a circular queue instead of a linear array queue?
• Q147. How do you implement a lock free ring buffer in embedded C?
• Q148. How do you solve the producer consumer problem?
• Q149. How do you hand data from an ISR to a task?
• Q150. How do DMA descriptor chains work?
• Q151. When can a queue be made lock free?
• Q152. What does an RTOS queue give you over your own ring buffer?
• Q153. Where are queues used in embedded systems?

---

Questions 124 to 153, explained fully. This begins Sections 7 to 14, the second half of the bank.

For an embedded interview this is the highest value pair of sections in the whole bank. Ring buffers, ISR to task handoff, and stack overflow detection all live here, and they come up in almost every firmware screen.

---

Section 7: Stack

---

Q124. How do you implement a stack, and what does it cost?

Say this out loud A last in first out container with three operations: push adds to the top, pop removes from the top, and peek reads the top without removing it. All three are O(1). The only design decision is whether the storage is an array or a linked list, and in firmware it is almost always an array.

The full explanation

The defining property is the access rule, not the storage. Only the most recently added element is reachable. Everything else is buried until the things above it are removed.

push(10)   push(20)   push(30)      pop() -> 30
                       +----+        +----+
            +----+     | 30 | <-top  | 20 | <-top
 +----+     | 20 |     | 20 |        | 10 |
 | 10 |     | 10 |     | 10 |        +----+
 +----+     +----+     +----+

The minimal interface

typedef struct {
    int    data[STACK_MAX];
    int    top;                 /* index of the next free slot, so empty is 0 */
} stack_t;

void stack_init(stack_t *s)      { s->top = 0; }
bool stack_empty(const stack_t *s){ return s->top == 0; }
bool stack_full(const stack_t *s) { return s->top >= STACK_MAX; }

bool stack_push(stack_t *s, int v) {
    if (stack_full(s)) return false;
    s->data[s->top++] = v;
    return true;
}

bool stack_pop(stack_t *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[--s->top];
    return true;
}

bool stack_peek(const stack_t *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[s->top - 1];
    return true;
}

The top convention matters. Two choices exist and mixing them causes off by one bugs:

The first is cleaner because top doubles as the element count and never goes negative, so it works with an unsigned type. Pick one, state it in a comment, and never mix them.

Returning bool rather than void. In firmware, push must be able to fail, because the capacity is fixed. A void push that silently drops data, or worse writes past the end, is not acceptable. Making the caller handle the failure is the whole point.

---

Q125. Why is an array stack the right choice in firmware?

That is Q124. What is worth adding is the analysis of why this is the right choice for firmware.

The only real limitation is the fixed capacity, and in firmware that is a feature rather than a limitation. You size it for the worst case, prove the worst case at design time, and the build fails on your desk if it does not fit.

The growable version, for completeness

if (s->top == s->cap) {
    int *tmp = realloc(s->data, s->cap * 2 * sizeof(int));
    if (!tmp) return false;
    s->data = tmp;
    s->cap *= 2;
}

Amortized O(1) per push by the doubling argument from Q55. Mention it, then say you would not use it on a target.

---

Q126. How do you implement a stack with a linked list?

typedef struct snode {
    int           data;
    struct snode *next;
} snode_t;

typedef struct { snode_t *top; } lstack_t;

bool lstack_push(lstack_t *s, int v) {
    snode_t *n = malloc(sizeof *n);
    if (!n) return false;
    n->data = v;
    n->next = s->top;
    s->top = n;
    return true;
}

bool lstack_pop(lstack_t *s, int *out) {
    if (s->top == NULL) return false;
    snode_t *n = s->top;
    *out = n->data;
    s->top = n->next;
    free(n);
    return true;
}

Push is insert at head, pop is delete at head. Both O(1). A stack is the one data structure where the linked list version needs no traversal at all, which is why it is the textbook example.

The comparison, and the answer for an embedded role

The linked list version calls malloc on every single push. On a target that is disqualifying by itself. If you genuinely need unbounded depth, use a pool allocator (Q121) so the allocation is O(1) and bounded, and then you have a linked stack with array-like determinism.

---

Q127. How do you check whether brackets are balanced?

Say this out loud Push every opening bracket. On a closing bracket, pop and check that it matches the expected partner. The string is balanced if every closer matched and the stack is empty at the end.

static char partner(char c) {
    switch (c) {
        case ')': return '(';
        case ']': return '[';
        case '}': return '{';
        default:  return 0;
    }
}

bool is_balanced(const char *s) {
    char stack[MAX];
    int top = 0;

    for (; *s; s++) {
        if (*s == '(' || *s == '[' || *s == '{') {
            if (top >= MAX) return false;            /* too deeply nested */
            stack[top++] = *s;
        } else if (*s == ')' || *s == ']' || *s == '}') {
            if (top == 0) return false;              /* closer with nothing open */
            if (stack[--top] != partner(*s)) return false;   /* wrong type */
        }
    }
    return top == 0;                                 /* nothing left open */
}

The three failure conditions, which is what the question tests

Candidates usually catch the first and forget one of the other two. Check all three explicitly.

Why a stack is the correct structure. Nesting is inherently last in first out. The bracket you must close next is always the most recently opened one. Any problem with that property is a stack problem, and recognising the property is more valuable than the code.

Why it matters in firmware. JSON and XML config parsing, expression evaluation in a command shell, and detecting truncated or corrupted protocol frames. The depth limit is a real security control: unbounded nesting depth in a parser is a standard denial of service technique, and here the fixed array gives you that limit for free.

---

Q128. How does the shunting yard algorithm convert infix to postfix?

Say this out loud The shunting yard algorithm. Scan left to right. Operands go straight to the output. Operators are pushed, but before pushing, pop any operator on the stack with higher or equal precedence, respecting associativity. An opening parenthesis is pushed and a closing one pops until the matching open is found.

Why bother. Infix needs precedence rules and parentheses to be unambiguous. Postfix needs neither: it is evaluated by a single left to right scan with one stack, which is exactly why compilers, calculators, and virtual machines use it.

The algorithm

1. Operand: append to output.
2. (: push.
3. ): pop to output until ( is on top, then discard the (.
4. Operator: while the stack top is an operator with precedence greater than this one, or equal precedence and this operator is left associative, pop it to output. Then push this operator.
5. End of input: pop everything remaining to output.

Precedence table

Full trace of a + b * c - d

Result: a b c * + d -. Reading it back: multiply b and c, add to a, subtract d. Correct.

Second trace, showing parentheses and right associativity: (a + b) ^ c ^ d

The right associativity of ^ is why 2^3^2 is 512 and not 64. That single rule is the detail that separates a correct implementation from an almost correct one.

static int prec(char op) {
    switch (op) {
        case '^': return 3;
        case '*': case '/': case '%': return 2;
        case '+': case '-': return 1;
        default: return 0;
    }
}
static bool right_assoc(char op) { return op == '^'; }

int infix_to_postfix(const char *in, char *out, int outmax) {
    char stack[MAX];
    int top = 0, o = 0;

    for (; *in; in++) {
        char c = *in;
        if (isspace((unsigned char)c)) continue;

        if (isalnum((unsigned char)c)) {
            if (o >= outmax - 1) return -1;
            out[o++] = c;
        } else if (c == '(') {
            stack[top++] = c;
        } else if (c == ')') {
            while (top > 0 && stack[top - 1] != '(') out[o++] = stack[--top];
            if (top == 0) return -1;                 /* unmatched ) */
            top--;                                   /* discard the ( */
        } else {
            while (top > 0 && stack[top - 1] != '(' &&
                   (prec(stack[top - 1]) > prec(c) ||
                    (prec(stack[top - 1]) == prec(c) && !right_assoc(c)))) {
                out[o++] = stack[--top];
            }
            stack[top++] = c;
        }
    }
    while (top > 0) {
        if (stack[top - 1] == '(') return -1;        /* unmatched ( */
        out[o++] = stack[--top];
    }
    out[o] = '\0';
    return o;
}

---

Q129. How do you evaluate a postfix expression?

Say this out loud Single left to right scan with one stack. Push operands. On an operator, pop two operands, apply, push the result. At the end exactly one value remains and that is the answer. No precedence rules and no parentheses are needed, which is the entire point of postfix.

bool eval_postfix(const char *expr, long *result) {
    long stack[MAX];
    int top = 0;

    for (const char *p = expr; *p; p++) {
        if (isspace((unsigned char)*p)) continue;

        if (isdigit((unsigned char)*p)) {
            long v = 0;
            while (isdigit((unsigned char)*p)) v = v * 10 + (*p++ - '0');
            p--;                                    /* the for loop will advance */
            if (top >= MAX) return false;
            stack[top++] = v;
        } else {
            if (top < 2) return false;              /* malformed expression */
            long b = stack[--top];                  /* SECOND operand pops FIRST */
            long a = stack[--top];
            long r;
            switch (*p) {
                case '+': r = a + b; break;
                case '-': r = a - b; break;
                case '*': r = a * b; break;
                case '/': if (b == 0) return false; r = a / b; break;
                default: return false;
            }
            stack[top++] = r;
        }
    }
    if (top != 1) return false;
    *result = stack[0];
    return true;
}

The operand order is the trap. For a b -, the correct result is a - b, but b is on top of the stack and pops first. Writing long a = stack[--top]; long b = stack[--top]; silently computes b - a, which is right for + and * and wrong for - and /. This is the single most common bug on this question and it survives testing if you only test with addition.

Trace of 5 3 + 8 2 - *, which is (5+3) * (8-2) = 48:

Validation as a bonus. top < 2 when an operator arrives means too few operands. top != 1 at the end means too many. Those two checks make the function a validator as well as an evaluator, and mentioning that is a nice touch.

---

Q130. What is stack overflow, and which meaning is being asked?

Say this out loud Two distinct meanings, and I would clarify which one is being asked. In the data structure sense, it is pushing onto a full fixed capacity stack, and the fix is to return an error. In the system sense, it is the call stack growing past its allocated region, which on a microcontroller without an MPU silently corrupts adjacent memory rather than faulting.

Data structure overflow

bool stack_push(stack_t *s, int v) {
    if (s->top >= STACK_MAX) return false;      /* detect and report */
    s->data[s->top++] = v;
    return true;
}

The failure to write this check is a buffer overflow, and it writes past the end of the struct into whatever follows.

System stack overflow

Causes, in order of frequency:

1. Recursion whose depth follows the input (Q90 and Q91)
2. Large local arrays or structs, especially inside a task with a small stack
3. A task stack sized by guesswork rather than by measurement
4. Deep or nested interrupts, since the ISR frame lands on whichever stack was active
5. printf or snprintf with floating point, which can consume several hundred bytes of stack in one call

That last one surprises people. A newlib printf with %f can use 500 bytes or more. Adding one debug print inside a task with 256 bytes of headroom is enough to overflow it, which is why the bug appears only when you instrument the code.

The detection techniques are Q137 and Q138.

---

Q131. What is stack underflow and how do you guard against it?

Popping or peeking an empty stack.

bool stack_pop(stack_t *s, int *out) {
    if (s->top == 0) return false;              /* the check that must exist */
    *out = s->data[--s->top];
    return true;
}

Without the check, --s->top makes top equal to -1, and s->data[-1] reads the memory immediately before the array, which is whatever struct member or variable the linker placed there. Then the next push writes to data[-1] and corrupts it.

If top is unsigned it is worse. 0 - 1 wraps to UINT32_MAX, so data[4294967295] is an access billions of bytes away, which usually does fault but with an address that tells you nothing useful.

The general principle worth stating: every operation on a bounded structure has a precondition, and in firmware the precondition is checked and reported rather than assumed. In a hot path where the caller has already validated, an assert in the debug build plus a comment documenting the precondition is the alternative, since assert compiles away in release.

---

Q132. Why must the function call stack be a stack?

Covered mechanically in Q3 of the first file. What matters here is that it is a stack in the data structure sense, and why that is the only structure that could work.

Function calls nest strictly. If A calls B and B calls C, then C must return before B, and B before A. That is last in first out by definition, so the frames can be stored contiguously with a single pointer marking the top, and allocation is a subtraction.

What each frame holds

+-------------------------+
| return address (LR)     |  where to resume in the caller
+-------------------------+
| saved callee registers  |  r4 to r11 as needed
+-------------------------+
| local variables         |
+-------------------------+
| spilled temporaries     |
+-------------------------+
| outgoing args 5 and up  |
+-------------------------+

Cortex M specifics worth knowing

• Two stack pointers exist. MSP is used by handler mode and by the main program before an RTOS starts. PSP is used by threads under an RTOS. This separation means an ISR does not consume the task’s stack for its own frame, which is what lets task stacks be small.
• On exception entry the hardware automatically pushes r0, r1, r2, r3, r12, LR, PC, xPSR onto the active stack before the handler runs. Eight words, 32 bytes, and more if the FPU context is stacked. That is why worst case task stack analysis must include interrupt overhead.
• A context switch in an RTOS is exactly this: push the remaining registers onto the outgoing task’s stack, save its SP into the task control block, load the incoming task’s SP, and pop. The stack is the saved context.

That last sentence is a good thing to say. It reframes the call stack from a language detail into the mechanism the scheduler is built on.

---

Q133. How do you evaluate an arbitrary expression end to end?

The full pipeline, which ties Q127 to Q129 together:

"3 + 4 * 2"
    |  tokenize
    v
[3] [+] [4] [*] [2]
    |  shunting yard (Q128)
    v
3 4 2 * +
    |  postfix evaluation (Q129)
    v
11

The direct alternative: two stacks, one pass

You can evaluate infix without converting, using an operand stack and an operator stack.

/* on an operand: push to the operand stack
   on an operator: while the operator stack top has >= precedence, apply it, then push
   on ')' : apply until '(' is popped
   at end : apply everything remaining */

apply means pop two operands and one operator, compute, push the result. It is the same algorithm as shunting yard with evaluation substituted for output.

Which to use

Why it matters in firmware. A debug shell that accepts set gain = base * 1.5 + offset, a rule engine on an IoT node, or a configuration file with computed values. And the two stack pattern generalises: an operand stack plus an operator stack is the skeleton of every simple interpreter.

---

Q134. How do you implement browser back and forward with stacks?

Say this out loud Two stacks. Back holds the pages behind you and forward holds the pages ahead. Navigating to a new page pushes the current one onto back and clears forward. Pressing back pops from back, pushes the current onto forward, and makes the popped page current.

typedef struct {
    page_t back[MAX];    int nback;
    page_t fwd[MAX];     int nfwd;
    page_t current;
} history_t;

void visit(history_t *h, page_t p) {
    h->back[h->nback++] = h->current;
    h->current = p;
    h->nfwd = 0;                     /* a new branch invalidates the forward history */
}

bool go_back(history_t *h) {
    if (h->nback == 0) return false;
    h->fwd[h->nfwd++] = h->current;
    h->current = h->back[--h->nback];
    return true;
}

bool go_forward(history_t *h) {
    if (h->nfwd == 0) return false;
    h->back[h->nback++] = h->current;
    h->current = h->fwd[--h->nfwd];
    return true;
}

The detail that is the actual question. Clearing the forward stack on a new visit. If you go back three pages and then click a link, the pages you had gone forward past are unreachable and must be discarded. Every real browser behaves this way, and candidates who forget it produce a history that lets you go forward into a branch you abandoned.

The firmware equivalent is a menu system on a device with a display. Back navigation through a nested menu tree is exactly this, and the fixed size array means a deeply nested menu simply cannot exhaust memory.

---

Q135. How do you implement undo and redo?

Say this out loud A stack of operations rather than a stack of states. Each entry stores enough information to reverse the action. Undo pops, applies the inverse, and pushes onto a redo stack. Any new action clears redo, for the same reason as browser forward.

typedef enum { OP_SET, OP_INSERT, OP_DELETE } op_kind_t;

typedef struct {
    op_kind_t kind;
    int       index;
    int       old_value;      /* what it was, so undo can restore it */
    int       new_value;      /* what it became, so redo can reapply it */
} operation_t;

Storing the delta rather than the whole state is the design point. Snapshotting the entire document on every keystroke is O(size) memory per operation. Storing “character X was inserted at position Y” is O(1) per operation, and the undo is “delete the character at Y”.

The bounded history requirement. In firmware the undo stack is a fixed size ring buffer. When it fills, the oldest entry is discarded, not the newest, so you keep the most recent N operations undoable. That is a circular buffer with a stack-like access pattern, which is a nice thing to point out because it shows you are combining structures rather than picking one from a list.

Command pattern. In C++ this is a vector of objects each exposing execute() and undo(). In C it is a struct with a tag and a union, plus a switch. Mentioning that the design is the same and only the dispatch differs is a good answer to a follow up about how you would make it extensible.

---

Q136. How do you write depth first search without recursion?

Say this out loud Replace the implicit recursion stack with an explicit one. Push the start node, then loop: pop a node, visit it if unvisited, and push its neighbours. This gives depth first order with a stack whose size you control and whose overflow you can detect.

void dfs_iterative(graph_t *g, int start) {
    int  stack[MAX_NODES];
    int  top = 0;
    bool visited[MAX_NODES] = {false};

    stack[top++] = start;

    while (top > 0) {
        int n = stack[--top];
        if (visited[n]) continue;         /* may be pushed more than once */
        visited[n] = true;
        visit(n);

        for (int i = degree(g, n) - 1; i >= 0; i--) {    /* reverse order */
            int nb = neighbour(g, n, i);
            if (!visited[nb]) {
                if (top >= MAX_NODES) { log_error("dfs stack full"); return; }
                stack[top++] = nb;
            }
        }
    }
}

Two details worth stating.

Neighbours are pushed in reverse order so that the first neighbour is popped first, matching the order the recursive version would visit them. If order does not matter, push forward and say so.

The visited check happens on pop, not only on push, because a node can be pushed by several different neighbours before it is ever popped. Checking only at push time still works if you also mark visited at push time, but then the traversal order changes subtly. Knowing that these two variants differ is a good sign.

Why explicit beats recursive in firmware. The stack is a named array in .bss whose size appears in the linker map, and overflow is a checkable condition that returns an error instead of corrupting a neighbouring task. This is the concrete payoff of the recursion-to-iteration transformation from Q93.

Stack versus queue is the only difference between DFS and BFS. Swap the stack for a queue and the identical code performs breadth first search. Saying this out loud is worth more than either implementation.

---

Q137. How do you detect stack overflow on an embedded target?

Say this out loud Five techniques, and I would use several together. Pattern fill with high water mark measurement, an MPU guard region below each stack, the ARMv8-M hardware stack limit registers where available, RTOS overflow hooks, and compile time analysis with -fstack-usage.

1. Pattern fill and high water mark. The everyday tool.

Fill the whole stack with a known value at task creation. Later, scan from the low end to find how much has been touched.

#define FILL 0xA5A5A5A5u

void stack_paint(uint32_t *base, size_t words) {
    for (size_t i = 0; i < words; i++) base[i] = FILL;
}

size_t stack_unused_words(const uint32_t *base, size_t words) {
    size_t unused = 0;
    while (unused < words && base[unused] == FILL) unused++;
    return unused;                                  /* words never touched */
}

Report this for every task periodically. The number only ever decreases. If any task drops below roughly 20 percent headroom, increase it. This is the measurement that replaces guessing, and “I measure the high water mark rather than guessing stack sizes” is a strong sentence in an interview.

The limitation to acknowledge: it is a sampling technique. A deep call chain that overflows and then returns can be missed if it happened not to write to the untouched region, though in practice it almost always does.

2. MPU guard region. The rigorous one.

Place a small region, typically 32 bytes, immediately below each task stack, configured as no access. Any write into it raises a MemManage fault at the exact faulting instruction, with the address in MMFAR.

  higher address
  +----------------------+
  |  Task A stack        |   grows downward
  +----------------------+
  |  GUARD, no access    |   <-- MPU region, faults on any access
  +----------------------+
  |  Task B stack        |
  +----------------------+

This converts a silent corruption into an immediate, diagnosable fault. FreeRTOS with MPU support and Zephyr both do this automatically when configured.

3. ARMv8-M stack limit registers. MSPLIM and PSPLIM are hardware bounds checked on every stack pointer update. Available on Cortex M23, M33, M55 and later. Zero cost, no MPU region consumed, and the fault is immediate. If the part supports it, use it.

4. RTOS hooks. FreeRTOS offers two methods:

Both call vApplicationStackOverflowHook, where you should log the task name and reset rather than trying to continue. Enable method 2 in development and consider leaving it on in production, since the cost is a handful of comparisons per switch.

5. Compile time analysis. -fstack-usage emits a .su file with the frame size of every function. Combined with a call graph, this gives a provable worst case, provided there is no recursion and no indirect calls. Recursion and function pointers are exactly what break the proof, which is a large part of why safety standards restrict both.

The sentence that ties it together: static analysis gives you a bound before the product ships, the high water mark tells you whether reality matches that bound, and the MPU or stack limit register catches the case where it does not.

---

Q138. How do you monitor task stack usage in an RTOS?

Practical specifics, since Q137 covered mechanism.

FreeRTOS

UBaseType_t words_remaining = uxTaskGetStackHighWaterMark(task_handle);

Returns the minimum number of words ever free, so multiply by 4 for bytes. Passing NULL queries the calling task. Requires INCLUDE_uxTaskGetStackHighWaterMark.

void vApplicationStackOverflowHook(TaskHandle_t xTask, char *pcTaskName) {
    /* Do NOT call printf here. The stack is already corrupt. */
    log_to_noinit_buffer(pcTaskName);
    NVIC_SystemReset();
}

The rule inside an overflow hook: do as little as possible. The stack that would carry your diagnostic call is the one that just overflowed. Write a task name and a magic value into a .noinit RAM region that the startup code does not clear, then reset. On the next boot, check for the magic value and report it. That pattern, a persistent crash record surviving reset, is worth describing because it is what real products do.

Sizing tasks in practice

1. Start generous, for example 512 words.
2. Run the worst case workload, including error paths, the deepest menu, and any printf with floats.
3. Read the high water mark.
4. Set the size to the peak usage plus 30 to 50 percent margin.
5. Re measure after any significant change, and put the check in CI if you can.

Do not forget the interrupt contribution. On Cortex M under an RTOS, tasks run on PSP and interrupts run on MSP, so an ISR does not eat task stack for its own frame. But the hardware-stacked eight words on exception entry go on the active stack, which is the task’s. Add that, plus FPU context if lazy stacking is enabled, plus the deepest nested interrupt chain, to every task’s requirement.

The number worth quoting: basic exception entry stacks 32 bytes. With FPU context it is 104 bytes. Nested interrupts multiply it. A task sized with only 40 bytes of headroom is not safe even if its own code never uses them.

---

Section 8: Queue

---

Q139. How do you implement a queue, and why is the naive version wrong?

Say this out loud First in first out. Enqueue adds at the rear, dequeue removes from the front. The naive array version where dequeue shifts everything down is O(n) and wrong. The correct array version is circular, with separate head and tail indices, giving O(1) for both.

The naive version and why it fails

/* WRONG */
int dequeue(queue_t *q) {
    int v = q->data[0];
    for (int i = 0; i < q->count - 1; i++) q->data[i] = q->data[i + 1];   /* O(n) */
    q->count--;
    return v;
}

Every dequeue shifts the whole queue. For a UART receive queue draining 115200 bits per second that is thousands of pointless memory moves per second.

The linear index version and why it also fails

Keep separate front and rear indices and never shift. Now dequeue is O(1), but both indices only ever increase, so the queue crawls toward the end of the array and reports full while the front of the array sits empty. That wasted space is exactly the problem the circular queue solves.

after several operations:
[ . . . . D E F . . . ]
          ^     ^
        front  rear      <- indices 0 to 3 are unusable

So the real answer is the circular queue, Q140.

---

Q140. How does a circular queue tell full from empty?

Say this out loud The indices wrap around to the start of the array using modulo, so freed space at the front is reused. Both enqueue and dequeue are O(1) with no data movement. The one design decision is how to distinguish full from empty, since both give head == tail.

#define QSIZE 16            /* power of two, so the wrap is a mask */

typedef struct {
    int      data[QSIZE];
    uint32_t head;          /* index to read from */
    uint32_t tail;          /* index to write to */
    uint32_t count;         /* elements currently held */
} cqueue_t;

bool cq_enqueue(cqueue_t *q, int v) {
    if (q->count == QSIZE) return false;
    q->data[q->tail] = v;
    q->tail = (q->tail + 1) & (QSIZE - 1);
    q->count++;
    return true;
}

bool cq_dequeue(cqueue_t *q, int *out) {
    if (q->count == 0) return false;
    *out = q->data[q->head];
    q->head = (q->head + 1) & (QSIZE - 1);
    q->count--;
    return true;
}

Why & (QSIZE - 1) and not % QSIZE. For a power of two size they are identical in result, but the mask is a single cycle AND while the modulo is a division. Cortex M0 and M0+ have no hardware divider, so % becomes a library call costing tens of cycles. Inside a UART interrupt running at high baud, that difference is real. Always size ring buffers as powers of two and mask.

Full trace with QSIZE = 4

Slot 0 was reused after A left. That reuse is the entire point of the structure.

The full versus empty problem, three solutions

For a lock free single producer single consumer ring, the count version is wrong, because count is modified by both the ISR and the task, which is a read modify write race. Use the wasted slot version or free running indices, where the producer only writes head and the consumer only writes tail. This is the single most important design point in the whole section, and it comes back in Q147, Q149, and Q151.

---

Q141. What is a deque and how do you implement one?

Say this out loud Insertion and removal at both ends, all in O(1). Implemented as a circular array where the head index can move backward as well as forward, or as a doubly linked list.

bool dq_push_front(deque_t *d, int v) {
    if (d->count == DSIZE) return false;
    d->head = (d->head - 1) & (DSIZE - 1);      /* move BACKWARD, and wrap */
    d->data[d->head] = v;
    d->count++;
    return true;
}

bool dq_pop_back(deque_t *d, int *out) {
    if (d->count == 0) return false;
    d->tail = (d->tail - 1) & (DSIZE - 1);
    *out = d->data[d->tail];
    d->count--;
    return true;
}

The (index - 1) & mask handles the wrap correctly even at index 0, because on an unsigned type 0 - 1 becomes UINT32_MAX, and masking that with DSIZE - 1 yields DSIZE - 1, which is the last slot. That is exactly right, and it only works because the type is unsigned. On a signed type it is undefined behaviour. This is a good detail to point out.

A deque is a superset: restrict it to push back and pop front and it is a queue, restrict it to push back and pop back and it is a stack. Saying that shows structural understanding.

Firmware uses. A sliding window filter where you push new samples at one end and drop old ones from the other. A work stealing scheduler, where a worker takes from its own front and thieves take from the back, minimising contention.

---

Q142. What is a priority queue and how is it implemented?

Say this out loud Elements come out in priority order rather than arrival order. The standard implementation is a binary heap, giving O(log n) insert and O(log n) extract with O(1) peek at the highest priority. For a small fixed number of priority levels, an array of FIFOs indexed by priority is better, because every operation becomes O(1).

The three implementations and when each wins

The bucket approach, which is the embedded answer

#define NPRIO 8

typedef struct {
    fifo_t   level[NPRIO];
    uint32_t ready_mask;            /* bit i set means level i is non empty */
} prio_queue_t;

void pq_push(prio_queue_t *q, int prio, item_t it) {
    fifo_push(&q->level[prio], it);
    q->ready_mask |= (1u << prio);
}

bool pq_pop(prio_queue_t *q, item_t *out) {
    if (q->ready_mask == 0) return false;
    int top = 31 - __builtin_clz(q->ready_mask);   /* highest set bit, ONE instruction */
    fifo_pop(&q->level[top], out);
    if (fifo_empty(&q->level[top])) q->ready_mask &= ~(1u << top);
    return true;
}

__builtin_clz maps to the ARM CLZ instruction, count leading zeros, which executes in one cycle. So finding the highest priority ready task is constant time regardless of how many priority levels exist. This is exactly how FreeRTOS finds the next task to run when configUSE_PORT_OPTIMISED_TASK_SELECTION is enabled, and mentioning it is a strong signal for an RTOS role.

Why an RTOS does not use a heap. A heap is O(log n) and, more importantly, its execution time varies with the contents. A scheduler must be O(1) and deterministic, because the scheduling decision happens inside a critical section on every tick. Trading generality for determinism is the recurring theme of embedded data structure choice, and saying that explicitly is the answer they are looking for.

---

Q143. How do you implement a queue with a linked list?

typedef struct qnode { int data; struct qnode *next; } qnode_t;
typedef struct { qnode_t *front, *rear; } lqueue_t;

bool lq_enqueue(lqueue_t *q, int v) {
    qnode_t *n = malloc(sizeof *n);
    if (!n) return false;
    n->data = v; n->next = NULL;

    if (q->rear) q->rear->next = n;
    else         q->front = n;            /* was empty */
    q->rear = n;
    return true;
}

bool lq_dequeue(lqueue_t *q, int *out) {
    if (q->front == NULL) return false;
    qnode_t *n = q->front;
    *out = n->data;
    q->front = n->next;
    if (q->front == NULL) q->rear = NULL;   /* THE detail: queue became empty */
    free(n);
    return true;
}

The bug everyone writes. Forgetting to clear rear when the last element is dequeued. front becomes NULL, but rear still points at the freed node. The next enqueue does q->rear->next = n, writing through a dangling pointer into freed memory. It usually appears to work, because the allocator has not reused the block yet, and it corrupts the heap.

Both operations are O(1) with the rear pointer, which is why the queue is the second structure, after the stack, where a linked list needs no traversal.

The firmware objection is the same as Q126: a malloc and free on every single element. Use a pool allocator or, better, a ring buffer.

---

Q144. How do you implement a queue with an array?

Covered in Q139 and Q140. The summary to give:

• Naive with shifting: O(n) dequeue, unacceptable
• Linear indices without wrap: O(1) but wastes the front of the array and falsely reports full
• Circular with masked indices: O(1) both ways, no waste, no data movement. This is the answer

The array version beats the linked list version in firmware on every axis: no allocation, zero per element overhead, contiguous memory that can be handed to DMA, and a capacity known at build time.

---

Q145. How do you build a queue from two stacks?

Say this out loud An in stack and an out stack. Enqueue pushes onto in. Dequeue pops from out, but if out is empty, first move everything from in to out, which reverses the order and turns LIFO into FIFO. Each element is moved at most twice, so the amortized cost is O(1) even though a single dequeue can be O(n).

typedef struct { stack_t in, out; } q2s_t;

bool q2s_enqueue(q2s_t *q, int v) {
    return stack_push(&q->in, v);
}

bool q2s_dequeue(q2s_t *q, int *out) {
    if (stack_empty(&q->out)) {
        int v;
        while (stack_pop(&q->in, &v)) {         /* transfer, reversing the order */
            if (!stack_push(&q->out, v)) return false;
        }
    }
    return stack_pop(&q->out, out);
}

Trace: enqueue 1, 2, 3 then dequeue three times

enqueue 1,2,3:   in = [1,2,3]  (3 on top)      out = []

dequeue: out is empty, transfer.
   pop 3 from in, push to out    out = [3]
   pop 2 from in, push to out    out = [3,2]
   pop 1 from in, push to out    out = [3,2,1]  (1 on top)
   pop from out -> 1             correct, first in first out

dequeue: out is not empty, pop -> 2
dequeue: out is not empty, pop -> 3

The two things being tested

1. Only transfer when out is empty. Transferring on every dequeue destroys the ordering and the complexity. This is the condition candidates get wrong.
2. Amortized analysis. Each element is pushed to in once, popped from in once, pushed to out once, popped from out once. Four operations per element total, so n dequeues cost O(n) overall, which is O(1) each on average, even though one particular dequeue may be O(n).

Is it useful in practice? Almost never, and saying so is fine. It is a reasoning exercise about amortized cost and about building one abstraction from another. The one real caveat for firmware is that the worst case single operation is O(n), so it is unsuitable for anything with a deadline, even though the average is fine.

---

Q146. Why use a circular queue instead of a linear array queue?

Against the linear array queue:

• No wasted space. Slots freed at the front are reused, so a size N array actually holds N elements over its lifetime rather than N total insertions.
• No data movement. Dequeue is an index update, not a shift, so it is O(1) instead of O(n).
• Fixed memory forever. No allocation, no growth, no fragmentation.
• Deterministic timing. Every operation is the same handful of instructions, which is what an ISR needs.
• Natural overflow policy. When full you can reject the new data or overwrite the oldest, and both are one line. For a debug log the overwrite policy is right, for received packets the reject policy is right.
• Cache and DMA friendly. Contiguous memory. A DMA controller can be pointed at a region of the buffer directly.

The comparison to make against a linked list queue: no per element allocation, no pointer overhead, and bounded execution time. Those three points are the reason essentially every serial driver in the world uses a ring buffer.

---

Q147. How do you implement a lock free ring buffer in embedded C?

Say this out loud It is a circular queue used for producer consumer handoff, most often from an ISR to a task. With exactly one producer and one consumer, and one writer per index, it needs no lock at all, only a memory barrier between writing the data and publishing the index.

#define RB_SIZE 256                      /* power of two, mandatory */

typedef struct {
    uint8_t  buf[RB_SIZE];
    volatile uint32_t head;              /* written ONLY by the producer */
    volatile uint32_t tail;              /* written ONLY by the consumer */
} ringbuf_t;

/* producer side, called from the ISR */
bool rb_put(ringbuf_t *r, uint8_t v) {
    uint32_t h = r->head;
    uint32_t next = (h + 1) & (RB_SIZE - 1);
    if (next == r->tail) return false;              /* full: one slot sacrificed */
    r->buf[h] = v;
    __DMB();                                        /* data lands BEFORE the index moves */
    r->head = next;
    return true;
}

/* consumer side, called from a task */
bool rb_get(ringbuf_t *r, uint8_t *out) {
    uint32_t t = r->tail;
    if (t == r->head) return false;                 /* empty */
    *out = r->buf[t];
    __DMB();                                        /* read the data BEFORE freeing the slot */
    r->tail = (t + 1) & (RB_SIZE - 1);
    return true;
}

Why this is safe with no critical section, stated precisely

• The producer writes only head and reads only tail. The consumer writes only tail and reads only head. Neither index has two writers, so there is no read modify write race.
• On a 32 bit core, an aligned 32 bit load or store is a single indivisible bus transaction, so neither side can ever observe a half updated index.
• The producer writes the data first, then the index. The consumer sees a new index only after the data exists. The barrier is what guarantees the compiler and the core do not reorder those two.

Why volatile alone is not enough. From the first file, Q15: volatile guarantees the accesses happen and are not reordered relative to each other, but it does not stop the write buffer or the core from making them visible out of order to another observer, and on a multi core or DMA capable system that matters. __DMB() is a data memory barrier and it is the correct tool. On a single core Cortex M with no cache the barrier is often unnecessary in practice, but writing it costs one cycle and makes the code correct by construction rather than by accident.

Why a count field would break it. count++ on the producer side and count-- on the consumer side are both read modify write on shared state. That is a race, and it corrupts the count. The wasted slot approach exists precisely so that each variable has one writer.

Sizing. Capacity must cover the worst case burst that can arrive before the consumer runs. For a UART at 115200 baud, that is about 11520 bytes per second, so if the draining task can be delayed 10 ms by a higher priority task, you need at least 116 bytes plus margin. Being able to do that arithmetic on the spot is a very strong answer.

The overwrite variant. For a debug trace where losing old data is preferable to losing new data, advance tail when full instead of returning false. Note that this makes the consumer’s index writable by the producer, so it is no longer lock free and needs a critical section.

---

Q148. How do you solve the producer consumer problem?

Say this out loud One or more producers generate data, one or more consumers process it, and a bounded buffer sits between them. The problems to solve are what happens when the buffer is full, when it is empty, and how the two sides synchronise without busy waiting.

The four cases and their handling

In an ISR the producer can never block. That constraint decides the design: the ISR does a non blocking put and returns immediately, and if the buffer is full it increments a dropped counter and continues. Blocking in an ISR would either deadlock or blow interrupt latency.

The RTOS version

/* ISR side */
void UART_IRQHandler(void) {
    uint8_t b = UART->DR;
    BaseType_t woken = pdFALSE;
    xQueueSendFromISR(rx_queue, &b, &woken);        /* never blocks */
    portYIELD_FROM_ISR(woken);                      /* switch immediately if a task woke */
}

/* task side */
void rx_task(void *arg) {
    uint8_t b;
    for (;;) {
        if (xQueueReceive(rx_queue, &b, portMAX_DELAY) == pdTRUE) {   /* blocks, no polling */
            process(b);
        }
    }
}

portYIELD_FROM_ISR is the detail worth pointing out. Without it, a task unblocked by the ISR does not run until the next tick, which can add a full tick period of latency. With it, the context switch happens on exit from the interrupt.

The counting semaphore formulation, which is the textbook answer:

semaphore empty = N     (slots available)
semaphore full  = 0     (items available)
mutex     lock          (only needed for multiple producers or consumers)

producer:  wait(empty);  lock;  put();  unlock;  signal(full)
consumer:  wait(full);   lock;  get();  unlock;  signal(empty)

The classic deadlock: acquiring the mutex before the counting semaphore. A producer then holds the lock while blocking on a full buffer, so the consumer can never acquire the lock to drain it. The order shown above, count first then mutex, avoids it. Being able to name that deadlock is a good senior signal.

---

Q149. How do you hand data from an ISR to a task?

Say this out loud The ISR must do the minimum: read the hardware, push into a queue, signal a task, and return. Everything else happens at task priority. This bounds interrupt latency, which is the number that determines whether the whole system meets its deadlines.

The rules for a queue used from an ISR

1. Never block. No mutex, no blocking send, no waiting for anything.
2. Never allocate. malloc is not ISR safe in most implementations and has unbounded time regardless.
3. Use the FromISR variants. xQueueSendFromISR, xSemaphoreGiveFromISR. The normal versions can block and will assert or corrupt state if called from handler mode.
4. Keep it short. Bytes, small structs, or pointers to preallocated buffers. Never copy a large payload inside an interrupt.
5. Handle full without blocking. Increment a dropped counter and return. Log it later from a task.

typedef struct {
    uint32_t timestamp;
    uint16_t adc_value;
    uint8_t  channel;
} sample_t;

static volatile uint32_t dropped_count;

void ADC_IRQHandler(void) {
    sample_t s = { .timestamp = get_tick(),
                   .adc_value = ADC->DR,
                   .channel   = current_channel };

    if (!rb_put_struct(&sample_ring, &s)) {
        dropped_count++;                   /* never block, never log from here */
    }
}

Why not just process it in the ISR. Interrupt latency for every other interrupt in the system is bounded by the longest time any handler runs with interrupts masked. If your ADC handler does a filter computation taking 200 microseconds, every other peripheral waits. Deferring keeps handlers in the microsecond range.

The variant worth mentioning: pass a pointer, not the data. For large payloads such as a received network frame, the ISR takes a buffer from a pool (Q121), points the DMA at it, and enqueues the pointer. Zero copy, constant time, and the task frees the buffer back to the pool when finished. That design is what a real network driver does and describing it unprompted is a strong differentiator.

---

Q150. How do DMA descriptor chains work?

Say this out loud A DMA descriptor chain is a linked list the hardware walks by itself. Each descriptor holds a source, destination, length, control flags, and the address of the next descriptor, so the controller performs a sequence of transfers with no CPU involvement between them.

typedef struct dma_desc {
    uint32_t         src;
    uint32_t         dst;
    uint32_t         len;
    uint32_t         ctrl;
    struct dma_desc *next;      /* NULL ends the chain */
} __attribute__((aligned(16))) dma_desc_t;

The alignment attribute is required. DMA controllers commonly demand descriptors aligned to 16 or 32 bytes, and an unaligned descriptor is either rejected or read incorrectly. That is Q4 from the first file applied to hardware.

The two common queue patterns

Ping pong, or double buffering. Two buffers. DMA fills A while the CPU processes B, then they swap on the transfer complete interrupt. Continuous capture with no gaps and no copying.

Circular DMA. The controller is configured in circular mode over a single ring buffer and never stops. Half transfer and full transfer interrupts tell the CPU which half is safe to read. This is the standard way to receive continuous UART or I2S data with almost zero CPU cost.

/* circular DMA: the head is the hardware's write index, derived from the counter */
uint32_t dma_head(void) {
    return RB_SIZE - DMA->NDTR;      /* NDTR counts DOWN as the DMA writes */
}

void poll_uart_rx(void) {
    uint32_t head = dma_head();
    while (tail != head) {
        process(rx_buf[tail]);
        tail = (tail + 1) & (RB_SIZE - 1);
    }
}

The producer here is the DMA hardware itself and the consumer is your task. It is a ring buffer where the producer index lives in a peripheral register rather than in RAM.

The cache trap, which is the senior detail. On a Cortex M7 or an A series core with a data cache:

• Before reading a buffer the DMA has written, you must invalidate the cache lines, or you read stale data that was cached before the transfer.
• After writing a buffer the DMA will read, you must clean the cache lines, or the data is still sitting in cache and the DMA reads stale RAM.
• The buffer must be aligned to the cache line size, typically 32 bytes, and padded to a multiple of it. Otherwise an invalidate discards a neighbouring variable that shared the line.

__attribute__((aligned(32))) static uint8_t dma_buf[256];   /* 256 is already a multiple of 32 */

SCB_InvalidateDCache_by_Addr((uint32_t *)dma_buf, sizeof dma_buf);   /* before reading */

Bringing this up unprompted signals real DMA experience, because it is the bug that everyone hits exactly once and never forgets.

---

Q151. When can a queue be made lock free?

Covered in depth in Q122 of the previous file, including the ABA problem and the SPSC ring. The queue specific summary:

The MPSC enqueue with CAS

bool mpsc_put(ringbuf_t *r, uint8_t v) {
    uint32_t h, next;
    do {
        h = __LDREXW(&r->head);
        next = (h + 1) & (RB_SIZE - 1);
        if (next == r->tail) return false;          /* full */
    } while (__STREXW(next, &r->head) != 0);        /* retry if another writer won */

    r->buf[h] = v;                                  /* WARNING: see below */
    __DMB();
    return true;
}

And that code has a real bug worth discussing, because it illustrates why this is hard: the slot is written after the index was published, so a consumer could read the slot before the producer fills it. Fixing it properly needs a second index, a commit counter, so a slot is only visible once its data is complete. Being able to spot that in your own code during an interview is far more impressive than producing a flawless snippet.

LDREX and STREX are the ARM load exclusive and store exclusive instructions. STREX fails if anything else touched the address since the LDREX, which is how compare and swap is built on ARM.

The judgement to state: on a single core Cortex M, disabling interrupts for the three instructions of a ring buffer update costs about 5 cycles and is provably correct. A lock free implementation costs a retry loop and considerable design risk. Reach for it only on a multi core part, or when profiling shows the critical section is genuinely the bottleneck.

---

Q152. What does an RTOS queue give you over your own ring buffer?

Say this out loud An RTOS queue is a thread safe FIFO that copies data by value and integrates with the scheduler, so a task waiting on an empty queue is blocked rather than polling and consumes no CPU. It combines a ring buffer with a wait list of blocked tasks.

What it actually contains

struct QueueDefinition {
    int8_t     *pcHead;             /* start of the storage area */
    int8_t     *pcWriteTo;          /* next write position */
    int8_t     *pcReadFrom;
    List_t      xTasksWaitingToSend;      /* blocked because the queue is full */
    List_t      xTasksWaitingToReceive;   /* blocked because it is empty */
    UBaseType_t uxMessagesWaiting;
    UBaseType_t uxLength;
    UBaseType_t uxItemSize;
};

Note the two List_t members. Those are the intrusive doubly linked lists from Q97 and Q120. An RTOS queue is a ring buffer plus two linked lists, which is a nice illustration that real systems are compositions of these primitives rather than one clever structure.

The blocking mechanism

1. Task calls xQueueReceive with a timeout, the queue is empty.
2. The kernel removes the task from the ready list and inserts it into xTasksWaitingToReceive, and into the delayed list if the timeout is finite.
3. The scheduler runs something else. The waiting task uses zero CPU.
4. Another task or an ISR sends. The kernel takes the highest priority task from xTasksWaitingToReceive, moves it back to the ready list, and requests a context switch if it now outranks the running task.

All of those list operations are O(1), which is why they can happen inside a critical section without hurting interrupt latency.

Copy by value, which is the design decision to discuss. FreeRTOS queues copy uxItemSize bytes in and out. That means the sender can reuse its buffer immediately and there is no ownership question, but it costs a memcpy per operation. For large payloads the idiom is to queue a pointer to a pool buffer instead, so the item size is 4 bytes and the copy is trivial. Ownership then transfers with the pointer, which you must document.

Cost. An RTOS queue send is on the order of a few hundred cycles once you count the critical section, the copy, the list operations, and a possible context switch. A raw ring buffer put is under ten. For a UART interrupt at high baud, use the raw ring and signal the task with a semaphore only once per burst rather than once per byte. That optimisation, batching the notification, is a very good thing to volunteer.

---

Q153. Where are queues used in embedded systems?

The unifying principle to state: a queue is what you use whenever a producer and a consumer run at different rates or at different priorities, and the buffer absorbs the difference. The size of the buffer is exactly the size of the worst case burst you must survive. If you can compute that number for a specific scenario during the interview, that arithmetic is often what they are really testing.

---

Quick revision sheet, questions 124 to 153

---

---

All seven parts of the guide

• Part 1: C Fundamentals, Pointers and Memory — Q1 to Q35
• Part 2: Arrays and Strings — Q36 to Q73
• Part 3: Recursion and Linked Lists — Q74 to Q123
• Part 4: Stack and Queue — Q124 to Q153 (you are here)
• Part 5: Trees and Binary Search Trees — Q154 to Q188
• Part 6: Heap and Sorting — Q189 to Q218
• Part 7: Hashing and Complexity — Q219 to Q248

Start here: The Embedded Firmware DSA Interview Guide, all 248 questions indexed in one place. Architecture round: Firmware Architecture Interview Questions: 100 Q&A.

---

Work with us

Kalapi Infotech builds firmware for connected embedded products — architecture and BSP work, RTOS and bare-metal development, secure boot and OTA infrastructure. If you are hiring for these roles, or building a product that needs them, we would be glad to talk.

Get in touch with our firmware team →