队列(循环队列)的顺序存储实现

//
//

/************************************队列的顺序存储实现********************************************/
/**
 * 1、队列:一端进，另一端出；队列由两个参数决定，front(头),rear(尾)；
	头指针指向头一个元素，尾指针指向指向最后一个元素的下一存储单元；若数组长度为n，当元素个数为n-1时就认为队列已满。r指向最后一个空的元素空间。

	出队：头指针往上移动，

	入队：尾指针向上移动，故：静态队列只能是循环队列，不然出队的元素占用的空间
	永远无法重复利用。

	1）：队列的初始化:front,rear的值都是零、
	2）：队列非空：front代表的是队列的第一个元素,rear代表的是队列的最后一个元素的下个存储单元
	3)  ：队列空:front和rear的值相等，但不一定是零
	4）：动态队列：链表实现
	     静态队列：数组实现

2、循环队列:
	出队：f = (f+1) % 数组长度
	入队：r = (r+1) % 数组长度

		+++++++++++++++++++++
		+		    +
		+		    +<----r
		+		    +
		+++++++++++++++++++++
		+		    +
		+	c	    +
		+		    +
		+++++++++++++++++++++
		+		    +
		+	b	    +
		+		    +
		+++++++++++++++++++++
		+		    +
 f ---> +	 a	    +
		+		    +
		+++++++++++++++++++++

	如何判断循环队列是否为空: 如果f == r 就一定为空
	如何判断队列已满：
		1）增加一个标志n记录队列元素的个数，当n = 数组长度-1时，就满了。
		2)if((r+1)%arr.length == f){
			队列已满
		}
		通常使用第二种
 * **/


#include <stdio.h>
#include <stdlib.h>

/**
 * 循环队列
 */
typedef  struct array_queue{
    int * data; //数组
    int limit; //队列容量
    int size;//队列中元素个数
    int head;//队首
    int tail;//队尾
}ArrayQueue;


/**
 * 创建队列
 * @param limit
 * @return
 */
static ArrayQueue * createArrayQueue(int limit){
    ArrayQueue * queue = (ArrayQueue *)calloc(1, sizeof(ArrayQueue));
    int * data = (int *)calloc(limit + 1, sizeof(int)); //因为队尾指向最后一个元素的下一个位置，所以数组大小为limit+1
    queue->data = data;
    queue->size = 0;
    queue->limit = limit;
    queue->head = 0;
    queue->tail = 0;
}

/**
 * 队列是否满了
 * @param queue
 * @return
 */
static int isFull(ArrayQueue * queue){
    if((queue->tail + 1) % (queue->limit+1) == queue->head){
        return 1;
    }
    return 0;
}

/**
 * 是否空
 * @param queue
 * @return
 */
static int isEmpty(ArrayQueue * queue){
    if(queue->head == queue->tail){
        return 1;
    }
    return 0;
}

/**
 * 入队
 * @param queue
 * @param data
 */
static  void enqueue(ArrayQueue *queue, int data){
    if(isFull(queue)){
        printf("queue is full\n");
        return;
    }
    queue->data[queue->tail] = data;
    queue->tail = (queue->tail+1) % (queue->limit+1);
    queue->size++;
}

/**
 * 出队
 * @param queue
 * @return
 */
static int dequeue(ArrayQueue * queue){
    if(isEmpty(queue)){
        printf("queue is empty\n");
        return -1;
    }
    int data = queue->head;
    queue->head = (queue->head+1) % (queue->limit+1);
    return data;
}
void freeQueue(ArrayQueue * queue){
    free(queue->data);
    free(queue);
}

int main(){
    ArrayQueue * queue = createArrayQueue(10);
    for(int i = 0; i < 12; i++){
        enqueue(queue, i);
    }
    for(int i = 0; i < 12; i++){
        printf("%d\n", dequeue(queue));
    }
    freeQueue(queue);
    return 0;
}