Circular queue using linked list

A circular queue using a linked list is a singly linked list whose last node points back to the first node. One pointer rear pointing to the last node is enough: rear->next is the front node. Insertion is done after rear, deletion from rear->next.

 rear
  |
  v
 [10|*]->[20|*]->[30|*]--+
  ^ (front)               |
  +-----------------------+

struct node { int info; struct node *next; };
struct node *rear = NULL;       /* NULL means queue is empty */

ENQUEUE(x)

1. Create node p; if malloc fails print "overflow" and stop. p->info = x.
2. If rear == NULL (empty): p->next = p (points to itself).
3. Else: p->next = rear->next (new node points to the front); rear->next = p.
4. rear = p.

DEQUEUE()

1. If rear == NULL, print "underflow" and stop.
2. f = rear->next (front node); x = f->info.
3. If f == rear (only one node): rear = NULL.
4. Else: rear->next = f->next.
5. free(f); return x.

DISPLAY()

If rear == NULL print "empty". Else p = rear->next; do { print p->info; p = p->next; } while (p != rear->next);

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

Trace

(The C code was compiled and run on this sequence: it gives 1, then 2, 3, 4.) Both operations are O(1) and no space is wasted, unlike an array queue.