java假设以带头结点的循环链表表示队列
时间: 2023-11-04 08:07:42 浏览: 91
假设以带头结点的循环链表表示一个队列,并且只设一个队尾指针指向尾元素结点(注意不设头指针),试写出相应的置空队、入队、出队的算法 (Java)
Java可以使用以下代码来实现以带头结点的循环链表表示队列:
```java
public class Queue<T> {
private Node<T> head;
private int size;
public Queue() {
head = new Node<>(null);
head.next = head;
size = 0;
}
public void enqueue(T item) {
Node<T> newNode = new Node<>(item);
newNode.next = head.next;
head.next = newNode;
size++;
}
public T dequeue() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
Node<T> nodeToRemove = head.next;
head.next = nodeToRemove.next;
size--;
return nodeToRemove.data;
}
public T peek() {
if (isEmpty()) {
throw new NoSuchElementException("Queue is empty");
}
return head.next.data;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
private static class Node<T> {
T data;
Node<T> next;
Node(T data) {
this.data = data;
this.next = null;
}
}
}
```
在这个实现中,`Queue`类有一个`head`属性,它是一个带有`null`数据的空节点,用来作为循环链表的头结点。队列的大小由`size`属性记录。
`enqueue`方法将一个新节点插入到头结点之后,然后更新`size`。
`dequeue`方法从队列的头部删除一个节点,然后更新`size`并返回被删除节点的数据。如果队列为空,则抛出`NoSuchElementException`异常。
`peek`方法返回队列头部的节点的数据,但不删除该节点。如果队列为空,则抛出`NoSuchElementException`异常。
`isEmpty`方法检查队列是否为空。
`size`方法返回队列的大小。
`Node`是一个私有静态嵌套类,表示队列中的节点。每个节点都有一个`data`属性和一个指向下一个节点的`next`属性。
阅读全文