C array-based stacks and circular queues
A stack follows last-in, first-out order. In an array it needs a top index: push stores at top and increments it, and pop decrements it and returns the element. Both are O(1). Because the array has a fixed capacity, push must report failure when the stack is full, and pop must report failure when it is empty.
C
#include <stdio.h>
#define CAP 4
typedef struct {
int data[CAP];
int top;
} Stack;
static int push(Stack *s, int value) {
if (s->top == CAP) {
return 0;
}
s->data[s->top++] = value;
return 1;
}
static int pop(Stack *s, int *out) {
if (s->top == 0) {
return 0;
}
*out = s->data[--s->top];
return 1;
}
typedef struct {
int data[CAP];
int head;
int size;
} Queue;
static int enqueue(Queue *q, int value) {
if (q->size == CAP) {
return 0;
}
q->data[(q->head + q->size) % CAP] = value;
q->size++;
return 1;
}
static int dequeue(Queue *q, int *out) {
if (q->size == 0) {
return 0;
}
*out = q->data[q->head];
q->head = (q->head + 1) % CAP;
q->size--;
return 1;
}
int main(void) {
Stack s = {{0}, 0};
for (int v = 10; v <= 40; v += 10) {
push(&s, v);
}
printf("fifth push succeeded: %d\n", push(&s, 50));
int a, b;
pop(&s, &a);
pop(&s, &b);
printf("popped %d then %d\n", a, b);
Queue q = {{0}, 0, 0};
for (int v = 1; v <= 4; v++) {
enqueue(&q, v);
}
int x, y;
dequeue(&q, &x);
dequeue(&q, &y);
enqueue(&q, 5);
enqueue(&q, 6);
printf("dequeued %d and %d, then wrapped around; queue holds:", x, y);
int value;
while (dequeue(&q, &value)) {
printf(" %d", value);
}
printf("\n");
return 0;
}