C array-based stacks and circular queues

Build a fixed-capacity stack and a queue that wraps around the end of its array.

#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;
}

Output

fifth push succeeded: 0
popped 40 then 30
dequeued 1 and 2, then wrapped around; queue holds: 3 4 5 6

Explanation

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.

A queue follows first-in, first-out order. A naive array queue wastes space as the head moves right. A circular queue reuses the freed slots by wrapping indexes with the modulo operator: the next slot after position i is (i + 1) % capacity. A head index and a size are enough to tell the full state from the empty state.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

3#define CAP 4

5typedef struct {

6 int data[CAP];

7 int top;

8} Stack;

10static int push(Stack *s, int value) {

11 if (s->top == CAP) {

12 return 0;

13 }

14 s->data[s->top++] = value;

15 return 1;

16}

18static int pop(Stack *s, int *out) {

19 if (s->top == 0) {

20 return 0;

21 }

22 *out = s->data[--s->top];

23 return 1;

24}

26typedef struct {

27 int data[CAP];

28 int head;

29 int size;

30} Queue;

32static int enqueue(Queue *q, int value) {

33 if (q->size == CAP) {

34 return 0;

35 }

36 q->data[(q->head + q->size) % CAP] = value;

37 q->size++;

38 return 1;

39}

41static int dequeue(Queue *q, int *out) {

42 if (q->size == 0) {

43 return 0;

44 }

45 *out = q->data[q->head];

46 q->head = (q->head + 1) % CAP;

47 q->size--;

48 return 1;

49}

51int main(void) {

52 Stack s = {{0}, 0};

53 for (int v = 10; v <= 40; v += 10) {

54 push(&s, v);

55 }

56 printf("fifth push succeeded: %d\n", push(&s, 50));

57 int a, b;

58 pop(&s, &a);

59 pop(&s, &b);

60 printf("popped %d then %d\n", a, b);

62 Queue q = {{0}, 0, 0};

63 for (int v = 1; v <= 4; v++) {

64 enqueue(&q, v);

65 }

66 int x, y;

67 dequeue(&q, &x);

68 dequeue(&q, &y);

69 enqueue(&q, 5);

70 enqueue(&q, 6);

71 printf("dequeued %d and %d, then wrapped around; queue holds:", x, y);

72 int value;

73 while (dequeue(&q, &value)) {

74 printf(" %d", value);

75 }

76 printf("\n");

77 return 0;

78}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Store at top and move top up by one.	`—`	—
The array holds 4 elements, so the fifth push fails.	`—`	fifth push succeeded: 0
The last values pushed come out first.	`—`	fifth push succeeded: 0 popped 40 then 30
The new element goes at the slot after the last one, wrapping around the end of the array.	`—`	fifth push succeeded: 0 popped 40 then 30
After two dequeues the slots at the front are free, so 5 and 6 wrap around into them.	`queue data wraps`	fifth push succeeded: 0 popped 40 then 30
The queue still returns items in first-in, first-out order.	`queue data wraps`	fifth push succeeded: 0 popped 40 then 30 dequeued 1 and 2, then wrapped around; queue holds: 3 4 5 6

Cost and common mistakes

push, pop, enqueue, and dequeue are all O(1).

Ignoring the return value of push or enqueue silently loses data when the structure is full.
Using only head and tail indexes makes a full queue look empty. Keeping a size field avoids the ambiguity.
For a growing structure, use malloc and realloc, or a linked list, instead of a fixed capacity.

Try it yourself

What does the stack hold after the two pops?

Reveal answer and reasoning

The values 10 and 20, with 20 on top.

C array-based stacks and circular queues

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading