关于数据结构与算法:Circular-Queue-顺序存储和链式存储结构实现循环队列

队列的程序、链式存储构造实现

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”.

题目作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetb…
题解作者:WildDuck

顺序存储构造的实现形式

struct MyCircularQueue{
    int front;
    int tail;
    int Max_size;
    int* data;
};

typedef struct MyCircularQueue MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue* head =(MyCircularQueue*)malloc(sizeof(struct MyCircularQueue));
    head->data = (int*)malloc(sizeof(int)*(k+1));
    head->front = 0;
    head->tail = 0;
    head->Max_size = k+1;
    return head;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{if(obj->front == obj->tail)
    {return true;}
    else return false;

}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{if((obj->tail+1)%obj->Max_size == obj->front)
    {return true;}
    else return false;

}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj) == false)
    {obj->data[obj->tail] =  value;
        obj->tail = (obj->tail+1)%obj->Max_size;
        return true;
    }
    else return false;

}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj) == false)
    {obj->data[obj->front] =  -1;
        obj->front = (obj->front+1)%obj->Max_size;
        return true;
    }
    else return false;

}

int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj) == false)
    {return obj->data[obj->front];
    }
    else return -1;
    
}

int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj) == false)
    {if(obj->tail-1 >= 0)
        {return obj->data[obj->tail-1];
        }
        else return obj->data[obj->Max_size-1];
    }
    else return -1;
}




void myCircularQueueFree(MyCircularQueue* obj) {

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * 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);
*/

链式存储构造实现

struct Linklist
{
    int data;
    struct Linklist* next;
};
typedef struct Linklist* Linklist_pointer;

typedef struct {
    int Max_length;
    int current_length;
    Linklist_pointer front;
    Linklist_pointer rear;
} MyCircularQueue;


bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{if (obj->current_length == 0)
    {return true;}
    else return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{if (obj->current_length == obj->Max_length)
    {return true;}
    else return false;
}

MyCircularQueue* myCircularQueueCreate(int k)
{MyCircularQueue* record = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    record->Max_length = k;
    record->current_length = 0;
    record->front = NULL;
    record->rear = NULL;
    
    Linklist_pointer head = (Linklist_pointer)malloc(sizeof(struct Linklist));
    record->front = head;
    record->rear = head;
    
    return record;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value)
{if(myCircularQueueIsFull(obj) == false)
    {Linklist_pointer new_elem = (Linklist_pointer)malloc(sizeof(struct Linklist));
        new_elem -> data = value;
        new_elem -> next = NULL;
    
        obj->rear->next = new_elem;
        obj->rear = new_elem;
        obj->current_length = obj->current_length +1;
        return true;
    }
    return false;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj) == false)
    {
        Linklist_pointer temp_pointer = obj->front->next;
        obj->front->next = obj->front->next->next;
        obj->current_length = obj->current_length -1;
        if(myCircularQueueIsEmpty(obj) == true)// 删除过后队列为空，须要解决 rear 指针的指向
        {obj->rear = obj->front;}
        free(temp_pointer);
        return true;
    }
    return false;
}

int myCircularQueueFront(MyCircularQueue* obj)
{if(myCircularQueueIsEmpty(obj) == false)
    {return obj->front->next->data;}
    return -1;
}

int myCircularQueueRear(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj) == false)
    {return obj->rear->data;}
    return -1;
}





void myCircularQueueFree(MyCircularQueue* obj) {

}

/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * 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);
*/