Embedded Interview Questions from a Major Company – Implementing Stack and Queue Containers in C

Today, I had an interview with a major company, where I was asked how to implement stack and queue using C language. I found the questions quite interesting, so I would like to review them here.StackA stack is a last-in-first-out (LIFO) data structure. The implementation idea is to use an array to realize it, maintaining the stack’s capacity and pointer through a structure. When the stack is full, it expands.First, define a structure that includes capacity, top pointer, and data address elements.When creating a stack, manually allocate the size of the capacity, and initialize the top pointer to -1.The operation to push an element into the stack: if the capacity is insufficient, double the capacity. Based on the position pointed to by the top pointer, copy the data to the pointer position and increment the pointer.The pop operation: decrement the top pointer.

typedef void (*FreeFunction)(void*);        // Provides a generic memory release mechanism

typedef struct{    void **data;        // Data    int top;            // Top pointer    int capacity;        // Capacity    FreeFunction freeFn;} Stack;
Stack* stack_create(int capacity, FreeFunction freeFn) {    Stack *stack = (Stack*)malloc(sizeof(Stack));    stack->data = (void**)malloc(sizeof(void*) * capacity);    stack->top = -1;    stack->capacity = capacity;    stack->freeFn = freeFn;    return stack;}
void stack_push(Stack* stack, void* element) {    if (stack->top == stack->capacity - 1) {        stack->capacity *= 2;        stack->data = (void**)realloc(stack->data, sizeof(void*) * stack->capacity);    }    stack->data[++stack->top] = element;}
void* stack_pop(Stack* stack) {    if (stack->top == -1) return NULL;    return stack->data[stack->top--];}
void* stack_top(Stack* stack) {    if (stack->top == -1) return NULL;    return stack->data[stack->top];}
int stack_empty(Stack* stack) {    return stack->top == -1;}
void stack_destroy(Stack* stack) {    if (stack->freeFn) {        for (int i = 0; i <= stack->top; i++) {            stack->freeFn(stack->data[i]);        }    }    free(stack->data);    free(stack);}

QueueA queue is a first-in-first-out (FIFO) data structure. The implementation idea is to use an array, maintaining the head and tail of the queue through a structure. It also expands when the capacity is insufficient.Without further ado, the implementation method is similar to that of the stack, but it requires maintaining an additional pointer.

typedef struct {    void** data;    int front;    int rear;    int capacity;    int size;    FreeFunction freeFn;} Queue;
Queue* queue_create(int capacity, FreeFunction freeFn) {    Queue* queue = (Queue*)malloc(sizeof(Queue));    queue->data = (void**)malloc(sizeof(void*) * capacity);    queue->front = 0;    queue->rear = -1;    queue->size = 0;    queue->capacity = capacity;    queue->freeFn = freeFn;    return queue;}
void queue_enqueue(Queue* queue, void* element) {    if (queue->size == queue->capacity) {        queue->capacity *= 2;        queue->data = (void**)realloc(queue->data, sizeof(void*) * queue->capacity);    }    queue->rear = (queue->rear + 1) % queue->capacity;    queue->data[queue->rear] = element;    queue->size++;}
void* queue_dequeue(Queue* queue) {    if (queue->size == 0) return NULL;    void* element = queue->data[queue->front];    queue->front = (queue->front + 1) % queue->capacity;    queue->size--;    return element;}
void* queue_front(Queue* queue) {    if (queue->size == 0) return NULL;    return queue->data[queue->front];}
int queue_empty(Queue* queue) {    return queue->size == 0;}
void queue_destroy(Queue* queue) {    if (queue->freeFn) {        while (!queue_empty(queue)) {            void* element = queue_dequeue(queue);            queue->freeFn(element);        }    }    free(queue->data);    free(queue);}