Algorithms 101: Circular Queue Implementation Using Array

环形队列用数组实现 Circular Queue Implementation Using Array

A circular queue is a more efficient implementation of a queue using an array, where the end of the array wraps around to the beginning. This avoids the need to shift elements and allows the queue to efficiently utilize space. Unlike a traditional linear queue, where the rear pointer simply moves to the next array index, a circular queue allows the rear pointer to loop back to the start of the array when it reaches the end, provided there is space.

环形队列是一种更高效的队列实现方式，使用数组，其中数组的末尾环绕到开头。这避免了需要移动元素，并允许队列有效利用空间。与传统的线性队列不同，在传统队列中，尾指针只会移动到数组的下一个索引，而在环形队列中，当尾指针到达末尾时，如果有空间，它可以循环回到数组的开头。

实现代码

Implementation Code

class CircularQueue:
    def __init__(self, k):
        self.queue = [None] * k
        self.max_size = k
        self.front = 0
        self.rear = 0
        self.size = 0

    def enqueue(self, value):
        if self.is_full():
            return False  # Queue is full, cannot enqueue
        self.queue[self.rear] = value
        self.rear = (self.rear + 1) % self.max_size
        self.size += 1
        return True

    def dequeue(self):
        if self.is_empty():
            return None  # Queue is empty, cannot dequeue
        value = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.max_size
        self.size -= 1
        return value

    def peek(self):
        if self.is_empty():
            return None  # Queue is empty
        return self.queue[self.front]

    def is_empty(self):
        return self.size == 0

    def is_full(self):
        return self.size == self.max_size

解释

Explanation

1. CircularQueue Class

CircularQueue 类

The CircularQueue class implements a queue using a fixed-size array and maintains a circular structure through the use of modulo arithmetic (%). This class keeps track of the queue’s front and rear positions, as well as its current size.

CircularQueue 类使用固定大小的数组实现了一个队列，并通过模运算 (%) 维护其环形结构。该类跟踪队列的前端和后端位置，以及其当前大小。

2. enqueue(value): Adds an Element to the Rear of the Queue

enqueue(value)：将元素添加到队列的后端

The enqueue method adds an element to the position indicated by the rear pointer. After inserting the element, the rear pointer is incremented by one and wraps around to the beginning of the array if it reaches the end (using the modulo operation). If the queue is full (is_full() returns True), the operation fails.

enqueue 方法将元素添加到 rear 指针所指示的位置。插入元素后，rear 指针增加一，并在到达数组末尾时环绕回到数组的开头（使用模运算）。如果队列已满（is_full() 返回 True），则操作失败。

cq = CircularQueue(5)
cq.enqueue(10)  # Enqueue 10
cq.enqueue(20)  # Enqueue 20

3. dequeue(): Removes the Front Element from the Queue

dequeue()：从队列前端移除元素

The dequeue method removes and returns the element at the position indicated by the front pointer. After removing the element, the front pointer is incremented by one and wraps around to the beginning of the array if it reaches the end. If the queue is empty (is_empty() returns True), the operation returns None.

dequeue 方法移除并返回 front 指针所指示位置的元素。移除元素后，front 指针增加一，并在到达数组末尾时环绕回到数组的开头。如果队列为空（is_empty() 返回 True），则操作返回 None。

front_element = cq.dequeue()  # Dequeue the front element (10)

4. peek(): Retrieves the Front Element Without Removing It

peek()：检索队列前端的元素但不移除

The peek method allows you to view the element at the front of the queue without removing it. This is useful when you need to check the next item to be processed without altering the queue’s structure. If the queue is empty, the method returns None.

peek 方法允许您查看队列前端的元素而不移除它。当您需要检查下一个将要处理的项目而不改变队列结构时，此方法非常有用。如果队列为空，则该方法返回 None。

front_element = cq.peek()  # Peek at the front element (20)

5. is_empty(): Checks If the Queue Is Empty

is_empty()：检查队列是否为空

The is_empty method checks whether the queue contains any elements. This is important for preventing errors when attempting to dequeue or peek from an empty queue.

is_empty 方法检查队列中是否包含任何元素。这对于防止在尝试从空队列 dequeue 或 peek 时出现错误非常重要。

empty_check = cq.is_empty()  # Check if the queue is empty (False)

6. is_full(): Checks If the Queue Is Full

is_full()：检查队列是否已满

The is_full method checks whether the queue has reached its maximum capacity. This is crucial for preventing errors when attempting to enqueue into a full queue.

is_full 方法检查队列是否已达到其最大容量。这对于防止在尝试向满队列 enqueue 时出现错误至关重要。

full_check = cq.is_full()  # Check if the queue is full (False)

环形队列的优缺点

Advantages and Disadvantages of Circular Queue

优点

Advantages

高效利用空间：环形队列避免了数组实现队列时在 dequeue 操作中移动元素的问题，从而更高效地利用数组空间。
固定大小：环形队列具有固定大小，适合内存受限的应用场景。
避免溢出：环形队列利用环绕结构，可以避免在添加元素时出现溢出问题。
Efficient Space Utilization: Circular queues avoid the issue of shifting elements during the dequeue operation in an array implementation, making better use of the array’s space.
Fixed Size: Circular queues have a fixed size, making them suitable for memory-constrained applications.
Overflow Prevention: Circular queues use a wrap-around structure to prevent overflow issues when adding elements.

缺点

Disadvantages

固定大小限制：尽管环形队列避免了移动元素的问题，但其固定大小仍然可能导致溢出。
实现复杂性：相对于简单的线性队列，环形队列的实现稍微复杂一些。
Fixed Size Limitation: Despite avoiding the shifting issue, the fixed size of circular queues can still lead to overflow.
Complexity: The implementation of circular queues is slightly more complex compared to simple linear queues.

总结

Conclusion

A circular queue is a more efficient and space-conscious implementation of a queue using an array. It avoids the need to shift elements by wrapping around the end of the array to the beginning. This makes it ideal for scenarios where a fixed-size, efficient queue is needed, such as in resource-constrained environments or systems requiring predictable performance.

环形队列是一种更高效、更节省空间的队列实现方式，使用数组，并通过环绕结构避免移动元素的需要。这使其非常适合需要固定大小、高效队列的场景，如资源受限的环境或需要可预测性能的系统。

Post Views: 21

CODEBITWAVE