数据结构与算法07——循环队列

循环队列的特点：
所有队列的特点都是先进先出
**在循环队列中，由于入队时：尾指针向前驱赶头指针。出队时：头指针向前驱赶尾指针。无论当队空或队满时：front==rear，所以不能判断队空或者队满。这个时候我们可以空出一个元素空间，也就是最后一个元素空间不使用，这样样的话，队满时就是：(rear+1)%n==front。从而判断队空和队满
**

image.png

循环队列的操作

• 循环队列的定义

#define OK 1
#define ERROR 0
#define ARR_SIZE 6
typedef int Status;

typedef struct Queue{
    int *QArr;//存放队列元素的数组
    int front;
    int rear;
}QUEUE;

• 循环队列初始化
  新建队列，分配内存，头指针和尾指针置0;

Status InitQueue(QUEUE *q){
    q->QArr = (int *)malloc(sizeof(int) * ARR_SIZE);
    
    if (q->QArr != NULL) {
        q->front = q->rear = 0;
        return OK;
    }
    return ERROR;
}

• 判断队列为空
  头指针和尾指针指向相同的地方时，队空。

Status IsEmptyQueue(QUEUE q){
    if (q.front == q.rear) {
        return OK;
    }
    return ERROR;
}

• 判断队满
  队满的条件：(rear+1)%n==front

Status IsFullQueue(QUEUE q){
    if ((q.rear+1)%ARR_SIZE == q.front) {
        return OK;
    }
    return ERROR;
}

• 获取对头元素
  获取对头元素就是获取先进的元素

Status GetTopValue(QUEUE q){
    if (IsEmptyQueue(q)) return ERROR;
    
    return q.QArr[q.front];
}

• 获取队列的长度

int lengthOfQueue(QUEUE q){
    if (IsEmptyQueue(q)) return ERROR;
    
    return (q.rear - q.front + ARR_SIZE)%ARR_SIZE;
}

• 清空队列
  头尾置空

Status ClearQueue(QUEUE *q){
    
    q->front = q->rear = 0;
    
    return OK;
}

• 入队
  入队操作就是将数据放到内存中，但是要考虑放到那一块内存中。我们要做的是，保持头指针不动，尾指针向后移动一位

Status InQueue(QUEUE *q,int data){
    if (IsFullQueue(*q)) return ERROR;
    
    q->QArr[q->rear] = data;
    q->rear = (q->rear + 1)%ARR_SIZE;
    return OK;
}

• 出队
  先进先出，出队操作是将先进来的元素移出。头指针向后偏移，尾指针不动

Status OutQueue(QUEUE *q,int *data){
    if (IsEmptyQueue(*q)) return ERROR;
    
    //出队元素
    *data = q->QArr[q->front];
    q->QArr[q->front] = 0;
    q->front = (q->front + 1)%ARR_SIZE;
    
    return OK;
}

遍历

void printQueue(QUEUE q){
    if (IsEmptyQueue(q)) return;
    
    printf("打印队列！\n");
    while (q.front != q.rear) {
        printf("%d  ",q.QArr[q.front]);
        
        q.front = (q.front + 1)%ARR_SIZE;
    }
    printf("\n");
}