SyntaxPilot
Courses/C Coding Questions/Lesson 28
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

C Coding Questions · Lesson 28 of 30

Stack and queue questions

stack with an array (overflow/underflow)balanced bracketscircular queue

These are the notes for C Coding Questions, episode 28, placement practice for people who finished the SyntaxPilot C course. Three classics: a stack built on an array (with overflow and underflow), checking balanced brackets with a stack, and a circular queue.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was compiled with gcc -Wall -O2 -Wno-unused-result main.c -o main -lm (gcc 13.3, glibc, Linux x86-64), the SyntaxPilot compiler's C command with warnings on, and every output below is real. The fixed programs were also run under valgrind: no errors.

Real-life pictures

In real life In C
a pile of plates at a wedding buffet: the last plate put on is the first one taken stack, last in, first out (LIFO): push on top, pop from the top
lunch boxes packed one inside another: the box opened last is closed first balanced brackets: the latest ( must be closed first
the giant wheel at a mela: people get on and off in order, and a seat that comes round empty is used again circular queue, first in, first out (FIFO): the index wraps back to 0

Two words to know before we start:

  • A stack is a list where you only add and remove at one end, the top. Push adds on top, pop removes the top item and gives it back, peek looks at the top without removing it. The order is LIFO: last in, first out.
  • A queue is a list where you add at one end, the rear, and remove at the other, the front. Enqueue adds, dequeue removes. The order is FIFO: first in, first out.

Q1: A stack on an array (overflow and underflow)

Problem. Build a stack of int on an array of size MAX (5 here) with push, pop and peek.

Think out loud.

  • struct Stack { int a[MAX]; int top; }; where top is the index of the top item and top == -1 means empty.
  • Push: top moves up, then the item is stored at a[top]. Pop: read a[top], then top moves down.
  • Edge cases: overflow (push onto a full stack, top == MAX - 1), underflow (pop from an empty stack, top == -1), and items that are themselves -1.

The obvious attempt: no checks

#include <stdio.h>
#define MAX 5

struct Stack {
    int a[MAX];
    int top;                    /* index of the top item, -1 = empty */
};

void push(struct Stack *s, int x) {
    s->top++;
    s->a[s->top] = x;           /* no check */
}

int pop(struct Stack *s) {
    return s->a[s->top--];      /* no check */
}

int main() {
    struct Stack s = { .top = -1 };
    printf("push:");
    for (int i = 1; i <= 6; i++) {
        push(&s, i * 10);
        printf(" %d", i * 10);
    }
    printf(" -> top = %d\npop:", s.top);
    while (s.top >= 0) printf(" %d", pop(&s));
    printf(" %d\n", pop(&s));                /* one pop too many */
    return 0;
}

Real compiler output (the program still compiles and runs):

In function ‘push’,
    inlined from ‘main’ at main.c:22:9:
main.c:11:18: warning: iteration 5 invokes undefined behavior [-Waggressive-loop-optimizations]
   11 |     s->a[s->top] = x;           /* no check */
      |     ~~~~~~~~~~~~~^~~
main.c: In function ‘main’:
main.c:21:23: note: within this loop
   21 |     for (int i = 1; i <= 6; i++) {
      |                     ~~^~~~
In function ‘pop’,
    inlined from ‘main’ at main.c:27:5:
main.c:15:16: warning: array subscript -1 is below array bounds of ‘int[5]’ [-Warray-bounds=]
   15 |     return s->a[s->top--];      /* no check */
      |            ~~~~^~~~~~~~~~
main.c: In function ‘main’:
main.c:5:9: note: while referencing ‘a’
    5 |     int a[MAX];
      |         ^

Real output (the last number is garbage and changes on every run: 21982, 21975, 22018 in three runs):

push: 10 20 30 40 50 60 -> top = 5
pop: 60 50 40 30 20 10 21982

Why it failed

  • The 6th push sets top = 5 and writes a[5], but the array is a[0]..a[4]. Writing outside an array is undefined behaviour (UB): the C standard gives no rule for what happens. Here it seemed to work (six items in five slots), which is the most dangerous outcome: the same code can overwrite another variable or crash on another day, another compiler or another optimisation level.
  • The 7th pop happens with top == -1, so it reads a[-1]: underflow, another UB, and we got a garbage number.
  • gcc saw both at compile time because main uses fixed numbers. With input-driven pushes there is often no warning at all, so the checks must be in the code.

The fix: check full and empty, return success, pass the item out

#include <stdio.h>
#define MAX 5

struct Stack {
    int a[MAX];
    int top;                    /* index of the top item, -1 = empty */
};

int push(struct Stack *s, int x) {
    if (s->top == MAX - 1) return 0;      /* full: overflow */
    s->a[++s->top] = x;
    return 1;
}

int pop(struct Stack *s, int *out) {
    if (s->top == -1) return 0;           /* empty: underflow */
    *out = s->a[s->top--];
    return 1;
}

int peek(const struct Stack *s, int *out) {
    if (s->top == -1) return 0;
    *out = s->a[s->top];
    return 1;
}

int main() {
    struct Stack s = { .top = -1 };
    int x;
    for (int i = 1; i <= 6; i++) {
        if (push(&s, i * 10)) printf("push %d -> top = %d\n", i * 10, s.top);
        else                  printf("push %d -> overflow: stack is full\n", i * 10);
    }
    if (peek(&s, &x)) printf("peek -> %d\n", x);
    while (pop(&s, &x)) printf("pop -> %d\n", x);
    if (!pop(&s, &x)) printf("pop -> underflow: stack is empty\n");
    push(&s, -1);                          /* -1 is a real item now */
    if (pop(&s, &x)) printf("pop -> %d (a real -1, not an error)\n", x);
    return 0;
}

Real output (no warnings):

push 10 -> top = 0
push 20 -> top = 1
push 30 -> top = 2
push 40 -> top = 3
push 50 -> top = 4
push 60 -> overflow: stack is full
peek -> 50
pop -> 50
pop -> 40
pop -> 30
pop -> 20
pop -> 10
pop -> underflow: stack is empty
pop -> -1 (a real -1, not an error)

Why int pop(struct Stack *s, int *out) and not int pop(struct Stack *s) returning -1 for "empty"? Because -1 can be a real item. A value that means two things (a sentinel value) is a trap. Returning a success flag and writing the item through a pointer (an out-parameter) keeps the two apart.

Complexity. push, pop and peek are each O(1): a fixed amount of work no matter how many items there are. Space: O(MAX) for the array.

Q2: Balanced brackets

Problem. Given a line, are its brackets (), [], {} balanced? Each opener must be closed by its own kind, in the reverse order it was opened; other characters are ignored.

Think out loud.

Input Answer Why
{[()]} balanced closed in reverse order
([)] NOT wrong order
(] NOT wrong kind
(( NOT left open
)) NOT a closer with nothing open
(empty line) balanced nothing to close
a(b[c]d)e balanced letters are ignored

Lines are read with fgets, and line[strcspn(line, "\n")] = '\0'; removes the newline fgets keeps.

The obvious attempt: one counter

#include <stdio.h>
#include <string.h>

int balanced(const char *s) {
    int open = 0;
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '[' || s[i] == '{') open++;
        if (s[i] == ')' || s[i] == ']' || s[i] == '}') open--;
        if (open < 0) return 0;            /* a closer with nothing open */
    }
    return open == 0;
}

int main() {
    char line[200];
    while (fgets(line, sizeof line, stdin) != NULL) {
        line[strcspn(line, "\n")] = '\0';  /* drop the newline */
        printf("%-12s %s\n", line[0] ? line : "(empty)", balanced(line) ? "balanced" : "NOT balanced");
    }
    return 0;
}

Input:

{[()]}
([)]
(]

Real output:

{[()]}       balanced
([)]         balanced
(]           balanced

Why it failed

The counter goes 1, 2, 1, 0 for ([)]. It knows how many brackets are open, but not which kind, and not in which order. (] also counts 1, 0.

The fix: a stack of open brackets

Push every opener. For every closer: if the stack is empty, it's not balanced; otherwise pop the latest opener and check that it is the same kind. At the end, balanced only if the stack is empty.

#include <stdio.h>
#include <string.h>
#define MAX 200

int balanced(const char *s) {
    char st[MAX];                          /* a stack of open brackets */
    int top = -1;
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == MAX - 1) return 0;  /* too deep: overflow */
            st[++top] = c;                 /* push */
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return 0;       /* nothing to close */
            char o = st[top--];            /* pop the latest opener */
            if ((c == ')' && o != '(') || (c == ']' && o != '[') ||
                (c == '}' && o != '{')) return 0;   /* wrong kind */
        }                                  /* other characters: skip */
    }
    return top == -1;                      /* nothing left open */
}

int main() {
    char line[MAX];
    while (fgets(line, sizeof line, stdin) != NULL) {
        line[strcspn(line, "\n")] = '\0';  /* drop the newline */
        printf("%-12s %s\n", line[0] ? line : "(empty)", balanced(line) ? "balanced" : "NOT balanced");
    }
    return 0;
}

Input:

{[()]}
([)]
(]
((
))

a(b[c]d)e

Real output:

{[()]}       balanced
([)]         NOT balanced
(]           NOT balanced
((           NOT balanced
))           NOT balanced
(empty)      balanced
a(b[c]d)e    balanced

Complexity. O(n) time for a line of n characters (each character once). O(n) space in the worst case (a line of only openers).

Q3: A queue on an array, then a circular queue

Problem. A queue of tokens (like a bank counter) in an array of 5 seats. Tokens 1 to 5 join, all 5 are served, then token 6 joins: it must fit, because the queue is empty.

Think out loud.

  • front = where the next token is served from; rear = where the next token joins.
  • Edge cases: a full queue, an empty queue, joining after some tokens were served.

The obvious attempt: front++ and rear++

#include <stdio.h>
#define MAX 5

struct Queue {
    int a[MAX];
    int front, rear;            /* take from front, add at rear */
};

int enqueue(struct Queue *q, int x) {
    if (q->rear == MAX) return 0;          /* full? */
    q->a[q->rear++] = x;
    return 1;
}

int dequeue(struct Queue *q, int *out) {
    if (q->front == q->rear) return 0;     /* empty */
    *out = q->a[q->front++];
    return 1;
}

int main() {
    struct Queue q = { .front = 0, .rear = 0 };
    int x;
    for (int t = 1; t <= 5; t++) enqueue(&q, t);       /* tokens 1..5 */
    for (int k = 0; k < 5; k++)
        if (dequeue(&q, &x)) printf("served token %d\n", x);
    printf("queue is empty: %s\n", q.front == q.rear ? "yes" : "no");
    if (enqueue(&q, 6)) printf("token 6 joined\n");
    else                printf("token 6: queue is FULL\n");
    return 0;
}

Real output:

served token 1
served token 2
served token 3
served token 4
served token 5
queue is empty: yes
token 6: queue is FULL

Why it failed

front and rear only ever move forward. After 5 joins, rear == 5 == MAX, so the queue says "full" for ever, even after every seat was freed. The freed seats at the front are never used again.

The fix: wrap the index with % and keep a count

The modulo operator % gives the remainder after division: (3 + 2) % 5 == 0, so an index that reaches the end wraps back to 0, like a seat on the giant wheel. We also keep a count, because in a circular queue "front == rear" happens both when it is empty and when it is full.

#include <stdio.h>
#define MAX 5

struct Queue {
    int a[MAX];
    int front;                  /* index of the first item */
    int count;                  /* how many items are in the queue */
};

int enqueue(struct Queue *q, int x) {
    if (q->count == MAX) return 0;             /* really full */
    int rear = (q->front + q->count) % MAX;    /* wrap around */
    q->a[rear] = x;
    q->count++;
    return 1;
}

int dequeue(struct Queue *q, int *out) {
    if (q->count == 0) return 0;               /* empty: underflow */
    *out = q->a[q->front];
    q->front = (q->front + 1) % MAX;           /* wrap around */
    q->count--;
    return 1;
}

int main() {
    struct Queue q = { .front = 0, .count = 0 };
    int x;
    for (int t = 1; t <= 5; t++) enqueue(&q, t);       /* tokens 1..5 */
    if (!enqueue(&q, 99)) printf("token 99: queue is full (5 waiting)\n");
    for (int k = 0; k < 3; k++)
        if (dequeue(&q, &x)) printf("served token %d\n", x);
    for (int t = 6; t <= 8; t++)
        if (enqueue(&q, t)) printf("token %d joined (front = %d)\n", t, q.front);
    while (dequeue(&q, &x)) printf("served token %d\n", x);
    if (!dequeue(&q, &x)) printf("queue is empty: nothing to serve\n");
    return 0;
}

Real output:

token 99: queue is full (5 waiting)
served token 1
served token 2
served token 3
token 6 joined (front = 3)
token 7 joined (front = 3)
token 8 joined (front = 3)
served token 4
served token 5
served token 6
served token 7
served token 8
queue is empty: nothing to serve

Tokens 6, 7 and 8 went into seats 0, 1 and 2 ((3 + 2) % 5 = 0, (3 + 3) % 5 = 1, (3 + 4) % 5 = 2), and they were still served in order.

Complexity. enqueue and dequeue are O(1). Space O(MAX), and no seat is wasted.

Another common way: keep front and rear and leave one seat always empty, so "full" is (rear + 1) % MAX == front and "empty" is front == rear. It holds MAX - 1 items. The count version above uses every seat.

Complexity summary

Question Time Extra space
Stack push / pop / peek O(1) each O(MAX)
Balanced brackets with one counter O(n), but wrong O(1)
Balanced brackets with a stack O(n) O(n)
Plain array queue O(1) each, but wastes seats O(MAX)
Circular queue O(1) each O(MAX)

Common mistakes (and the real results)

Mistake What happens Why Fix
push with no full check warning: iteration 5 invokes undefined behavior · writes a[5] a[5] is outside a[0..4] if (s->top == MAX - 1) return 0;
pop with no empty check warning: array subscript -1 is below array bounds · garbage reads a[-1] if (s->top == -1) return 0;
return -1; for "empty" a real -1 item looks like an error one value, two meanings return 1/0, item through int *out
one counter for brackets ([)] and (] say balanced no kind, no order a stack of openers
forgetting the final check (( says balanced openers left on the stack return top == -1;
rear++ until MAX an empty queue says FULL the front seats are never reused (i + 1) % MAX
front == rear means empty (circular, no count) a full queue looks empty the same test for two cases keep a count (or leave one seat empty)

Your turn: a min stack (solution)

Problem. A stack with push, pop and get_min() (the smallest item in the stack), all three in O(1). Push 5, 3, 7 → min 3; pop → min 3; pop → min 5.

Idea. A second array m where m[i] is the minimum of a[0..i]. Each push stores min(x, m[top - 1]); the current minimum is always m[top].

#include <stdio.h>
#define MAX 100

struct MinStack {
    int a[MAX];                 /* the items */
    int m[MAX];                 /* m[i] = the minimum of a[0..i] */
    int top;
};

int push(struct MinStack *s, int x) {
    if (s->top == MAX - 1) return 0;                 /* overflow */
    s->top++;
    s->a[s->top] = x;
    s->m[s->top] = (s->top == 0 || x < s->m[s->top - 1]) ? x : s->m[s->top - 1];
    return 1;
}

int pop(struct MinStack *s, int *out) {
    if (s->top == -1) return 0;                      /* underflow */
    *out = s->a[s->top--];
    return 1;
}

int get_min(const struct MinStack *s, int *out) {
    if (s->top == -1) return 0;
    *out = s->m[s->top];                             /* O(1): it's on top */
    return 1;
}

int main() {
    struct MinStack s = { .top = -1 };
    int x;
    push(&s, 5); push(&s, 3); push(&s, 7);
    if (get_min(&s, &x)) printf("min = %d\n", x);    /* 3 */
    pop(&s, &x);
    if (get_min(&s, &x)) printf("min = %d\n", x);    /* 3 */
    pop(&s, &x);
    if (get_min(&s, &x)) printf("min = %d\n", x);    /* 5 */
    pop(&s, &x);
    if (!get_min(&s, &x)) printf("empty: no min\n");
    return 0;
}

Real output:

min = 3
min = 3
min = 5
empty: no min

O(1) for every operation, O(MAX) extra space for m.

Practice questions (with solutions)

1. Reverse a string with a stack

Push every character, then pop them all.

#include <stdio.h>
#include <string.h>
#define MAX 200

int main() {
    char line[MAX], st[MAX];
    int top = -1;
    if (fgets(line, sizeof line, stdin) == NULL) return 0;
    line[strcspn(line, "\n")] = '\0';
    for (int i = 0; line[i] != '\0'; i++) st[++top] = line[i];   /* push all */
    while (top >= 0) putchar(st[top--]);                         /* pop all  */
    putchar('\n');
    return 0;
}

Input SyntaxPilot, real output:

toliPxatnyS

O(n) time, O(n) space.

2. A queue made of two stacks

Enqueue pushes onto in. Dequeue pops from out; when out is empty, first pour everything from in into out (which reverses the order, so the oldest item ends on top).

#include <stdio.h>
#define MAX 100

struct Stack { int a[MAX]; int top; };
int push(struct Stack *s, int x) { if (s->top == MAX - 1) return 0; s->a[++s->top] = x; return 1; }
int pop(struct Stack *s, int *out) { if (s->top == -1) return 0; *out = s->a[s->top--]; return 1; }

struct Queue { struct Stack in, out; };          /* add to in, serve from out */

int enqueue(struct Queue *q, int x) { return push(&q->in, x); }

int dequeue(struct Queue *q, int *x) {
    if (q->out.top == -1) {                      /* out is empty: pour in → out */
        int y;
        while (pop(&q->in, &y)) push(&q->out, y);
    }
    return pop(&q->out, x);                      /* 0 if both are empty */
}

int main() {
    struct Queue q = { .in.top = -1, .out.top = -1 };
    int x;
    enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3);
    dequeue(&q, &x); printf("%d ", x);
    enqueue(&q, 4);
    while (dequeue(&q, &x)) printf("%d ", x);
    printf("\n");
    return 0;
}

Real output:

1 2 3 4 

Each item is moved from in to out once, so a run of n operations costs O(n) in total: amortised O(1) per operation (a single dequeue can be O(n), but on average it's O(1)).

3. Say where the brackets first go wrong

Like Q2, but return the position of the first problem. A stack of positions next to the stack of brackets tells you which opener was left open.

#include <stdio.h>
#include <string.h>
#define MAX 200

/* -1 if balanced, else the 0-based position of the first problem
   (a closer that doesn't match, or the end of the line if something is left open) */
int first_error(const char *s) {
    char st[MAX];
    int pos[MAX], top = -1, i;
    for (i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            if (top == MAX - 1) return i;
            st[++top] = c;
            pos[top] = i;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return i;                       /* nothing open */
            char o = st[top--];
            if ((c == ')' && o != '(') || (c == ']' && o != '[') ||
                (c == '}' && o != '{')) return i;          /* wrong kind */
        }
    }
    return top == -1 ? -1 : pos[top];                      /* left open */
}

int main() {
    char line[MAX];
    while (fgets(line, sizeof line, stdin) != NULL) {
        line[strcspn(line, "\n")] = '\0';
        int e = first_error(line);
        if (e < 0) printf("%-10s balanced\n", line);
        else       printf("%-10s first problem at position %d ('%c')\n", line, e, line[e]);
    }
    return 0;
}

Input:

{[()]}
([)]
(()
)(

Real output:

{[()]}     balanced
([)]       first problem at position 2 (')')
(()        first problem at position 0 ('(')
)(         first problem at position 0 (')')

Quick quiz

/* a stack, pop() prints the item it takes */
push(10);
push(20);
pop();
push(30);
pop();
pop();

What does it print? (A) 10 20 30 (B) 20 30 10 (C) 30 20 10 (D) 20 10 30

Answer

(B) 20 30 10. The first pop takes 20 (on top of 10). 30 goes on top of 10, so the next pop takes 30. The last pop takes 10.

Interview questions

  1. Stack vs queue? Stack: LIFO, one end (top). Queue: FIFO, add at the rear, remove at the front.
  2. What are overflow and underflow? Push on a full stack / pop from an empty one. On an array without checks both are undefined behaviour.
  3. Why not return -1 from pop when the stack is empty? -1 may be a real item: use a success flag and an out-parameter.
  4. Check balanced brackets. A stack of openers; each closer must match the top; the stack must be empty at the end. O(n), O(n).
  5. Why isn't a counter enough? It knows how many are open, not which kind or in what order.
  6. What's wrong with a simple array queue? Freed seats at the front are never reused; it reports full while empty.
  7. How do you tell full from empty in a circular queue? Keep a count, or leave one seat empty.
  8. Implement a queue using two stacks. in/out stacks, pour when out is empty: amortised O(1).
  9. Min stack in O(1). A second stack of running minimums.
  10. Where are stacks used for real? Function calls (the call stack), undo, back button, expression evaluation, bracket checking in compilers.

Glossary

Term Meaning Example
Stack A list where you add and remove only at the top a pile of plates
LIFO Last in, first out the last plate on is taken first
Push Add an item on top of the stack push(&s, 10)
Pop Remove the top item and give it back pop(&s, &x)
Peek Look at the top item without removing it peek(&s, &x)
top The index of the top item; -1 means empty s.top
Overflow Pushing onto a full stack (or queue) the 6th push into 5 slots
Underflow Popping from an empty stack (or queue) pop with top == -1
Undefined behaviour (UB) Code the C standard gives no meaning to; anything can happen writing a[5] in int a[5]
-Waggressive-loop-optimizations, -Warray-bounds gcc warnings about an index outside an array Q1's two warnings
Garbage value Whatever bytes happen to be in memory the 7th pop
Sentinel value A special value that means "no result" returning -1 for empty
Out-parameter A pointer parameter the function writes its result into int *out
Balanced brackets Every opener closed by its own kind, in reverse order {[()]}
Opener / closer ( [ { and ) ] }
fgets Reads one line (keeps the \n) fgets(line, sizeof line, stdin)
strcspn Length of the start of a string with none of the given characters removing the \n
Queue Add at the rear, remove at the front a bank token line
FIFO First in, first out the first token is served first
Enqueue / dequeue Add to a queue / remove from a queue enqueue(&q, 6)
front / rear Where items leave / where items join q.front
Circular queue A queue whose index wraps back to 0 at the end the giant wheel
Modulo % The remainder after division (3 + 2) % 5 == 0
O(1) A fixed amount of work, whatever the size push, pop
O(n) Work that grows with the input size the bracket check
Amortised O(1) O(1) on average over many operations queue with two stacks
valgrind A tool that reports memory errors and leaks every fixed program

Summary

  • Stack (LIFO) on an array: full is top == MAX - 1, empty is top == -1. Check before every push and pop; without checks, a[5] and a[-1] are undefined behaviour, and gcc's warnings are only a lucky hint.
  • Return a success flag and pass the item out through a pointer, so -1 can be a real item.
  • Balanced brackets: a stack of openers, each closer must match the top, empty at the end. O(n), O(n).
  • Queue (FIFO): a plain array queue wastes freed seats. A circular queue wraps with (i + 1) % MAX and keeps a count. O(1) per operation.

Next episode: File handling questions: count the lines, words and characters of a file, copy a file, and append and read records with fprintf and fscanf.