双端队列数组实现的具体代码
时间: 2024-10-08 16:05:10 浏览: 10
双端队列(deque,即double-ended queue)数组实现的基本思路是在数组中设置两个指针,一个指向队首元素,一个指向队尾元素。下面是一个简单的Python实现示例:
```python
class ArrayDeque:
def __init__(self, capacity):
self.capacity = capacity
self.data = [None] * capacity
self.head = 0 # 队首
self.tail = 0 # 队尾
def is_empty(self):
return self.head == self.tail
def append_left(self, item):
if not self.is_full():
self.data[self.tail] = item
self.tail = (self.tail + 1) % self.capacity
def append_right(self, item):
if not self.is_full():
self.data[self.head] = item
self.head = (self.head + 1) % self.capacity
def pop_left(self):
if not self.is_empty():
item = self.data[self.tail]
self.data[self.tail] = None
self.tail = (self.tail - 1) % self.capacity
return item
def pop_right(self):
if not self.is_empty():
item = self.data[self.head]
self.data[self.head] = None
self.head = (self.head - 1) % self.capacity
return item
def is_full(self):
return self.head == self.tail + 1
# 使用示例:
deq = ArrayDeque(5)
deq.append_left(1)
deq.append_right(2)
print(deq.pop_left()) # 输出: 2
```
在这个例子中,`append_left` 和 `append_right` 分别用于在队列的头部和尾部添加元素,`pop_left` 和 `pop_right` 则分别从头部和尾部移除元素。通过 `%` 运算符实现循环索引,使得队列可以无缝扩展到数组的开始位置。