Java

java循环队列怎么实现

小亿
97
2023-08-01 22:54:26
栏目: 编程语言

Java中可以使用数组或者链表来实现循环队列。

  1. 使用数组实现循环队列:
public class CircularQueue {
private int[] queue;
private int front;
private int rear;
private int size;
public CircularQueue(int capacity) {
queue = new int[capacity];
front = 0;
rear = -1;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == queue.length;
}
public void enqueue(int data) {
if (isFull()) {
throw new IllegalStateException("Queue is full");
}
rear = (rear + 1) % queue.length;
queue[rear] = data;
size++;
}
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
int data = queue[front];
front = (front + 1) % queue.length;
size--;
return data;
}
}
  1. 使用链表实现循环队列:
public class CircularQueue {
private static class Node {
int data;
Node next;
public Node(int data) {
this.data = data;
}
}
private Node head;
private Node tail;
private int size;
public CircularQueue() {
head = null;
tail = null;
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode;
} else {
tail.next = newNode;
}
tail = newNode;
tail.next = head; // make it circular
size++;
}
public int dequeue() {
if (isEmpty()) {
throw new IllegalStateException("Queue is empty");
}
int data = head.data;
if (head == tail) { // only one node in the queue
head = null;
tail = null;
} else {
head = head.next;
tail.next = head; // remove the reference to the old head node
}
size--;
return data;
}
}

以上是两种常见的循环队列的实现方式,可以根据自己的实际需求选择适合的实现方式。

0
看了该问题的人还看了