Queue is a data structure which allows data in it come or go with a FIFO (First In First Out) sequence. Queue could either be implemented with arrays or linked lists. In this article, I'll use array to describe queue in C Language.

Compared with being implemented in linked list, the queue implemented in array has a queue size and we set a "head pointer" **head** and a "tail pointer" **rear** always indicates the head and tail of the queue respectively; Note that **head** and **rear** are not real pointers, they're just indices of the array. Note that there're a lot of methods of representing queue empty or full, I just use, in my opinion, the most simple way to represent: When the queue is empty, the **head** equals **rear**, which means the **rear** is always indicating the next index of available slot of queue. Now the problem is that with some data are moved out from queue and some data are inserted into queue, when the **head** reaches the length of queue, although the queue has empty slots, we cannot use it because **rear** will exceed the array boundary.

To solve this problem, we use **module** operation to make the queue circular. That means when **head** or **rear** will exceed the array boundary, it wraps around to the first index. Note that we need an idle slot, otherwise the condition on queue empty and queue full is the same.

The data structure of queue is quite simple. Note that the type of base field could be any other types, even a struct.

```
typedef struct Queue {
type* base;
int head;
int rear;
int size;
} Queue;
```

**Initialize**

To initialize the queue, we need to set the size of the queue, applying for the dynamic memory space for it; And set **head** equals to -1 and **rear** equals to 0

```
int initialQueue(Queue *q, int size){
if (NULL == q)
return -1;
q->base = (elementType*)malloc(size*sizeof(elementType))
if (NULL == q->base)
return -1;
q->size = size + 1;
q->head = 0;
q->rear = 0;
return 0;
}
```

**Enter Queue**

Insert an element into the tail of queue. Before inserting, we need to check whether the queue is full or not. when **(rear + 1) % size = head**, the queue is full.

```
int enQueue(Queue *q, elementType element){
if (NULL == q)
return -1;
if ((q->rear + 1) % q->size == q->head)
return -1; // full
q->base[q->rear] = element;
q->rear = (q->rear + 1) % q->size;
return 0;
}
```

**Leave Queue**

Pull an element from the head of queue. Before pulling, we need to check whether the queue is empty or not. when **head = rear**, the queue is empty.

```
int deQueue(Stack *q, elementType *element){
if (NULL == q)
return -1;
if (q->head == q->rear)
return -1; // empty
q->head = (q->head + 1) % q->size;
*element = q->base[q->head];
return 0;
}
```

**Get Queue Length**

Get the length of the queue.

```
int getLength(Queue q) {
if (NULL == q.base)
return -1;
return (q.rear + q.size - q.head) % q.size;
}
```

**Destroy**

Free the dynamic memory for the queue.

```
void destroyQueue(Queue q){
if (NULL == q.base)
return;
free(q.base);
}
```