3.17. 用Python实现双端队列

3.17. Implementing a Deque in Python

中文英文

正如我们在之前的章节中所做的，我们将为抽象数据类型双端队列（deque）的实现创建一个新类。再次使用 Python 列表，我们可以利用其提供的丰富方法来构建双端队列的细节。我们的实现（Listing 1）将假设双端队列的后端在列表的第 0 个位置。

class Deque:
    """使用列表实现双端队列"""

    def __init__(self):
        """创建一个新的双端队列"""
        self._items = []

    def is_empty(self):
        """检查双端队列是否为空"""
        return not bool(self._items)

    def add_front(self, item):
        """将一个项添加到双端队列的前端"""
        self._items.append(item)

    def add_rear(self, item):
        """将一个项添加到双端队列的后端"""
        self._items.insert(0, item)

    def remove_front(self):
        """从双端队列的前端移除一个项"""
        return self._items.pop()

    def remove_rear(self):
        """从双端队列的后端移除一个项"""
        return self._items.pop(0)

    def size(self):
        """获取双端队列中的项数"""
        return len(self._items)

在 remove_front 方法中，我们使用 pop 方法从列表中移除最后一个元素。然而，在 remove_rear 方法中，pop(0) 方法必须移除列表中的第一个元素。同样，在 add_rear 方法中，我们需要使用 insert 方法（第 12 行），因为 append 方法假设将新元素添加到列表的末尾。

CodeLens 1 展示了 Deque 类的实际操作，按照 表 1 中的操作序列执行。

class Deque:
    """使用列表实现双端队列"""

    def __init__(self):
        """创建一个新的双端队列"""
        self._items = []

    def is_empty(self):
        """检查双端队列是否为空"""
        return not bool(self._items)

    def add_front(self, item):
        """将一个项添加到双端队列的前端"""
        self._items.append(item)

    def add_rear(self, item):
        """将一个项添加到双端队列的后端"""
        self._items.insert(0, item)

    def remove_front(self):
        """从双端队列的前端移除一个项"""
        return self._items.pop()

    def remove_rear(self):
        """从双端队列的后端移除一个项"""
        return self._items.pop(0)

    def size(self):
        """获取双端队列中的项数"""
        return len(self._items)

d = Deque()
print(d.is_empty())
d.add_rear(4)
d.add_rear('dog')
d.add_front('cat')
d.add_front(True)
print(d.size())
print(d.is_empty())
d.add_rear(8.4)
print(d.remove_rear())
print(d.remove_front())

你可以看到，这个实现与之前描述的栈和队列的 Python 代码有很多相似之处。你还会发现，在这个实现中，从前端添加和移除项的操作是 $O(1)$，而从后端添加和移除项的操作是 $O(n)$。这符合常见的操作复杂度。再次强调，了解在实现中前端和后端的位置非常重要。

As we have done in previous sections, we will create a new class for the implementation of the abstract data type deque. Again, the Python list will provide a very nice set of methods upon which to build the details of the deque. Our implementation (Listing 1) will assume that the rear of the deque is at position 0 in the list.

class Deque:
    """Deque implementation as a list"""

    def __init__(self):
        """Create new deque"""
        self._items = []

    def is_empty(self):
        """Check if the deque is empty"""
        return not bool(self._items)

    def add_front(self, item):
        """Add an item to the front of the deque"""
        self._items.append(item)

    def add_rear(self, item):
        """Add an item to the rear of the deque"""
        self._items.insert(0, item)

    def remove_front(self):
        """Remove an item from the front of the deque"""
        return self._items.pop()

    def remove_rear(self):
        """Remove an item from the rear of the deque"""
        return self._items.pop(0)

    def size(self):
        """Get the number of items in the deque"""
        return len(self._items)

In remove_front we use the pop method to remove the last element from the list. However, in remove_rear, the pop(0) method must remove the first element of the list. Likewise, we need to use the insert method (line 12) in add_rear since the append method assumes the addition of a new element to the end of the list.

CodeLens 1 shows the Deque class in action as we perform the sequence of operations from Table 1.

class Deque:
    """Queue implementation as a list"""

    def __init__(self):
        """Create new deque"""
        self._items = []

    def is_empty(self):
        """Check if the deque is empty"""
        return not bool(self._items)

    def add_front(self, item):
        """Add an item to the front of the deque"""
        self._items.append(item)

    def add_rear(self, item):
        """Add an item to the rear of the deque"""
        self._items.insert(0, item)

    def remove_front(self):
        """Remove an item from the front of the deque"""
        return self._items.pop()

    def remove_rear(self):
        """Remove an item from the rear of the deque"""
        return self._items.pop(0)

    def size(self):
        """Get the number of items in the deque"""
        return len(self._items)

d=Deque()
print(d.is_empty())
d.add_rear(4)
d.add_rear('dog')
d.add_front('cat')
d.add_front(True)
print(d.size())
print(d.is_empty())
d.add_rear(8.4)
print(d.remove_rear())
print(d.remove_front())

You can see many similarities to Python code already described for stacks and queues. You are also likely to observe that in this implementation adding and removing items from the front is $O(1)$ whereas adding and removing from the rear is $O(n)$. This is to be expected given the common operations that appear for adding and removing items. Again, the important thing is to be certain that we know where the front and rear are assigned in the implementation.

---

最后更新: 2024年9月12日
创建日期: 2024年9月9日