用循环方式实现双端队列
时间: 2024-09-20 18:04:10 浏览: 29
双端队列(Deque,全称Double Ended Queue),是一种允许在其两端进行插入和删除操作的数据结构,类似于数组的两端。用循环方式实现双端队列可以采用数组或者链表数据结构。
1. 数组实现(如Java的ArrayDeque):
```java
public class CircularArrayDeque {
private int[] elements;
private int front; // 队首元素索引
private int rear; // 队尾元素索引
// 初始化数组大小和初始化等...
public void addFront(int value) {
if (isFull()) {
throw new IllegalStateException("Queue is full");
}
elements[(front + size - 1) % size] = value; // 使用模运算保持front始终在0到size-1范围内
front = (front + 1) % size;
}
public int removeRear() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
int removedValue = elements[rear];
rear = (rear + 1) % size;
return removedValue;
}
// 其他方法...
private boolean isEmpty() { ... }
private boolean isFull() { ... }
}
```
2. 链表实现:
```java
public class LinkedListDeque<T> {
private Node<T> front;
private Node<T> rear;
// 添加、删除节点等操作...
public void addFront(T value) {
Node<T> newNode = new Node<>(value);
if (isEmpty()) {
front = newNode;
rear = newNode;
} else {
newNode.next = front;
front.prev = newNode;
front = newNode;
}
}
public T removeRear() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
T value = rear.value;
rear = rear.prev;
if (rear == null) {
front = null;
}
return value;
}
// 省略其他方法...
}
class Node<T> {
T value;
Node<T> prev;
Node<T> next;
// 构造函数和内部方法...
}
```