Push and pop on stack as linked list

A stack as a linked list keeps its top at the head of a singly linked list, so push and pop both work at the front. Nodes are created with malloc, hence no fixed size limit.

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

PUSH(x)

1. Create node p using malloc; if NULL, print "overflow" and stop.
2. p->info = x.
3. p->next = top (new node points to the old top).
4. top = p.

POP()

1. If top == NULL, print "underflow" and stop.
2. p = top.
3. x = p->info.
4. top = top->next.
5. free(p); return x.

Initial:           push(30):               pop():
top -> [20]->[10]  top -> [30]->[20]->[10]  top -> [20]->[10]  (returns 30)

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

Both operations take O(1) time.