“This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021”

Design loop queue

The title

image-20211103204637814


We’re going to use a queue called a loop queue. If you look at the producer consumer model in an operating system class, you’ll use circular queues. Circular queues can be implemented using arrays or circular linked lists.

image-20211103204617520


image-20211103230000226


The tail of a team is the tail of a team

Array (loop through subscript control)


Ring queue structure (array)

typedef struct {
    int* a;
    int front;
    int tail;
    int k;// Array element (queue length)
} MyCircularQueue;
Copy the code

The loop team is initialized

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc(sizeof(int)*(k+1));// The queue length is k and we need to open one more queue
    q->front = q->tail = 0;
    q->k = k;
    return q;
}
Copy the code

Check that the loop is empty

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->tail;
}
Copy the code

Judge the ring group to be full

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1) == obj->front;
}
Copy the code

Loop entry data merge returns true on success

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(! myCircularQueueIsFull(obj)) { obj->a[obj->tail] = value;// if the queue is full, index tail to value
        obj->tail++;
        obj->tail %= obj->k+1;//tail just steps one bit
        return true;
    }
    return false;// The line is full and there is no room for it
}
Copy the code

Returns true if the loop deleted data and succeeded

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) { obj->front++;// If the queue is not empty, it is out of the queue
        obj->front %= obj->k+1;
        return true;
    }
    return false;// You can't delete it when it is empty
}
Copy the code

Loop fetch header data (return -1 for null)

int myCircularQueueFront(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) {return obj->a[obj->front]; // Select * from front
    }
    return - 1;
}
Copy the code

Ring team fetch the tail data (return -1 for null)

int myCircularQueueRear(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) {return obj->a[obj->tail == 0 ? obj->k : obj->tail- 1];// select * from 'k' where 'k' = 0
    }
    return - 1;
}
Copy the code

Ring team destroyed

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a = NULL;
    obj->front = 0;
    obj->tail = 0;
    obj->k = 0;
    free(obj);
}
Copy the code
image-20211104220502511


image-20211104220526761


Loop array (array implementation)

typedef struct {
    int* a;
    int front;
    int tail;
    int k;// Array element (queue length)
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc(sizeof(int)*(k+1));// The queue length is k and we need to open one more queue
    q->front = q->tail = 0;
    q->k = k;
    return q;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(! myCircularQueueIsFull(obj)) { obj->a[obj->tail] = value;// if the queue is full, index tail to value
        obj->tail++;
        obj->tail %= obj->k+1;//tail just steps one bit
        return true;
    }
    return false;// The line is full and there is no room for it
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) { obj->front++;// If the queue is not empty, it is out of the queue
        obj->front %= obj->k+1;
        return true;
    }
    return false;// You can't delete it when it is empty
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) {return obj->a[obj->front]; // Select * from front
    }
    return - 1;
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(! myCircularQueueIsEmpty(obj)) {return obj->a[obj->tail == 0 ? obj->k : obj->tail- 1];// select * from 'k' where 'k' = 0
    }
    return - 1;
}

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

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->tail+1)%(obj->k+1) == obj->front;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    obj->a = NULL;
    obj->front = 0;
    obj->tail = 0;
    obj->k = 0;
    free(obj);
}
Copy the code

The list form


Ring team structure (linked list)

typedef int CQDataType;// Loop group data type

typedef struct CQNode
{
    CQDataType x;// Loop node data
    struct CQNode* next;// Ring queue node pointer
}CQNode;

typedef struct {
    CQNode* head;
    CQNode* tail;
    int k;
} MyCircularQueue;// Empty ring team has two bare Pointers
Copy the code

The loop team is initialized

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
    cq->k = k;
    cq->head = cq->tail = cur;
    while(k--)
    {
        CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
        CQNode* tail = cq->tail;// The last node
	    tail->next = newnode;// The last node points to the new node
	    newnode->next = cq->head;// The new node points to the head node
        cq->tail=newnode;
    }
    cq->head = cq->tail;
    return cq;
}
Copy the code

Check that the loop is empty

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->head == obj->tail;
}
Copy the code

Judge the ring group to be full

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->tail->next == obj->head;
}
Copy the code

Loop entry data merge returns true on success

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsFull(obj)) { obj->tail->x = value; obj->tail = obj->tail->next;return true;
    }
    return false;
}
Copy the code

Returns true if the loop deleted data and succeeded

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj)) { obj->head = obj->head->next;return true;
    }
    return false;
}
Copy the code

Loop fetch header data (return -1 for null)

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj))return obj->head->x;
    return - 1;
}
Copy the code

Ring team fetch the tail data (return -1 for null)

int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj)) { CQNode*ret=obj->head;while(ret->next! =obj->tail) { ret=ret->next; }return ret->x;
    }
    return - 1;    
}
Copy the code

Ring team destroyed

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    while(obj->head! =obj->tail) { CQNode*ret=obj->tail; obj->tail=obj->tail->next;free(ret);
    }
    free(obj->head);
    free(obj);
}
Copy the code
image-20211105064130129


Loop team (linked list implementation)

typedef int CQDataType;// Loop group data type

typedef struct CQNode
{
    CQDataType x;// Loop node data
    struct CQNode* next;// Ring queue node pointer
}CQNode;

typedef struct {
    CQNode* head;
    CQNode* tail;
    int k;
} MyCircularQueue;// Empty ring team has two bare Pointers

bool myCircularQueueIsEmpty(MyCircularQueue* obj);
bool myCircularQueueIsFull(MyCircularQueue* obj);


MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* cq = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    CQNode* cur = (CQNode*)malloc(sizeof(CQNode));
    cq->k = k;
    cq->head = cq->tail = cur;
    while(k--)
    {
        CQNode* newnode = (CQNode*)malloc(sizeof(CQNode));
        CQNode* tail = cq->tail;// The last node
	    tail->next = newnode;// The last node points to the new node
	    newnode->next = cq->head;// The new node points to the head node
        cq->tail=newnode;
    }
    cq->head = cq->tail;
    return cq;
}


bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsFull(obj)) { obj->tail->x = value; obj->tail = obj->tail->next;return true;
    }
    return false;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj)) { obj->head = obj->head->next;return true;
    }
    return false;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj))return obj->head->x;
    return - 1;
}

/*int myCircularQueueRear(MyCircularQueue* obj) { assert(obj->head && obj->tail); if(! myCircularQueueIsEmpty(obj)) { CQNode* ret = obj->head; While (--obj->k) {obj->tail = obj->tail->next; } ret = obj->tail; obj->tail = obj->tail->next; return obj->tail->x; } return -1; } * /
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    if(! myCircularQueueIsEmpty(obj)) { CQNode*ret=obj->head;while(ret->next! =obj->tail) { ret=ret->next; }return ret->x;
    }
    return - 1;    
}


bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->head == obj->tail;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    return obj->tail->next == obj->head;
}

void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj->head && obj->tail);
    while(obj->head! =obj->tail) { CQNode*ret=obj->tail; obj->tail=obj->tail->next;free(ret);
    }
    free(obj->head);
    free(obj);
}
Copy the code

Actually, I made a mistake on this one. I don’t want to find it. It’s disgusting.

img