“This is the 11th day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”
📝 Description: Design your circular queue implementation. A circular queue is a linear data structure that operates on a FIFO (first-in, first-out) basis and the tail of the queue is connected behind the head of the queue to form a loop. It is also known as a “ring buffer”. One of the nice things about a circular queue is that we can use the space that the queue has previously used. In a normal queue, once a queue is full, we cannot insert the next element, even though there is still space in front of the queue. But with circular queues, we can use that space to store new values.
Your implementation should support the following:
1️ MyCircularQueue(k): constructor, set queue length as K.
2️ Front: element acquisition from team head. If the queue is empty, -1 is returned.
3️ Rear: Acquiring the Rear element of the team. If the queue is empty, -1 is returned.
4️ discount queue (value): insert an element into the circular queue. Return true on successful insertion.
5️ deQueue(): remove an element from the circular queue. Return true if deleted successfully.
6️ isEmpty(): check whether the circular queue isEmpty.
7️ isFull(): check whether the circulation queue isFull.
💨 example:
MyCircularQueue circularQueue = new MyCircularQueue(3); // Set the length to 3
circularQueue.enQueue(1); / / return true
circularQueue.enQueue(2); / / return true
circularQueue.enQueue(3); / / return true
circularQueue.enQueue(4); // Return false, the queue is full
circularQueue.Rear(); / / return 3
circularQueue.isFull(); / / return true
circularQueue.deQueue(); / / return true
circularQueue.enQueue(4); / / return true
circularQueue.Rear(); / / return 4
🍳 prompt
1 all values of ️ are in the range of 0 to 1000;
2️ operation will be in the range of 1 to 1000;
3️ please do not use the built-in queue library.
🧷 Platform: Visual Studio 2017 && Windows
🔑 Core Idea:
The first question is whether to use arrays or linked lists ❔❓
Both arrays and linked lists work here, but arrays are more cache efficient, and linked lists (single-linked lists) can be pretty gross to implement some interfacesCopy the codeHow do arrays and lists form rings ❔❓
1) We need two Pointers: head to index 0 and tail to index 3Copy the code
2. Make the last node of the list point not to empty, but to the first nodeCopy the code
How to judge full and unsatisfied, empty and not empty? The head and tail both point to the starting position at the beginning, indicating empty. When the last space is inserted, tail returns to the starting position, indicating that it is full. This creates a contradiction) ❔❓
Either an array or a linked list gives you an extra space. Null if tail == head; If tail + 1 == head is fullCopy the code
Leetcode the original
typedef struct {
int* a;// Point to the open space
int front;/ / the first
int rear;/ / the end
int k; // Record the current number of valid data
} MyCircularQueue;
// Create space
MyCircularQueue* myCircularQueueCreate(int k) {
// Malloc a space of type MyCircularQueue
MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
// malloc specifies k int Spaces (note that an extra space is required)
q->a = (int*)malloc(sizeof(int) * (k + 1));
/ / initialization
q->front = 0;
q->rear = 0;
q->k = k;
// Returns the address of the structure
return q;
}
/ / found empty
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
assert(obj);
When front equals rear, the queue is empty
return obj->front == obj->rear;
}
/ / to full
bool myCircularQueueIsFull(MyCircularQueue* obj) {
assert(obj);
// Full when front equals rear+1 (but prevent rear+1 from crossing the line)
return (obj->rear + 1) % (obj->k + 1) == obj->front;
}
// Insert data - returns false if it cannot be inserted and true if it can
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
assert(obj);
MyCircularQueueIsFull determines whether the queue is full
// Full, return true
if(myCircularQueueIsFull(obj))
return false;
// If no, insert data
obj->a[obj->rear] = value;
obj->rear++;
Rear++ is out of bounds when the last space of the array is inserted
if(obj->rear == obj->k+1)
obj->rear = 0;
// At this point, return true
return true;
}
Delete data - False if it cannot be deleted, true if it can be deleted
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
assert(obj);
//myCircularQueueIsEmpty determines whether the queue is empty
// Empty, return true,
if(myCircularQueueIsEmpty(obj))
return false;
// If front is not empty, delete the data.
obj->front++;
// front++ is out of bounds when the last space of the array is deleted
if(obj->front == obj->k+1)
obj->front = 0;
// At this point, return true
return true;
}
// Get the queue head data
int myCircularQueueFront(MyCircularQueue* obj) {
assert(obj);
// Return -1 if the queue is empty
if(myCircularQueueIsEmpty(obj))
return - 1;
// return to queue head
return obj->a[obj->front];
}
// Get the data at the end of the queue
int myCircularQueueRear(MyCircularQueue* obj) {
assert(obj);
// Return -1 if the queue is empty
if(myCircularQueueIsEmpty(obj))
return - 1;
MyCircularQueueEnQueue tail++ = tail
//prevRear records the previous one
int prevRear = obj->rear - 1;
PrevRear is k when rear is the space with subscript 0
if(obj->rear == 0)
prevRear = obj->k;
// return to the end of the queue
return obj->a[prevRear];
}
// Reclaim space
void myCircularQueueFree(MyCircularQueue* obj) {
assert(obj);
// In the above code we malloc the space twice, first recycling the space of the members of the structure, and then recycling the structure
free(obj->a);
free(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); * /.Copy the code