Stack and queue using linked list

Both use the node struct node { int info; struct node *next; };. Memory is taken from the heap with malloc, so there is no fixed limit (overflow only when the heap is full).

Stack using a singly linked list

The top is the head of the list: push and pop both work at the front, so both are O(1).

top
 |
 v
[30|*]->[20|*]->[10|NULL]

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

void push(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) { printf("Overflow\n"); return; }
    p->info = x;
    p->next = top;        /* new node points to old top */
    top = p;              /* top moves to the new node  */
}

int pop(void) {
    struct node *p; int x;
    if (top == NULL) { printf("Underflow\n"); return -1; }
    p = top;
    x = p->info;
    top = top->next;      /* second node becomes top */
    free(p);
    return x;
}

Algorithm for push: (1) create node p; (2) p->info = x; (3) p->next = top; (4) top = p. Algorithm for pop: (1) if top = NULL, underflow; (2) p = top; (3) x = p->info; (4) top = top->next; (5) free(p); return x.

Queue using a singly linked list

Keep two pointers: front (where deletion occurs) and rear (where insertion occurs). Insert at the rear, delete from the front.

front                    rear
 |                        |
 v                        v
[10|*]->[20|*]->[30|NULL]

struct node *front = NULL, *rear = NULL;

void enqueue(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (p == NULL) { printf("Overflow\n"); return; }
    p->info = x;  p->next = NULL;
    if (rear == NULL)          /* queue empty */
        front = rear = p;
    else {
        rear->next = p;        /* link after the last node */
        rear = p;
    }
}

int dequeue(void) {
    struct node *p; int x;
    if (front == NULL) { printf("Underflow\n"); return -1; }
    p = front;
    x = p->info;
    front = front->next;
    if (front == NULL) rear = NULL;   /* queue became empty */
    free(p);
    return x;
}

Enqueue steps: create node with next = NULL; if queue empty then front = rear = node; else rear->next = node, rear = node. Dequeue steps: if front = NULL underflow; p = front; front = front->next; if front becomes NULL set rear = NULL; free(p).

Both operations are O(1) and no shifting is needed.