数组实现循环队列

循环队列作为一种常用的数据结构，它使头尾指针能够灵活的在容器头尾跳跃，实现循环存取的结构。线性队列，在不移动元素的情况下，随着数据的不断读写，会出现假上溢的情况（当尾部指针已经到了容器底部，线性队列就无法插入了，尽管存在已出队列的可以空间，），导致已出队列的可用空间无法再被利用。另外循环队列很适合作为缓存的处理。

//
//  CycleQueue.m
//  CycleQueue
//
//  Created by zengbailiang on 2018/5/8.
//  Copyright © 2018年 zengbailiang. All rights reserved.
//  循环队列

#import "CycleQueue.h"

#define CYCLE_QUEUE_MAX_SIZE 10
#define CYCLE_QUEUE_ELEMENT int

typedef struct kSCycleQueue
{
    CYCLE_QUEUE_ELEMENT data[CYCLE_QUEUE_MAX_SIZE];
    int fornt ,rear;
}*SCycleQueue;

@implementation CycleQueue

int queueInit(SCycleQueue *queue)
{
    if ((*queue) == NULL) {
        (*queue) = (SCycleQueue)malloc(sizeof(struct kSCycleQueue));
        //初始化队列头和队列尾部，队列尾初始化为-1是为了添加原始的时候统一操作为后移
        (*queue)->fornt = 0;
        (*queue)->rear = -1;
    }
    else
    {
        return -1;
    }
    return 1;
}

bool canAdd(SCycleQueue *queue)
{
    if((*queue) == NULL
       ||(*queue)->fornt + (*queue) ->rear + 1 == CYCLE_QUEUE_MAX_SIZE
       ||((*queue)->rear != -1 &&  (*queue)->rear + 1 == (*queue)->fornt))
    {
        return false;
    }
    else
    {
        return true;
    }
}

int add(SCycleQueue *queue,CYCLE_QUEUE_ELEMENT e)
{
    if (canAdd(queue)) {
        //如果已经是在最后一个原始，那么跳到第0个原始添加，实现循环
        if ((*queue) -> rear == CYCLE_QUEUE_MAX_SIZE - 1) {
            (*queue) -> rear = 0;
        }
        else
        {
            //非最后一个元素后移即可
            (*queue) -> rear += 1;
        }
        //队尾添加元素
        (*queue) ->data[(*queue) ->rear] = e;
        return 1;
    }
    else
    {
        return 0;
    }
    
}

int delete(SCycleQueue *queue,CYCLE_QUEUE_ELEMENT *e)
{
    if ((*queue) == NULL) {
        return  -1;
    }
    //如果rear不等于-1就代表存在元素
    else if((*queue)->fornt == 0 && (*queue)->rear == -1)
    {
        return 0;
    }
    else
    {
        (*e) = (*queue)->data[(*queue)->fornt];
        (*queue)->data[(*queue)->fornt] = -1;
        //如果 fornt == rear，代表最后一个元素了，这个时候把标记复位用于上面的判断。
        if ((*queue)->fornt == (*queue)->rear) {
            (*queue)->fornt = 0;
            (*queue)->rear = -1;
        }
        else if((*queue)->fornt == CYCLE_QUEUE_MAX_SIZE - 1)
        {
            //如果是最后一个元素出队列，那么队列头跳到容器第一个元素实现循环出队列
            (*queue)->fornt = 0;
        }
        else
        {
            (*queue)->fornt += 1;
        }
      return 1;
    }
}

+ (void)testt
{
    test();
    test1();
    test2();
}

void test()
{
    SCycleQueue queue;
    queueInit(&queue);
    add(&queue, 0);
    add(&queue, 1);
    add(&queue, 2);
    add(&queue, 3);
    add(&queue, 4);
    add(&queue, 5);
    add(&queue, 6);
    add(&queue, 7);
    add(&queue, 8);
    add(&queue, 9);//加满
    CYCLE_QUEUE_ELEMENT e;
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    add(&queue, 10);//容器底部已满，循环到头部开始添加
    add(&queue, 11);
    add(&queue, 12);
    add(&queue, 13);
    add(&queue, 14);
}
void test1()
{
    SCycleQueue queue;
    queueInit(&queue);
    add(&queue, 0);
    add(&queue, 1);
    add(&queue, 2);
    add(&queue, 3);
    add(&queue, 4);
    add(&queue, 5);
    add(&queue, 6);
    add(&queue, 7);
    add(&queue, 8);
    add(&queue, 9);
    CYCLE_QUEUE_ELEMENT e;
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);//全部出队列，标记复位
    delete(&queue, &e);
    add(&queue, 6);
    add(&queue, 7);
    add(&queue, 8);
    add(&queue, 9);
}

void test2()
{
    SCycleQueue queue;
    queueInit(&queue);
    add(&queue, 0);
    add(&queue, 1);
    add(&queue, 2);
    add(&queue, 3);
    add(&queue, 4);
    add(&queue, 5);
    add(&queue, 6);
    add(&queue, 7);
    add(&queue, 8);
    add(&queue, 9);
    CYCLE_QUEUE_ELEMENT e;
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);//font = 5
    add(&queue, 15);
    add(&queue, 16);
    add(&queue, 11);
    add(&queue, 12);
    add(&queue, 13);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);//循环到容器头出队列
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
    delete(&queue, &e);
}

@end