带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点,不设头指针。试编写相应的置空队、判队空、入队和出队的java 算法。
时间: 2024-04-30 17:01:49 浏览: 62
数据结构算法 习题 答案 带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设头指针).pdf
5星 · 资源好评率100%
```java
public class QueueWithCircularLinkedList {
private Node rear; // 指向队尾元素的指针
public QueueWithCircularLinkedList() {
rear = null; // 初始化为空队列
}
// 置空队
public void clear() {
rear = null;
}
// 判队空
public boolean isEmpty() {
return rear == null;
}
// 入队
public void enqueue(int value) {
Node newNode = new Node(value);
if (rear == null) { // 队列为空
rear = newNode;
newNode.next = newNode; // 环形链表
} else {
newNode.next = rear.next;
rear.next = newNode;
rear = newNode;
}
}
// 出队
public int dequeue() throws Exception {
if (isEmpty()) {
throw new Exception("队列为空,不能出队");
}
int value;
if (rear.next == rear) { // 队列只有一个元素
value = rear.data;
rear = null;
} else {
Node front = rear.next;
value = front.data;
rear.next = front.next;
front.next = null;
}
return value;
}
// 链表节点类
private class Node {
int data;
Node next;
Node(int data) {
this.data = data;
next = null;
}
}
}
```
阅读全文