Sponsored
Sponsored
This approach utilizes a fixed-size array along with two pointers (or indices), front and rear, to maintain the positions within the queue effectively. The idea revolves around using modular arithmetic to effectively wrap around the queue once the end of the array is reached.
Operations like enQueue and deQueue are performed using these pointers, and conditions such as when the queue is full or empty are checked based on the relative position of these pointers.
The time complexity for each operation such as enQueue, deQueue, Front, and Rear is O(1) as they involve simple arithmetic operations. The space complexity is O(k) where k is the size of the queue since we're using a static array.
1class MyCircularQueue:
2 def __init__(self, k: int):
3 self.queue = [0] * k
4 self.front = 0
This Python solution implements the circular queue using a list. The queue is initialized with a fixed size [0] * k. The enQueue method adds values, and deQueue removes them, both utilizing modular arithmetic to wrap around. Methods Front and Rear return the first and last elements, respectively.
This approach employs a circular linked list to implement the queue, leveraging linked nodes instead of a fixed-size array. The circular nature simplifies the wrap-around, allowing operations with dynamic sizing. Each node in the list holds a value and a reference to the next node, with the last node pointing back to the first, forming a circle.
Such a design accommodates flexible sizing but adds complexity in managing node references for enQueue and deQueue.
The time complexity for each operation is O(1) since they only involve rearranging node pointers. The space complexity is O(k) in the worst case if all queue slots are occupied.
class Node {
public:
int value;
Node* next;
Node(int val) : value(val), next(nullptr) {}
};
class MyCircularQueue {
private:
Node* front;
Node* rear;
int maxSize;
int curSize;
public:
MyCircularQueue(int k) : front(nullptr), rear(nullptr), maxSize(k), curSize(0) {}
bool enQueue(int value) {
if (isFull()) return false;
Node* newNode = new Node(value);
if (curSize == 0) {
front = rear = newNode;
rear->next = front;
} else {
rear->next = newNode;
rear = newNode;
rear->next = front;
}
curSize++;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
if (front == rear) {
delete front;
front = rear = nullptr;
} else {
Node* temp = front;
front = front->next;
rear->next = front;
delete temp;
}
curSize--;
return true;
}
int Front() {
if (isEmpty()) return -1;
return front->value;
}
int Rear() {
if (isEmpty()) return -1;
return rear->value;
}
bool isEmpty() {
return curSize == 0;
}
bool isFull() {
return curSize == maxSize;
}
};This C++ implementation uses a class for nodes with attributes for value and pointer. The main class MyCircularQueue manages the circular linked list where node pointers are linked in a circle. This changes dynamically, overcoming the fixed-size limitation of arrays. Careful node pointer updates ensure act of enQueue and deQueue operations.