Linked stack overcoming array demerits

Demerits of array stack: fixed size (overflow even when memory is free, or wasted space when mostly empty), size must be known in advance, and it cannot grow at run time. A linked stack removes these: nodes are allocated on demand, so the stack grows and shrinks dynamically.

Algorithm (top = head of a singly linked list)

struct node { int info; struct node *next; };
struct node *top = NULL;

PUSH(x)

1. Create node p with malloc; if NULL, overflow (heap full), stop.
2. p->info = x; p->next = top; top = p.

POP()

1. If top == NULL, underflow, stop.
2. p = top; x = p->info; top = top->next; free(p); return x.

PEEK(): if top != NULL return top->info.

void push(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (!p) { printf("Overflow\n"); return; }
    p->info = x; p->next = top; top = p;
}
int pop(void) {
    if (!top) { printf("Underflow\n"); return -1; }
    struct node *p = top; int x = p->info;
    top = top->next; free(p);
    return x;
}

Verification

push(2):  top -> [2]->[8]->[5]->NULL
pop():    top -> [8]->[5]->NULL       ([2] freed)

Elements leave in last-in first-out order, and push/pop are O(1) with no size limit except available memory.