【データ構造】設計サイクルキュー

要件:ループキュー実装を設計します.ループキューは線形データ構造であり、その動作表現はFIFO(先進先出)の原則に基づいており、キューの最後がキューの先頭に接続されてループを形成する.「リングバッファ」とも呼ばれる. ループキューの利点の1つは、このキューが以前に使用した空間を利用できることです.通常のキューでは、キューがいっぱいになると、キューの前にスペースがあっても次の要素を挿入できません.しかし、ループキューを使用すると、これらのスペースを使用して新しい値を格納することができます.あなたの実装は、次の操作をサポートする必要があります.

MyCircularQueue(k):コンストラクタで、キュー長をkに設定します.

Front:キューヘッダから要素を取得します.キューが空の場合は、-1を返します.

Rear:キューの末尾要素を取得します.キューが空の場合は、-1を返します.

enQueue(value):ループキューに要素を挿入します.挿入に成功した場合は真を返します.

deQueue():ループキューから要素を削除します.削除に成功した場合は、真を返します.

isEmpty():ループキューが空であるかどうかを確認します.

isFull():ループキューがいっぱいかどうかを確認します.

分析:
本来ならば、キューはチェーンテーブルで完成するのに適していますが、ループキューを設計するには、空か満かを区別するための空間を残しなければならないという問題に注意します.実現時にチェーンテーブルを使うなら、新しいノードを開くなど、面倒なので、ループ対列は配列で実現するのに適しています.実装コードは次のとおりです.

typedef struct {
    int* queue;
    int front;
    int rear;
    int k;
} MyCircularQueue;

/** Initialize your data structure here. Set the size of the queue to be k. */
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* pcq=( MyCircularQueue*)malloc(sizeof( MyCircularQueue));
    pcq->queue=(int*)malloc(sizeof(int)*(k+1));
    pcq->front=0;
    pcq->rear=0;
    pcq->k=k;
    return pcq;
}

/** Insert an element into the circular queue. Return true if the operation is successful. */
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
   if((obj->rear+1)%(obj->k+1)==obj->front)//                  
   {
       return false;
   }
    obj->queue[obj->rear]=value;
    obj->rear++;
    if(obj->rear==obj->k+1)
    {
        obj->rear=0;
    }
    return true;
}

/** Delete an element from the circular queue. Return true if the operation is successful. */
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    
    if(obj->front==obj->rear)//   
    {
        return false;
    }
    obj->front++;//  
    if(obj->front==obj->k+1)// front  k+1 ， front  0，      
    {
        obj->front=0;
    }
     return true;
}

/** Get the front item from the queue. */
int myCircularQueueFront(MyCircularQueue* obj) {
   if(obj->front==obj->rear)
   {
       return -1;
   }
    else
    {
        return obj->queue[obj->front];
    }
}

/** Get the last item from the queue. */
int myCircularQueueRear(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
   {
       return -1;
   }
    if(obj->rear==0)
    {
        return obj->queue[obj->k];
    } 
    else
    {
        return obj->queue[obj->rear-1];
    }
 
}

/** Checks whether the circular queue is empty or not. */
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/** Checks whether the circular queue is full or not. */
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%(obj->k+1)==obj->front)
    {
        return true;
    }
    else
    {
        return false;
    }
    
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->queue);
    obj->queue=NULL;
    free(obj);    
}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * struct MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 * bool param_2 = myCircularQueueDeQueue(obj);
 * int param_3 = myCircularQueueFront(obj);
 * int param_4 = myCircularQueueRear(obj);
 * bool param_5 = myCircularQueueIsEmpty(obj);
 * bool param_6 = myCircularQueueIsFull(obj);
 * myCircularQueueFree(obj);
 */