Queues

Queues are dynamic sets whose delete operation implements a first-in, last-out (FILO) policy. Adding to a queue is to enqueue and removing is to dequeue. Like linked lists, queues have a head and a tail. Enqueues always add to the tail and dequeues always take from the head. Enqueuing and dequeuing both take $O(n)$ time.

The queue will wrap around over time:

struct Queue {
  int head, tail, size;
  int array[QUEUE_SIZE];
}

bool enqueue(struct Queue q, int x) {
  if (q.tail == q.head-1)
    return false; // this is an overflow
  else {
    q.array[++q.tail] = x;
    return true;
  }
}

int dequeue(struct Queue q) {
  if (q.head == q.tail)
    return 0; // this is an underflow
  else
    return q.array[q.tail--];
}