Algorithms 101: Deque Implementation Using Fixed Array

Deque Implementation Using Fixed Array (双端队列用固定数组的实现)

Implementing a deque using a fixed-size array is another efficient method that provides constant-time access to elements and operations at both ends of the deque. This approach, however, requires handling the circular nature of the deque when the array is full or when operations cause the front or rear indices to wrap around the end of the array.

使用固定大小的数组实现双端队列是另一种高效的方法，它可以在双端队列的两端进行常数时间的元素访问和操作。然而，这种方法需要处理数组满时或操作导致前端或后端索引绕过数组末端时的环绕问题。

Structure of the Deque Class (双端队列类的结构):

The Deque class for a fixed array implementation manages an array of a fixed size, along with pointers (front and rear) and a size counter. These help in efficiently performing operations while maintaining the circular nature of the deque.

用于固定数组实现的 Deque 类管理一个固定大小的数组，以及指针（front 和 rear）和大小计数器。这些帮助高效地执行操作，同时保持双端队列的循环特性。

class Deque:
    def __init__(self, capacity):
        self.capacity = capacity
        self.array = [None] * capacity
        self.front = -1
        self.rear = 0
        self.size = 0

    def isFull(self):
        return self.size == self.capacity

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

    def insertFront(self, data):
        if self.isFull():
            return "Deque is full"

        if self.front == -1:  # Empty deque
            self.front = self.rear = 0
        else:
            self.front = (self.front - 1) % self.capacity

        self.array[self.front] = data
        self.size += 1

    def insertLast(self, data):
        if self.isFull():
            return "Deque is full"

        if self.front == -1:  # Empty deque
            self.front = self.rear = 0
        else:
            self.rear = (self.rear + 1) % self.capacity

        self.array[self.rear] = data
        self.size += 1

    def deleteFront(self):
        if self.isEmpty():
            return "Deque is empty"

        data = self.array[self.front]
        if self.front == self.rear:  # Deque has only one element
            self.front = self.rear = -1
        else:
            self.front = (self.front + 1) % self.capacity

        self.size -= 1
        return data

    def deleteLast(self):
        if self.isEmpty():
            return "Deque is empty"

        data = self.array[self.rear]
        if self.front == self.rear:  # Deque has only one element
            self.front = self.rear = -1
        else:
            self.rear = (self.rear - 1 + self.capacity) % self.capacity

        self.size -= 1
        return data

    def getFront(self):
        if self.isEmpty():
            return "Deque is empty"
        return self.array[self.front]

    def getRear(self):
        if self.isEmpty():
            return "Deque is empty"
        return self.array[self.rear]

Operations Explanation (操作说明):

Insert Front (插入前端):
- We calculate the new front index by moving backward in the array (using modulo operation for circular behavior) and insert the element at this position. If the deque was initially empty, both front and rear are set to the same index.
- 我们通过在数组中向后移动（使用取模操作实现循环行为）计算新的前端索引，并将元素插入此位置。如果双端队列最初为空，则 front 和 rear 设置为相同的索引。
Big O Analysis:
- Time Complexity: O(1) – Insertion is done in constant time.
- Space Complexity: O(1) – No additional space is required beyond the array.
Insert Last (插入后端):
- We calculate the new rear index by moving forward in the array (using modulo operation for circular behavior) and insert the element at this position. If the deque was initially empty, both front and rear are set to the same index.
- 我们通过在数组中向前移动（使用取模操作实现循环行为）计算新的后端索引，并将元素插入此位置。如果双端队列最初为空，则 front 和 rear 设置为相同的索引。
Big O Analysis:
- Time Complexity: O(1) – Insertion is done in constant time.
- Space Complexity: O(1) – No additional space is required beyond the array.
Delete Front (删除前端):
- We remove the element at the front of the deque. If the deque becomes empty after this operation, both front and rear are reset to -1. Otherwise, we update the front index to move forward in the array.
- 我们移除双端队列前端的元素。如果操作后双端队列为空，则 front 和 rear 都重置为 -1。否则，我们更新 front 索引以在数组中向前移动。
Big O Analysis:
- Time Complexity: O(1) – Deletion is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Delete Last (删除后端):
- We remove the element at the rear of the deque. If the deque becomes empty after this operation, both front and rear are reset to -1. Otherwise, we update the rear index to move backward in the array.
- 我们移除双端队列后端的元素。如果操作后双端队列为空，则 front 和 rear 都重置为 -1。否则，我们更新 rear 索引以在数组中向后移动。
Big O Analysis:
- Time Complexity: O(1) – Deletion is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Get Front (获取前端元素):
- We simply return the data at the front of the deque without removing it.
- 我们仅返回双端队列 front 处的元素，而不移除它。
Big O Analysis:
- Time Complexity: O(1) – Access is done in constant time.
- Space Complexity: O(1) – No additional space is required.
Get Rear (获取后端元素):
- We return the data at the rear of the deque without removing it.
- 我们返回双端队列 rear 处的元素，而不移除它。
Big O Analysis:
- Time Complexity: O(1) – Access is done in constant time.
- Space Complexity: O(1) – No additional space is required.

Handling the Circular Array (处理循环数组):

In this implementation, handling the circular nature of the array is crucial. The modulo operation (% self.capacity) is used to wrap around the indices when they reach the end of the array. This ensures that the array behaves like a circular buffer, allowing us to efficiently utilize the fixed array for deque operations.

在这个实现中，处理数组的循环特性是至关重要的。使用取模操作（% self.capacity）来绕过索引到达数组末端时的环绕问题。这确保了数组表现得像一个循环缓冲区，使我们能够高效地利用固定数组来进行双端队列操作。

Summary (总结):

Implementing a deque using a fixed-size array is a space-efficient method, especially for scenarios where the maximum size of the deque is known beforehand. The circular nature of the array ensures that we can perform all deque operations in constant time, making this implementation ideal for performance-critical applications.

使用固定大小的数组实现双端队列是一种节省空间的方法，尤其适用于事先知道双端队列最大大小的场景。数组的循环特性确保我们可以在常数时间内执行所有双端队列操作，使这种实现非常适合对性能要求严格的应用程序。

Post Views: 47

CODEBITWAVE