LeetCode 622: Design Circular queues
Let’s start with the queue data structure:
Queue: First-in, first-out data structure
In a FIFO data structure, the first element added to the queue is processed first.
As shown in the figure above, queues are typical FIFO data structures. An INSERT operation is also called an enqueue. New elements are always added to the end of the queue. A delete operation is also called a dequeue. You can only remove the first element.
Queue – Implementation
To implement queues, we can use dynamic arrays and indexes that point to the head of the queue.
As mentioned above, queues should support two operations: enqueue and enqueue. Joining the queue appends a new element to the queue, while exiting the queue removes the first element. So we need an index to indicate the starting point.
Circular queue
Previously, we provided a simple but inefficient implementation of queues.
A more efficient approach is to use circular queues. Specifically, we can use a fixed-size array and two Pointers to indicate the start and end positions. The goal is to reuse the wasted storage we mentioned earlier.
Let’s take a look at how circular queues work with an example. You should pay attention to the strategy we use for joining or leaving the team elements.
[img-sculotla-1564547660610)(queue.gif)]
Go through the animation for the strategy we use to check whether the queue is empty or full.
The above content is from Likou China, the content has changed
Topic: Designing loop queues:
Design your loop 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:
MyCircularQueue(k): constructor that sets the queue length to k.Front: Get elements from team leader. If the queue is empty, -1 is returned.Rear: Gets the last element of the queue. If the queue is empty, -1 is returned.enQueue(value): Inserts an element into the loop queue. Return true on successful insertion.deQueue(): Removes an element from the loop queue. Return true if deleted successfully.isEmpty(): Checks whether the loop queue is empty.isFull(): Checks whether the loop queue is full.
Example:
MyCircularQueue circularQueue = new MycircularQueue(3); Circularqueue.enqueue (1); // Set the length to 3 circularqueue.enqueue (1); / / returntruecircularQueue.enQueue(2); / / returntruecircularQueue.enQueue(3); / / returntruecircularQueue.enQueue(4); / / returnfalse, queue full circularqueue.rear (); Circularqueue.isfull (); / / returntruecircularQueue.deQueue(); / / returntruecircularQueue.enQueue(4); / / returntruecircularQueue.Rear(); / / return 4Copy the codeTip:
- All values are in the range 0 to 1000;
- Operands will be in the range 1 to 1000;
- Do not use the built-in queue library.
Answer:
Most high-level programming languages have built-in queue libraries, which can be easily referenced. In the loop queue, we use an array and two Pointers (head and tail). Head indicates the start position of the queue, and tail indicates the end position of the queue.
class MyCircularQueue {
private int[] data;
private int head;
private int tail;
private int size;
/** Initializes the data structure and specifies the queue size k */
public MyCircularQueue(int k) {
data = new int[k];
head = -1;
tail = -1;
size = k;
}
/** Inserts an entry into the queue and returns whether the insertion was successful */
public boolean enQueue(int value) {
if (isFull() == true) {
return false;
}
if (isEmpty() == true) {
head = 0;
}
tail = (tail + 1) % size;
data[tail] = value;
return true;
}
/** Deletes an item from the queue and returns whether the deletion succeeded */
public boolean deQueue(a) {
if (isEmpty() == true) {
return false;
}
if (head == tail) {
head = -1;
tail = -1;
return true;
}
head = (head + 1) % size;
return true;
}
/** gets the first item in the queue */
public int Front(a) {
if (isEmpty() == true) {
return -1;
}
return data[head];
}
/** gets the last item in the queue */
public int Rear(a) {
if (isEmpty() == true) {
return -1;
}
return data[tail];
}
/** Check if the queue is empty */
public boolean isEmpty(a) {
return head == -1;
}
/** Check whether the queue is full */
public boolean isFull(a) {
return ((tail + 1) % size) == head; }}Copy the codePython3:
class MyCircularQueue(a):
def __init__(self, k: int):
""" Initializes the data structure and specifies the queue size k ""
self.size = k
self.queue = [' ']*k
self.head = - 1
self.tail = - 1
def enQueue(self, value: int) -> bool:
Inserts an item into the queue and returns whether the insertion was successful.
if not self.isFull():
if self.head == - 1:
self.head = 0
self.tail = (self.tail+1)%self.size
self.queue[self.tail] = value
return True
else:
return False
def deQueue(self) -> bool:
""" Deletes an item from the queue and returns whether the deletion was successful """
if not self.isEmpty():
if self.head ==self.tail:
self.head,self.tail = - 1.- 1
else:
self.head = (self.head+1)%self.size
return True
else:
return False
def Front(self) -> int:
""" Get the first item in the queue ""
if self.isEmpty():
return - 1
else:
return self.queue[self.head]
def Rear(self) -> int:
""" Gets the last item in the queue """
if self.isEmpty():
return - 1
else:
return self.queue[self.tail]
def isEmpty(self) -> bool:
""" Check if the queue is empty ""
return self.head == - 1 and self.tail == - 1
def isFull(self) -> bool:
""" Check if the queue is full. ""
return (self.tail+1)%self.size ==self.head
Copy the code