双端队列double-ended queue
### 什么是双端队列？
想象一下你有一个长长的面包（可以从前面和后面吃的那种），你可以从面包的两端开始吃，也可以从两端加上更多的面包片。这就是双端队列的基本概念。它是一种你可以从两头进行操作的队列。
双端队列有四种主要的操作：
1. **Push(X,D)**：在前面加上一个新的面包片X。
2. **Pop(D)**：从前面拿走一个面包片。
3. **Inject(X,D)**：在后面加上一个新的面包片X。
4. **Eject(D)**：从后面拿走一个面包片。
- **X**：表示要加入的元素。
- **D**：表示双端队列（deque）。“double-ended queue” 就是“双端队列”的意思。因为这个词太长，所以我们把它缩写成“deque”。
### 实际应用
为什么我们需要这样一个双端队列呢？让我们来看几个例子帮助理解：
1. **排队买票**：如果你去看电影，通常大家会排成一列队伍。你可以从队伍的前面加入或者从后面加入，有时候特殊情况（比如VIP）还可以优先从前面插队，这就是双端队列的一个简单例子。
2. **浏览器历史记录**：在你用浏览器上网时，你可以前进到下一个网页，也可以后退到上一个网页。这就是在前后操作的一个例子。
### 怎样实现双端队列？
要实现双端队列，我们可以用一种叫做“双向链表”的东西来实现它。
想象你有一串珍珠，每个珍珠都用线连起来。每个珍珠不仅知道下一个珍珠是谁，还知道前一个珍珠是谁。这就是双向链表的基本概念。
#### 实现双端队列
我们可以用双向链表来实现双端队列。每个珍珠（也叫“节点”）都可以有前一个和后一个节点，这样我们就能很快地在两端进行操作。
让我们来看看这个双端队列是怎么工作的：
### 例子
```python
# 创建一个双端队列
deque = Deque()
# 插入一些值到前端
deque.push(1) # 队列: 1
deque.push(2) # 队列: 2, 1
deque.push(3) # 队列: 3, 2, 1
# 插入一些值到后端
deque.inject(4) # 队列: 3, 2, 1, 4
deque.inject(5) # 队列: 3, 2, 1, 4, 5
# 从前端弹出值
print(deque.pop()) # 输出: 3
print(deque.pop()) # 输出: 2
# 从后端弹出值
print(deque.eject()) # 输出: 5
print(deque.eject()) # 输出: 4
# 队列现在只剩下一个元素: 1
```
这个例子展示了如何使用 `push`, `pop`, `inject`, 和 `eject` 方法在双端队列上添加和移除元素。
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
class Deque:
def __init__(self):
self.front = None
self.rear = None
def push(self, value):
new_node = Node(value)
if self.front is None:
self.front = self.rear = new_node
else:
new_node.next = self.front
self.front.prev = new_node
self.front = new_node
def pop(self):
if self.front is None:
raise IndexError("Pop from empty deque")
value = self.front.value
self.front = self.front.next
if self.front is not None:
self.front.prev = None
else:
self.rear = None
return value
def inject(self, value):
new_node = Node(value)
if self.rear is None:
self.front = self.rear = new_node
else:
new_node.prev = self.rear
self.rear.next = new_node
self.rear = new_node
def eject(self):
if self.rear is None:
raise IndexError("Eject from empty deque")
value = self.rear.value
self.rear = self.rear.prev
if self.rear is not None:
self.rear.next = None
else:
self.front = None
return value
```
代码解释：
### `class Node` 类
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
self.prev = None
```
1. 定义 `Node` 类，表示双端队列中的一个节点。
2. `__init__` 方法初始化该节点，设置 `value` 为节点的值，`next` 和 `prev` 分别指向下一个和前一个节点，初始值均为 `None`。
### `class Deque` 类
```python
class Deque:
def __init__(self):
self.front = None
self.rear = None
```
1. 定义 `Deque` 类。
2. `__init__` 方法初始化双端队列，设置 `front` 和 `rear` 为 `None`，表示队列最初是空的。
### `push` 方法
```python
def push(self, value):
new_node = Node(value)
if self.front is None:
self.front = self.rear = new_node
else:
new_node.next = self.front
self.front.prev = new_node
self.front = new_node
```
1. 定义 `push` 方法，将一个新值添加到队列的前端。
2. 创建一个新节点 `new_node`。
3. 如果队列为空，设置 `front` 和 `rear` 都为新节点。
4. 否则，把新节点插入到前端，并更新指针关系。
### `pop` 方法
```python
def pop(self):
if self.front is None:
raise IndexError("Pop from empty deque")
value = self.front.value
self.front = self.front.next
if self.front is not None:
self.front.prev = None
else:
self.rear = None
return value
```
1. 定义 `pop` 方法，从队列的前端移除一个值并返回。
2. 如果队列为空，抛出错误。
3. 获取前端节点的值。
4. 移动前端到下一个节点，并更新指针关系。
5. 如果队列变为空，更新 `rear`。
6. 返回前端节点的值。
### `inject` 方法
```python
def inject(self, value):
new_node = Node(value)
if self.rear is None:
self.front = self.rear = new_node
else:
new_node.prev = self.rear
self.rear.next = new_node
self.rear = new_node
```
1. 定义 `inject` 方法，将一个新值添加到队列的后端。
2. 创建一个新节点 `new_node`。
3. 如果队列为空，设置 `front` 和 `rear` 都为新节点。
4. 否则，把新节点插入到后端，并更新指针关系。
### `eject` 方法
```python
def eject(self):
if self.rear is None:
raise IndexError("Eject from empty deque")
value = self.rear.value
self.rear = self.rear.prev
if self.rear is not None:
self.rear.next = None
else:
self.front = None
return value
```
1. 定义 `eject` 方法，从队列的后端移除一个值并返回。
2. 如果队列为空，抛出错误。
3. 获取后端节点的值。
4. 移动后端到前一个节点，并更新指针关系。
5. 如果队列变为空，更新 `front`。
6. 返回后端节点的值。
`def` 是 `define`（定义）的缩写。在 Python 中，`def` 关键字用于定义一个函数或方法。它告诉解释器接下来的代码块是一个函数的主体，并为这个函数指定一个名称。
`init` 是 `initialize`（初始化）的缩写。在编程中，`initialize` 通常意味着为变量或对象设置初始值或状态。在 Python 中，`__init__` 方法用于在创建对象时初始化该对象的属性。
`__init__` 不是某个词的缩写，而是 Python 中一种特殊的方法，称为“初始化方法”或构造函数。它用于在创建类的实例（对象）时初始化该实例的属性。
在 Python 中，双下划线开头和结尾的名称（如 `__init__`）是特殊方法，也被称为“魔术方法”或“魔法方法”。这些方法在特定情况下由 Python 自动调用，而不需要明确地调用它们。
具体地说，`__init__` 方法在创建类的实例时由 Python 解释器自动调用，用于初始化对象的属性。