java实现环形队列的链式存储
程序员文章站
2022-06-05 14:46:32
...
环形队列是首位相连的,所以队尾元素就会指向队首元素。
环形队列初始时,队尾指针rear.next等于null
大概图如下:
实现代码如下:
package 数据结构;
// 环形队列-链表实现
public class RingQueue {
private Node rear = new Node(); // 队尾指针
class Node{
String value;
Node next;
}
/**
* 进队在尾指针插入
* @return
* @param value
*/
public boolean enQueue(String value) {
Node n = new Node();
n.value = value;
if(rear.next == null) { // 空队列
rear.next = n; // 更新队首指针
n.next = n; // 指向自身
return true;
}
n.next = rear.next.next; // 在队尾插入新节点
rear.next.next = n;
rear = n; // 更新队尾指针
return true;
}
/**
* 出队在队首删除
* @return
*/
public String deQueue() {
if(rear.next == null) { // 空队列
return null;
}
String temp = null;
if(rear.next == rear.next.next) { // 环形队列中只有一个元素
temp = rear.next.value;
rear.next = null;
return temp;
}
temp = rear.next.next.value; // 环形队列中有两个或者两个以上的元素
rear.next.next = rear.next.next.next;
return temp;
}
/**
* 判断队列是否为空
* @return
*/
public boolean isEmpty() {
return rear.next == null;
}
public static void main(String[] args) {
RingQueue queue = new RingQueue();
System.out.println(queue.isEmpty());
queue.enQueue("苏悟空");
queue.enQueue("苏乞儿");
queue.enQueue("周星星");
System.out.println(queue.isEmpty());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.deQueue());
System.out.println(queue.isEmpty());
}
}
运行结果如下:
true
false
苏悟空
周星星
苏乞儿
true
下一篇: PHP匹配颜色函数的使用技巧_PHP教程