//
//
/************************************队列的顺序存储实现********************************************/
/**
* 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;
}