Stacks & Queues — 10 Examples | Ananta Code Academy

📚 Array-Based Stack — Push, Pop, Peek

Implement LIFO with a fixed array and a top index

Stack Basics

A stack is a Last In, First Out (LIFO) data structure. The last element pushed is the first one popped. The simplest implementation uses a fixed-size array and an integer top that tracks the index of the topmost element. Push increments top then writes. Pop reads then decrements top. Peek reads without changing top. Underflow (popping an empty stack) and overflow (pushing a full stack) must be guarded against.

ex1_array_stack.c

#include <stdio.h>
#define MAX 8

typedef struct {
    int data[MAX];
    int top;          /* index of topmost element; -1 = empty */
} Stack;

void initStack(Stack *s)           { s->top = -1; }
int  isEmpty (Stack *s)            { return s->top == -1; }
int  isFull  (Stack *s)            { return s->top == MAX-1; }

void push(Stack *s, int val) {
    if (isFull(s))  { printf("  Stack overflow!\n");  return; }
    s->data[++s->top] = val;
    printf("  push(%d)  top=%d\n", val, s->top);
}

int pop(Stack *s) {
    if (isEmpty(s)) { printf("  Stack underflow!\n"); return -1; }
    int v = s->data[s->top--];
    printf("  pop()  = %d  top=%d\n", v, s->top);
    return v;
}

int peek(Stack *s) {
    if (isEmpty(s)) return -1;
    return s->data[s->top];
}

void display(Stack *s) {
    printf("  Stack (top→bottom): ");
    for (int i = s->top; i >= 0; i--) printf("[%d] ", s->data[i]);
    printf("\n");
}

int main() {
    Stack s;
    initStack(&s);

    printf("--- Push ---\n");
    push(&s, 10); push(&s, 20); push(&s, 30);
    push(&s, 40); push(&s, 50);

    display(&s);
    printf("  peek = %d\n", peek(&s));

    printf("--- Pop ---\n");
    pop(&s); pop(&s); pop(&s);
    display(&s);
    return 0;
}

output

--- Push ---
  push(10)  top=0
  push(20)  top=1
  push(30)  top=2
  push(40)  top=3
  push(50)  top=4
  Stack (top→bottom): [50] [40] [30] [20] [10]
  peek = 50
--- Pop ---
  pop()  = 50  top=3
  pop()  = 40  top=2
  pop()  = 30  top=1
  Stack (top→bottom): [20] [10]

array stack — top index tracks the active top of the stack

data[0..4]

← top=4 (bold)

push order

1st

2nd

3rd

4th

5th

← LIFO: last in, first out

Stack size rule: initialise top = -1. Push increments first: data[++top] = val. Pop reads first: val = data[top--]. This keeps top pointing at the valid topmost element at all times — never at an empty slot.

example 2

🚌 Array-Based Queue — Enqueue & Dequeue

FIFO with a fixed array, front and rear indices

Queue Basics

A queue is a First In, First Out (FIFO) data structure. Elements enter at the rear and leave from the front — like a ticket line. The simplest implementation uses a fixed array with two indices: front and rear. Enqueue writes at rear then increments. Dequeue reads from front then increments. The downside of this linear array approach — wasted space when front advances — is solved in Example 5 with a circular queue.

ex2_array_queue.c

#include <stdio.h>
#define MAX 8

typedef struct {
    int data[MAX];
    int front, rear;   /* front = dequeue side, rear = enqueue side */
    int size;
} Queue;

void initQueue(Queue *q) { q->front = q->rear = q->size = 0; }
int  qEmpty   (Queue *q) { return q->size == 0; }
int  qFull    (Queue *q) { return q->size == MAX; }

void enqueue(Queue *q, int val) {
    if (qFull(q))  { printf("  Queue full!\n"); return; }
    q->data[q->rear++] = val;
    q->size++;
    printf("  enqueue(%d)  rear=%d  size=%d\n", val, q->rear, q->size);
}

int dequeue(Queue *q) {
    if (qEmpty(q)) { printf("  Queue empty!\n"); return -1; }
    int v = q->data[q->front++];
    q->size--;
    printf("  dequeue() = %d  front=%d  size=%d\n", v, q->front, q->size);
    return v;
}

void qDisplay(Queue *q) {
    printf("  Queue (front→rear): ");
    for (int i = q->front; i < q->rear; i++) printf("[%d] ", q->data[i]);
    printf("\n");
}

int main() {
    Queue q;
    initQueue(&q);

    printf("--- Enqueue ---\n");
    enqueue(&q, 100); enqueue(&q, 200);
    enqueue(&q, 300); enqueue(&q, 400);
    qDisplay(&q);

    printf("--- Dequeue ---\n");
    dequeue(&q); dequeue(&q);
    qDisplay(&q);

    printf("--- Enqueue more ---\n");
    enqueue(&q, 500); enqueue(&q, 600);
    qDisplay(&q);
    return 0;
}

output

--- Enqueue ---
  enqueue(100)  rear=1  size=1
  enqueue(200)  rear=2  size=2
  enqueue(300)  rear=3  size=3
  enqueue(400)  rear=4  size=4
  Queue (front→rear): [100] [200] [300] [400]
--- Dequeue ---
  dequeue() = 100  front=1  size=3
  dequeue() = 200  front=2  size=2
  Queue (front→rear): [300] [400]
--- Enqueue more ---
  enqueue(500)  rear=5  size=3
  enqueue(600)  rear=6  size=4
  Queue (front→rear): [300] [400] [500] [600]

Linear array queues waste space. After dequeuing, front advances and those slots can never be reused — even though size is small. Once rear reaches MAX, the queue appears full even if many slots at the front are empty. The circular queue in Example 5 fixes this with modulo arithmetic.

example 3

🔤 Bracket Matching — Stack Application

Use a stack to verify (, [, { are correctly paired and nested

Application

The most classic stack application: verifying that brackets are balanced and correctly nested. Scan the expression left to right. When you see an opening bracket ((, [, {), push it. When you see a closing bracket, pop the stack and check that the popped bracket matches. If it doesn't match, or the stack is empty when you try to pop, or the stack is non-empty at the end — the expression is invalid. This is exactly how compilers verify syntax.

ex3_bracket_match.c

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

typedef struct { char data[MAX]; int top; } CStack;
void cs_init(CStack *s)        { s->top = -1; }
int  cs_empty(CStack *s)       { return s->top == -1; }
void cs_push(CStack *s, char c){ s->data[++s->top] = c; }
char cs_pop (CStack *s)        { return s->data[s->top--]; }

int isOpen (char c){ return c=='('||c=='['||c=='{'; }
int isMatch(char o, char c){
    return (o=='('&&c==')')||(o=='['&&c==']')||(o=='{'&&c=='}');
}

int isBalanced(const char *expr) {
    CStack s; cs_init(&s);
    for (int i = 0; expr[i]; i++) {
        char c = expr[i];
        if (isOpen(c)) {
            cs_push(&s, c);
        } else if (c==')'||c==']'||c=='}') {
            if (cs_empty(&s) || !isMatch(cs_pop(&s), c))
                return 0;
        }
    }
    return cs_empty(&s);  /* valid only if stack is empty at end */
}

int main() {
    const char *tests[] = {
        "(a + b) * [c - d]",
        "{x + (y * z)}",
        "((a + b)",
        "[x + y)",
        "{[(a+b)*(c-d)]}",
        ")(a+b)"
    };
    int n = sizeof(tests)/sizeof(tests[0]);

    printf("%-30s  %s\n", "Expression", "Result");
    printf("%s\n", "----------------------------------------------");
    for (int i = 0; i < n; i++)
        printf("%-30s  %s\n", tests[i],
               isBalanced(tests[i]) ? "✓ Balanced" : "✗ Unbalanced");
    return 0;
}

output

Expression                      Result
----------------------------------------------
(a + b) * [c - d]               ✓ Balanced
{x + (y * z)}                   ✓ Balanced
((a + b)                        ✗ Unbalanced
[x + y)                         ✗ Unbalanced
{[(a+b)*(c-d)]}                 ✓ Balanced
)(a+b)                          ✗ Unbalanced

Three failure modes to handle: (1) closing bracket with empty stack — no matching open, (2) top of stack doesn't match the closing bracket — wrong pair, (3) stack non-empty after scanning — unclosed open bracket. All three are caught by the single isBalanced function above.

example 4

🧮 Postfix Expression Evaluator

Evaluate RPN expressions using a stack — no parentheses needed

Stack App

Postfix (Reverse Polish Notation) writes operators after their operands: 3 4 + means 3 + 4. It needs no parentheses because order is unambiguous. Evaluation uses a stack: scan left to right — if you see a number, push it; if you see an operator, pop two operands, apply the operator, and push the result. When done, the stack holds the answer. This is how compilers and calculators evaluate expressions internally.

ex4_postfix_eval.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX 64

typedef struct { double data[MAX]; int top; } DStack;
void   ds_init (DStack *s)           { s->top = -1; }
void   ds_push (DStack *s, double v) { s->data[++s->top] = v; }
double ds_pop  (DStack *s)           { return s->data[s->top--]; }

double evalPostfix(const char *expr) {
    DStack s; ds_init(&s);
    char buf[64]; strcpy(buf, expr);
    char *tok = strtok(buf, " ");

    while (tok) {
        if (isdigit(tok[0]) || (tok[0]=='-' && tok[1])) {
            ds_push(&s, atof(tok));
        } else {
            double b = ds_pop(&s);
            double a = ds_pop(&s);
            switch (tok[0]) {
                case '+': ds_push(&s, a + b); break;
                case '-': ds_push(&s, a - b); break;
                case '*': ds_push(&s, a * b); break;
                case '/': ds_push(&s, b ? a / b : 0); break;
            }
        }
        tok = strtok(NULL, " ");
    }
    return ds_pop(&s);
}

int main() {
    struct { const char *expr; const char *infix; } tests[] = {
        { "3 4 +",         "3 + 4"          },
        { "5 1 2 + 4 * + 3 -", "5+(1+2)*4-3" },
        { "15 7 1 1 + - / 3 * 2 1 1 + + -", "15/(7-1-1)*3-2+1+1" },
        { "2 3 * 4 5 * +", "2*3 + 4*5"      },
    };
    int n = sizeof(tests)/sizeof(tests[0]);

    printf("%-36s %-22s %s\n", "Postfix", "Infix", "Result");
    printf("%s\n", "-------------------------------------------------------------------");
    for (int i = 0; i < n; i++)
        printf("%-36s %-22s %.2f\n",
               tests[i].expr, tests[i].infix,
               evalPostfix(tests[i].expr));
    return 0;
}

output

Postfix                              Infix                  Result
-------------------------------------------------------------------
3 4 +                                3 + 4                  7.00
5 1 2 + 4 * + 3 -                    5+(1+2)*4-3            14.00
15 7 1 1 + - / 3 * 2 1 1 + + -       15/(7-1-1)*3-2+1+1    5.00
2 3 * 4 5 * +                        2*3 + 4*5              26.00

Algorithm in one sentence: number → push; operator → pop two, compute, push result. The stack depth never exceeds the number of operands in the expression. Postfix evaluation is O(n) — scan once, no recursion, no parsing tree needed.

example 5

🔄 Circular Queue — Reuse Empty Slots

Modulo arithmetic wraps front and rear around the array boundary

Circular Queue

The linear array queue wastes space once elements are dequeued. The circular queue (ring buffer) solves this by wrapping front and rear around using modulo: rear = (rear + 1) % MAX. Slots freed by dequeue are immediately reusable. Full vs empty is distinguished by tracking size (or by leaving one slot always empty). Circular queues are used in OS interrupt buffers, audio streaming, network packet buffers, and producer-consumer pipelines.

ex5_circular_queue.c

#include <stdio.h>
#define MAX 5

typedef struct {
    int data[MAX];
    int front, rear, size;
} CQueue;

void cq_init   (CQueue *q){ q->front=q->rear=q->size=0; }
int  cq_empty  (CQueue *q){ return q->size == 0; }
int  cq_full   (CQueue *q){ return q->size == MAX; }

void cq_enqueue(CQueue *q, int v) {
    if (cq_full(q)) { printf("  Full!\n"); return; }
    q->data[q->rear] = v;
    q->rear  = (q->rear + 1) % MAX;   /* wrap around */
    q->size++;
    printf("  enq(%3d)  front=%d rear=%d size=%d\n",
           v, q->front, q->rear, q->size);
}

int cq_dequeue(CQueue *q) {
    if (cq_empty(q)) { printf("  Empty!\n"); return -1; }
    int v = q->data[q->front];
    q->front = (q->front + 1) % MAX;  /* wrap around */
    q->size--;
    printf("  deq() = %d  front=%d rear=%d size=%d\n",
           v, q->front, q->rear, q->size);
    return v;
}

void cq_display(CQueue *q) {
    printf("  Slots: ");
    for (int i = 0; i < MAX; i++) {
        int active = 0;
        if (q->size > 0) {
            if (q->front < q->rear)
                active = (i >= q->front && i < q->rear);
            else
                active = (i >= q->front || i < q->rear);
        }
        if (active) printf("[%3d]", q->data[i]);
        else        printf("[ -- ]");
    }
    printf("\n");
}

int main() {
    CQueue q; cq_init(&q);

    printf("--- Fill queue (capacity=%d) ---\n", MAX);
    for (int i = 1; i <= MAX; i++) cq_enqueue(&q, i*10);
    cq_display(&q);

    printf("--- Dequeue 3 ---\n");
    cq_dequeue(&q); cq_dequeue(&q); cq_dequeue(&q);
    cq_display(&q);

    printf("--- Enqueue 3 more (slots wrap!) ---\n");
    cq_enqueue(&q, 60); cq_enqueue(&q, 70); cq_enqueue(&q, 80);
    cq_display(&q);
    return 0;
}

output

--- Fill queue (capacity=5) ---
  enq( 10)  front=0 rear=1 size=1
  enq( 20)  front=0 rear=2 size=2
  enq( 30)  front=0 rear=3 size=3
  enq( 40)  front=0 rear=4 size=4
  enq( 50)  front=0 rear=0 size=5
  Slots: [ 10][ 20][ 30][ 40][ 50]
--- Dequeue 3 ---
  deq() = 10  front=1 rear=0 size=4
  deq() = 20  front=2 rear=0 size=3
  deq() = 30  front=3 rear=0 size=2
  Slots: [ -- ][ -- ][ -- ][ 40][ 50]
--- Enqueue 3 more (slots wrap!) ---
  enq( 60)  front=3 rear=1 size=3
  enq( 70)  front=3 rear=2 size=4
  enq( 80)  front=3 rear=3 size=5
  Slots: [ 60][ 70][ -- ][ 40][ 50]

Key formula: rear = (rear + 1) % MAX and front = (front + 1) % MAX. When rear reaches MAX it wraps to 0 — reusing the slots freed by dequeue. Track size separately to distinguish full (size == MAX) from empty (size == 0) without ambiguity.

example 6

🔗 Linked List Stack — Unbounded Push

Each node is malloc'd — stack grows to any size, no overflow

Linked Stack

The array stack has a fixed capacity. A linked list stack grows dynamically — each push allocates a new node with malloc and links it to the top; each pop unlinks the top node and calls free. The head pointer is the top of the stack. There is no overflow unless the system runs out of memory. This is the implementation used when maximum stack depth is unknown at compile time.

ex6_linked_stack.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          data;
    struct Node *next;
} Node;

typedef struct {
    Node *top;
    int   size;
} LStack;

void ls_init (LStack *s)        { s->top = NULL; s->size = 0; }
int  ls_empty(LStack *s)        { return s->top == NULL; }

void ls_push(LStack *s, int v) {
    Node *nd = (Node*)malloc(sizeof(Node));
    nd->data = v;
    nd->next = s->top;   /* new node points to old top */
    s->top   = nd;        /* head pointer becomes new node */
    s->size++;
    printf("  push(%d)  size=%d\n", v, s->size);
}

int ls_pop(LStack *s) {
    if (ls_empty(s)) { printf("  Underflow!\n"); return -1; }
    Node *tmp = s->top;
    int   v   = tmp->data;
    s->top = tmp->next;
    free(tmp);
    s->size--;
    printf("  pop() = %d  size=%d\n", v, s->size);
    return v;
}

void ls_display(LStack *s) {
    printf("  Stack: ");
    for (Node *p = s->top; p; p = p->next)
        printf("[%d] ", p->data);
    printf("NULL\n");
}

int main() {
    LStack s; ls_init(&s);

    printf("--- Push ---\n");
    for (int i = 1; i <= 6; i++) ls_push(&s, i * 11);
    ls_display(&s);

    printf("--- Pop 3 ---\n");
    ls_pop(&s); ls_pop(&s); ls_pop(&s);
    ls_display(&s);

    /* Free remaining nodes */
    while (!ls_empty(&s)) ls_pop(&s);
    printf("  All nodes freed.\n");
    return 0;
}

output

--- Push ---
  push(11)  size=1
  push(22)  size=2
  push(33)  size=3
  push(44)  size=4
  push(55)  size=5
  push(66)  size=6
  Stack: [66] [55] [44] [33] [22] [11] NULL
--- Pop 3 ---
  pop() = 66  size=5
  pop() = 55  size=4
  pop() = 44  size=3
  Stack: [33] [22] [11] NULL
  pop() = 33  size=2
  pop() = 22  size=1
  pop() = 11  size=0
  All nodes freed.

Push prepends to the linked list; pop removes the head. Both operations are O(1) — no iteration needed. Every node allocated with malloc in push is freed with free in pop. Always drain the stack before program exit to avoid memory leaks.

example 7

🔗 Linked List Queue — Enqueue at Tail

head pointer for dequeue, tail pointer for O(1) enqueue

Linked Queue

A linked list queue keeps two pointers — head (front, dequeue side) and tail (rear, enqueue side). Enqueue allocates a new node and appends it at the tail in O(1). Dequeue removes the head node and advances the head pointer in O(1). Unlike the circular array queue, there is no capacity limit and no wasted slots. The tail->next = newNode; tail = newNode pattern is the standard append operation.

ex7_linked_queue.c

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int          data;
    struct Node *next;
} Node;

typedef struct {
    Node *head;   /* front — dequeue here */
    Node *tail;   /* rear  — enqueue here */
    int   size;
} LQueue;

void lq_init(LQueue *q) { q->head = q->tail = NULL; q->size = 0; }
int  lq_empty(LQueue *q){ return q->head == NULL; }

void lq_enqueue(LQueue *q, int v) {
    Node *nd = (Node*)malloc(sizeof(Node));
    nd->data = v; nd->next = NULL;
    if (q->tail) q->tail->next = nd;
    else         q->head = nd;
    q->tail = nd;
    q->size++;
    printf("  enq(%d)  size=%d\n", v, q->size);
}

int lq_dequeue(LQueue *q) {
    if (lq_empty(q)) { printf("  Empty!\n"); return -1; }
    Node *tmp = q->head;
    int   v   = tmp->data;
    q->head = tmp->next;
    if (!q->head) q->tail = NULL;
    free(tmp);
    q->size--;
    printf("  deq() = %d  size=%d\n", v, q->size);
    return v;
}

void lq_display(LQueue *q) {
    printf("  Queue (head→tail): ");
    for (Node *p = q->head; p; p = p->next)
        printf("[%d] ", p->data);
    printf("NULL\n");
}

int main() {
    LQueue q; lq_init(&q);

    printf("--- Enqueue A-E ---\n");
    int vals[] = {5,15,25,35,45};
    for (int i=0;i<5;i++) lq_enqueue(&q, vals[i]);
    lq_display(&q);

    printf("--- Dequeue 2 ---\n");
    lq_dequeue(&q); lq_dequeue(&q);
    lq_display(&q);

    printf("--- Enqueue 55, 65 ---\n");
    lq_enqueue(&q, 55); lq_enqueue(&q, 65);
    lq_display(&q);

    while (!lq_empty(&q)) lq_dequeue(&q);
    return 0;
}

output

--- Enqueue A-E ---
  enq(5)   size=1
  enq(15)  size=2
  enq(25)  size=3
  enq(35)  size=4
  enq(45)  size=5
  Queue (head→tail): [5] [15] [25] [35] [45] NULL
--- Dequeue 2 ---
  deq() = 5   size=4
  deq() = 15  size=3
  Queue (head→tail): [25] [35] [45] NULL
--- Enqueue 55, 65 ---
  enq(55)  size=4
  enq(65)  size=5
  Queue (head→tail): [25] [35] [45] [55] [65] NULL

The tail pointer is what makes enqueue O(1). Without it, every enqueue would walk the entire list to find the last node — O(n). With a tail pointer, appending is a single pointer update. Always set tail = NULL when the last node is dequeued, or the tail will point to freed memory.

example 8

↔️ Deque — Double-Ended Queue

Push and pop from both ends — front and rear insertions and deletions

Deque

A deque (double-ended queue) supports insert and delete at both the front and the rear. It generalises both a stack (push/pop front) and a queue (push rear, pop front). Built on a circular array, it uses four operations: pushFront, pushRear, popFront, popRear. Deques are used for sliding-window algorithms, palindrome checking, undo/redo history, and browser back/forward navigation.

ex8_deque.c

#include <stdio.h>
#define MAX 8

typedef struct {
    int data[MAX];
    int front, rear, size;
} Deque;

void dq_init  (Deque *d){ d->front=0; d->rear=0; d->size=0; }
int  dq_empty (Deque *d){ return d->size==0; }
int  dq_full  (Deque *d){ return d->size==MAX; }

void pushRear(Deque *d, int v) {
    if (dq_full(d))  { printf("  Full!\n"); return; }
    d->data[d->rear] = v;
    d->rear = (d->rear + 1) % MAX;
    d->size++;
}
void pushFront(Deque *d, int v) {
    if (dq_full(d))  { printf("  Full!\n"); return; }
    d->front = (d->front - 1 + MAX) % MAX;
    d->data[d->front] = v;
    d->size++;
}
int popFront(Deque *d) {
    if (dq_empty(d)) { printf("  Empty!\n"); return -1; }
    int v = d->data[d->front];
    d->front = (d->front + 1) % MAX;
    d->size--;
    return v;
}
int popRear(Deque *d) {
    if (dq_empty(d)) { printf("  Empty!\n"); return -1; }
    d->rear = (d->rear - 1 + MAX) % MAX;
    int v = d->data[d->rear];
    d->size--;
    return v;
}

void dq_display(Deque *d) {
    printf("  Deque (F→R): ");
    for (int i=0; i<d->size; i++)
        printf("[%d] ", d->data[(d->front+i)%MAX]);
    printf("\n");
}

int main() {
    Deque d; dq_init(&d);

    printf("pushRear 10,20,30:\n");
    pushRear(&d,10); pushRear(&d,20); pushRear(&d,30);
    dq_display(&d);

    printf("pushFront 5, pushFront 1:\n");
    pushFront(&d,5); pushFront(&d,1);
    dq_display(&d);

    printf("popFront = %d\n", popFront(&d));
    printf("popRear  = %d\n", popRear(&d));
    dq_display(&d);

    printf("\n--- Palindrome check via Deque ---\n");
    const char *words[] = { "racecar", "hello", "madam", "world" };
    for (int w=0;w<4;w++) {
        Deque pd; dq_init(&pd);
        for (int i=0; words[w][i]; i++) pushRear(&pd, words[w][i]);
        int ok=1;
        while (pd.size > 1)
            if (popFront(&pd) != popRear(&pd)) { ok=0; break; }
        printf("  %-8s %s\n", words[w], ok ? "palindrome" : "not palindrome");
    }
    return 0;
}

output

pushRear 10,20,30:
  Deque (F→R): [10] [20] [30]
pushFront 5, pushFront 1:
  Deque (F→R): [1] [5] [10] [20] [30]
popFront = 1
popRear  = 30
  Deque (F→R): [5] [10] [20]

--- Palindrome check via Deque ---
  racecar  palindrome
  hello    not palindrome
  madam    palindrome
  world    not palindrome

pushFront wraps backwards: front = (front - 1 + MAX) % MAX. Adding MAX before the modulo prevents negative values. The palindrome check is elegant — pop one character from each end and compare; if they always match until the deque has ≤ 1 element, the word is a palindrome.

example 9

⭐ Priority Queue — Serve Highest Priority First

Items carry a priority number — dequeue always returns the highest-priority item

Priority Queue

A priority queue dequeues elements by priority, not by arrival order. Implemented here as a sorted array — enqueue inserts in the correct sorted position (O(n)), dequeue simply removes the front element (O(1)). Lower priority number = higher priority (like OS process scheduling). This is used in Dijkstra's shortest path, Huffman encoding, CPU schedulers, and hospital triage systems.

ex9_priority_queue.c

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

typedef struct {
    char name[20];
    int  priority;    /* lower number = higher urgency */
} Task;

typedef struct {
    Task data[MAX];
    int  size;
} PQueue;

void pq_init (PQueue *q) { q->size = 0; }
int  pq_empty(PQueue *q) { return q->size == 0; }

/* Insert keeping array sorted by priority (ascending) */
void pq_enqueue(PQueue *q, const char *name, int pri) {
    if (q->size == MAX) { printf("  PQ full!\n"); return; }
    int i = q->size - 1;
    while (i >= 0 && q->data[i].priority > pri) {
        q->data[i+1] = q->data[i];
        i--;
    }
    strcpy(q->data[i+1].name, name);
    q->data[i+1].priority = pri;
    q->size++;
    printf("  enq %-14s  pri=%d\n", name, pri);
}

/* Dequeue the highest-priority (lowest number) item */
Task pq_dequeue(PQueue *q) {
    Task t = q->data[0];
    for (int i=0;i<q->size-1;i++) q->data[i]=q->data[i+1];
    q->size--;
    printf("  serve → %-14s (pri=%d)\n", t.name, t.priority);
    return t;
}

void pq_display(PQueue *q) {
    printf("  Queue: ");
    for (int i=0;i<q->size;i++)
        printf("[%s|P%d] ", q->data[i].name, q->data[i].priority);
    printf("\n");
}

int main() {
    PQueue pq; pq_init(&pq);

    printf("--- Enqueue tasks ---\n");
    pq_enqueue(&pq, "Email",     3);
    pq_enqueue(&pq, "System Alert",1);
    pq_enqueue(&pq, "Backup",    5);
    pq_enqueue(&pq, "DB Query",  2);
    pq_enqueue(&pq, "Log Write", 4);
    pq_enqueue(&pq, "Heartbeat", 1);

    printf("\n"); pq_display(&pq);

    printf("\n--- Serve all tasks ---\n");
    while (!pq_empty(&pq)) pq_dequeue(&pq);
    return 0;
}

output

--- Enqueue tasks ---
  enq Email           pri=3
  enq System Alert    pri=1
  enq Backup          pri=5
  enq DB Query        pri=2
  enq Log Write       pri=4
  enq Heartbeat       pri=1

  Queue: [System Alert|P1] [Heartbeat|P1] [DB Query|P2] [Email|P3] [Log Write|P4] [Backup|P5]

--- Serve all tasks ---
  serve → System Alert   (pri=1)
  serve → Heartbeat      (pri=1)
  serve → DB Query       (pri=2)
  serve → Email          (pri=3)
  serve → Log Write      (pri=4)
  serve → Backup         (pri=5)

This sorted-array approach is simple but O(n) on insert. For production code with thousands of items, replace with a binary heap for O(log n) insert and dequeue. The interface stays the same — only the internal storage and insertion logic change. The heap-based priority queue is the foundation of Dijkstra's algorithm and most OS schedulers.

example 10

🏗️ Full App — Multi-Queue Task Scheduler

Linked queue + priority queue + stack history — a complete CPU scheduler simulation

Complete App

Everything from Examples 1–9 combined into a real application. A task scheduler maintains three structures: a ready queue (linked list queue, FIFO) for normal tasks, a priority queue for urgent tasks, and a stack for execution history (most recent task on top). Each tick the scheduler picks the highest-priority urgent task first; if none, it takes from the ready queue. Completed tasks are pushed onto the history stack and can be reviewed at any time.

ex10_task_scheduler.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HMAX 20
#define PMAX 10

/* ── Task ── */
typedef struct {
    int  id;
    char name[24];
    int  priority;    /* 0=urgent, 1=normal */
} Task;

/* ── History Stack (array) ── */
typedef struct { Task data[HMAX]; int top; } HStack;
void hs_init (HStack *s)         { s->top=-1; }
int  hs_empty(HStack *s)         { return s->top==-1; }
void hs_push (HStack *s, Task t)  { s->data[++s->top]=t; }
Task hs_peek (HStack *s)          { return s->data[s->top]; }

/* ── Ready Queue (linked list) ── */
typedef struct QNode { Task t; struct QNode *next; } QNode;
typedef struct { QNode *head, *tail; int size; } RQueue;
void rq_init (RQueue *q){ q->head=q->tail=NULL; q->size=0; }
int  rq_empty(RQueue *q){ return !q->head; }
void rq_enq  (RQueue *q, Task t){
    QNode *n=(QNode*)malloc(sizeof(QNode));
    n->t=t; n->next=NULL;
    if(q->tail) q->tail->next=n; else q->head=n;
    q->tail=n; q->size++;
}
Task rq_deq(RQueue *q){
    QNode *tmp=q->head; Task t=tmp->t;
    q->head=tmp->next;
    if(!q->head) q->tail=NULL;
    free(tmp); q->size--; return t;
}

/* ── Priority Queue (sorted array) ── */
typedef struct { Task data[PMAX]; int size; } PQueue;
void pq_init (PQueue *q){ q->size=0; }
int  pq_empty(PQueue *q){ return !q->size; }
void pq_enq  (PQueue *q, Task t){
    int i=q->size-1;
    while(i>=0 && q->data[i].priority>t.priority){
        q->data[i+1]=q->data[i]; i--;
    }
    q->data[i+1]=t; q->size++;
}
Task pq_deq(PQueue *q){
    Task t=q->data[0];
    for(int i=0;i<q->size-1;i++) q->data[i]=q->data[i+1];
    q->size--; return t;
}

/* ── Scheduler ── */
void submit(RQueue *rq, PQueue *pq, Task t){
    printf("  SUBMIT  [%02d] %-20s (pri=%d)\n", t.id, t.name, t.priority);
    if(t.priority == 0) pq_enq(pq, t);
    else                 rq_enq(rq, t);
}

void tick(RQueue *rq, PQueue *pq, HStack *hs){
    Task t;
    if(!pq_empty(pq)){
        t = pq_deq(pq);
        printf("  RUN    [%02d] %-20s  <urgent>\n", t.id, t.name);
    } else if(!rq_empty(rq)){
        t = rq_deq(rq);
        printf("  RUN    [%02d] %-20s  <normal>\n", t.id, t.name);
    } else {
        printf("  IDLE   (no tasks)\n"); return;
    }
    hs_push(hs, t);
}

int main() {
    RQueue rq; PQueue pq; HStack hs;
    rq_init(&rq); pq_init(&pq); hs_init(&hs);

    printf("=== Submit Tasks ===\n");
    Task tasks[] = {
        {1,"Compile Module",    1},
        {2,"Security Patch",    0},
        {3,"Send Report",       1},
        {4,"System Monitor",    0},
        {5,"Cleanup Logs",      1},
        {6,"DB Backup",         1},
        {7,"Critical Alert",    0},
    };
    for(int i=0;i<7;i++) submit(&rq, &pq, tasks[i]);

    printf("\n=== Run Scheduler (7 ticks) ===\n");
    for(int tick=1;tick<=7;tick++){
        printf("Tick %d: ", tick);
        tick(&rq, &pq, &hs);
    }

    printf("\n=== Execution History (most recent first) ===\n");
    for(int i=hs.top;i>=0;i--)
        printf("  [%02d] %s\n", hs.data[i].id, hs.data[i].name);
    return 0;
}

output

=== Submit Tasks ===
  SUBMIT  [01] Compile Module       (pri=1)
  SUBMIT  [02] Security Patch       (pri=0)
  SUBMIT  [03] Send Report          (pri=1)
  SUBMIT  [04] System Monitor       (pri=0)
  SUBMIT  [05] Cleanup Logs         (pri=1)
  SUBMIT  [06] DB Backup            (pri=1)
  SUBMIT  [07] Critical Alert       (pri=0)

=== Run Scheduler (7 ticks) ===
Tick 1: RUN    [02] Security Patch        <urgent>
Tick 2: RUN    [04] System Monitor        <urgent>
Tick 3: RUN    [07] Critical Alert        <urgent>
Tick 4: RUN    [01] Compile Module        <normal>
Tick 5: RUN    [03] Send Report           <normal>
Tick 6: RUN    [05] Cleanup Logs          <normal>
Tick 7: RUN    [06] DB Backup             <normal>

=== Execution History (most recent first) ===
  [06] DB Backup
  [05] Cleanup Logs
  [03] Send Report
  [01] Compile Module
  [07] Critical Alert
  [04] System Monitor
  [02] Security Patch

All 4 data structures united in one program: linked queue for FIFO normal tasks · sorted-array priority queue for urgent tasks — always drains before the normal queue · array stack for execution history (most recent on top via LIFO) · dispatcher loop calls the right structure each tick. This is the exact architecture of a real-time OS task scheduler — priority queues for interrupt handlers, FIFO queues for user processes, stack for call history.

checklist

Ex 1 — Stack is LIFO. top = -1 means empty. Push: data[++top] = val. Pop: val = data[top--]. Guard overflow and underflow.
Ex 2 — Queue is FIFO. Enqueue at rear, dequeue at front. Linear array wastes slots — front never moves back.
Ex 3 — Bracket matching: push opens, pop on close and verify match. Stack non-empty at end means unclosed brackets.
Ex 4 — Postfix eval: number → push; operator → pop two, compute, push result. O(n) single-pass, no parentheses needed.
Ex 5 — Circular queue: (index + 1) % MAX wraps around. Track size to distinguish full from empty. Slots freed by dequeue are reused.
Ex 6 — Linked stack: push prepends a malloc'd node; pop frees the head. No capacity limit. Both operations are O(1).
Ex 7 — Linked queue: head pointer for O(1) dequeue; tail pointer for O(1) enqueue. Set tail = NULL when last node is removed.
Ex 8 — Deque allows insert/delete at both ends. pushFront wraps back: (front - 1 + MAX) % MAX. Solves palindrome check elegantly.
Ex 9 — Priority queue serves lowest-number priority first. Sorted-array insert is O(n); heap-based insert is O(log n) for production use.
Ex 10 — Full scheduler: priority queue drains before FIFO ready queue. History stack shows most recent task on top. Three structures, one dispatcher loop.

Stacks & Queues in C —10 Programs

Stacks & Queues in C —
10 Programs