如果允许在循环队列的两端都可以进行插入和删除操作。构造一个循环队列,实现从队头入队,从队尾出队并输出。约定从队头入队时向下标小的方向发展,从队尾入队时则向下标大的方向发展。
时间: 2024-05-15 09:15:37 浏览: 23
这种队列叫做双端循环队列,可以使用数组实现。需要记录队头和队尾的下标,以及队列当前的元素个数。
具体实现如下:
```python
class Deque:
def __init__(self, capacity):
self.capacity = capacity
self.data = [None] * capacity
self.front = 0
self.rear = 0
self.size = 0
def is_empty(self):
return self.size == 0
def is_full(self):
return self.size == self.capacity
def enqueue_front(self, value):
if self.is_full():
raise Exception('Queue is full')
self.front = (self.front - 1 + self.capacity) % self.capacity
self.data[self.front] = value
self.size += 1
def enqueue_rear(self, value):
if self.is_full():
raise Exception('Queue is full')
self.data[self.rear] = value
self.rear = (self.rear + 1) % self.capacity
self.size += 1
def dequeue_front(self):
if self.is_empty():
raise Exception('Queue is empty')
value = self.data[self.front]
self.front = (self.front + 1) % self.capacity
self.size -= 1
return value
def dequeue_rear(self):
if self.is_empty():
raise Exception('Queue is empty')
self.rear = (self.rear - 1 + self.capacity) % self.capacity
value = self.data[self.rear]
self.size -= 1
return value
def __str__(self):
return str(self.data[self.front:self.front+self.size])
q = Deque(5)
q.enqueue_front(1)
q.enqueue_front(2)
q.enqueue_rear(3)
q.enqueue_rear(4)
print(q.dequeue_rear()) # 输出4
print(q.dequeue_front()) # 输出2
print(q) # 输出[1, 3]
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)