In the Queue

I'm working on queues today. I'm implementing a queue using a fixed-size array, and also using a linked list.

These are the four operations each will support:

enqueue(value) - adds item at end of available storage
dequeue() - returns value and removes least recently added element
empty()
full() - not on linked list version

The array implementation involves a lot of modulo operations, in order to wrap around to the beginning of the array once the end is reached. One trick with the array implementation is that there's always an empty position that cannot be inserted to, so I have 2 constants: kQueueCapacity and kQueuePositions. kQueueCapacity is the number of items the queue can store, and kQueuePositions is kQueueCapacity + 1.

Here's a brief snippet of code in C that will tell you if the queue is full:

bool full(queue *q) {  
  return q->pop == (q->insert + 1) % kQueuePositions;
}

q->pop is the position that will be popped next, and q->insert is the position that will be inserted into next. There is always an empty gap between q->insert and q->pop. This code is true when the next position insert after an insert would be equal to pop.

I like this short bit of code I came up with for printing the queue:

void print_debug(queue *q) {  
  printf("Queue contents (old to new): ");

  for (int i = q->pop; i != q->insert; i = (i + 1) % kQueuePositions) {
    printf("%d, ", q->data[i]);
  }

  printf("\n");
}

Menu