Dynamic implementation of queue

In dynamic implementation, queue nodes are allocated from the heap with malloc when an element is inserted and released with free when removed. A singly linked list with pointers front (deletion end) and rear (insertion end) is used, so the queue has no fixed capacity.

struct node { int info; struct node *next; };
struct node *front = NULL, *rear = NULL;

ENQUEUE(x)

1. Allocate node p; if NULL print "overflow" and stop.
2. p->info = x; p->next = NULL.
3. If rear == NULL (empty): front = rear = p.
4. Else: rear->next = p; rear = p.

DEQUEUE()

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

void enqueue(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (!p) { printf("Overflow\n"); return; }
    p->info = x; p->next = NULL;
    if (rear == NULL) front = rear = p;
    else { rear->next = p; rear = p; }
}
int dequeue(void) {
    if (!front) { printf("Underflow\n"); return -1; }
    struct node *p = front; int x = p->info;
    front = front->next;
    if (!front) rear = NULL;
    free(p);
    return x;
}

Verification (illustration)

after enqueue 10,20,30:
front                 rear
  |                     |
  v                     v
 [10|*]->[20|*]->[30|NULL]

Elements leave in the order they entered (FIFO). Both operations are O(1).