队列的实现（数组方式）

用数组方式去实现队列，为了避免空间浪费，我们利用循环队列的方式，即当新成员入队时，如果队尾没有空间了，可以查询对头是否有空闲的空间，如果有，则入队，否则不入队。

入队时，只需rear+1，出队时，只需front+1。数组方式的实现，最主要需要考虑两个问题，一个是队列满的情况，一个是队列空的情况，因为入队出队操作都与这两种情况有关联。

首先，我们看下如何判断队列满的情况
1. 见下图

判断条件：(rear+1)%LEN == front
2. 见下图

判断条件：rear+1 == front
合并在一起，判断是否满的条件为：

(rear+1)%LEN == front

接着，我们看看如何判断队列为空的情况，这个很简单，只需要判断队列的头和尾是否重叠即可，如下

queue->front == queue->rear

代码实现如下

array_queue.h

#ifndef __ARRAY_QUEUE_H__
#define __ARRAY_QUEUE_H__


typedef int ElementType;
typedef int Position;

typedef struct ArrQueue_T
{
    Position front;
    Position rear;
    ElementType * array;
}ArrQueue;

typedef struct ArrQueue_T Node;


#define ARR_QUEUE_MAX_SIZE 5

extern void array_queue_main_test(void);

#endif

array_queue.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#include "array_queue.h"


ArrQueue * array_queue_create(void)
{
    ArrQueue * queue = (ArrQueue *)malloc(sizeof(ArrQueue));
    if(NULL == queue)
    {
        printf("queue malloc fail\n");
        return NULL;
    }

    queue->array = (ElementType *)malloc(sizeof(ElementType) * ARR_QUEUE_MAX_SIZE);
    if(NULL == queue->array)
    {
        printf("queue->array malloc fail\n");
        return NULL;
    }

    queue->front = 0;
    queue->rear = 0;

    return queue;
}

bool array_queue_is_empty(ArrQueue * queue)
{
    return queue->front == queue->rear;
}

bool array_queue_is_full(ArrQueue * queue)
{
    return queue->front == ((queue->rear + 1)%ARR_QUEUE_MAX_SIZE);
}

/*  Insert element, rear+1 */
int array_queue_in(ArrQueue * queue, ElementType elem)
{
    if(true == array_queue_is_full(queue))
    {
        printf("queue is full, cannot insert\n");
        return -1;
    }   

    queue->array[queue->rear] = elem;
    queue->rear = (queue->rear + 1) % ARR_QUEUE_MAX_SIZE;

    return 0;
}

/*  Delete element, front+1 */
int array_queue_out(ArrQueue * queue)
{
    if(true == array_queue_is_empty(queue))
    {
        printf("queue is empty, cannot delete\n");
        return -1;
    }

    queue->front = (queue->front + 1) % ARR_QUEUE_MAX_SIZE;

    return 0;
}

void array_queue_traverse(ArrQueue * queue)
{
    int i = queue->front;

    while(i != queue->rear)
    {
        printf("value=%d\n", queue->array[i]);
        i = (i+1)%ARR_QUEUE_MAX_SIZE;
    }
}

void array_queue_main_test(void)
{
    ArrQueue * q = array_queue_create();

    array_queue_in(q, 1);
    array_queue_in(q, 2);
    array_queue_in(q, 3);
    array_queue_in(q, 4);
    array_queue_out(q);
    array_queue_out(q);
    array_queue_in(q, 5);
    array_queue_in(q, 6);
    array_queue_in(q, 7);

    array_queue_traverse(q);
}