</>EmbeddedInterview

How do you implement a stack and a queue with fixed arrays?

EasyData Structures & Algorithms

Short answer: A stack (LIFO) needs an array and a top index: push writes a[top++], pop reads a[--top], checking for full (top == N) and empty (top == 0). A queue (FIFO) is a ring buffer with head and tail indices. Both give O(1) operations with no dynamic allocation, which is why firmware prefers them to linked implementations.

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

#define N 4
typedef struct { int a[N]; int top; } istack_t;

bool push(istack_t *s, int v) { if (s->top == N) return false; s->a[s->top++] = v; return true; }
bool pop(istack_t *s, int *v) { if (s->top == 0) return false; *v = s->a[--s->top]; return true; }

typedef struct { int a[N]; unsigned head, tail, count; } iqueue_t;

bool enqueue(iqueue_t *q, int v)
{
    if (q->count == N) return false;
    q->a[q->tail] = v; q->tail = (q->tail + 1) % N; q->count++;
    return true;
}
bool dequeue(iqueue_t *q, int *v)
{
    if (q->count == 0) return false;
    *v = q->a[q->head]; q->head = (q->head + 1) % N; q->count--;
    return true;
}

int main(void)
{
    istack_t s = {0}; iqueue_t q = {0}; int v;
    for (int i = 1; i <= 3; i++) { push(&s, i); enqueue(&q, i); }
    while (pop(&s, &v)) printf("%d ", v);         /* 3 2 1 */
    printf("| ");
    while (dequeue(&q, &v)) printf("%d ", v);     /* 1 2 3 */
    printf("\n");
    return 0;
}

Embedded uses: stacks for expression evaluation, undo, depth-first traversal without recursion, and parsing nested structures; queues for events, commands and data between ISRs and tasks.

Variants: a deque (double-ended queue, push/pop at both ends with a ring buffer), a priority queue (heap, next question), and a stack that returns its minimum in O(1) (keep a second stack of minimums; see the coding topics).

Error handling: always report overflow and underflow (return codes, counters) rather than silently overwriting; in safety-critical code, overflow is often treated as a fault.