欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

java实现环形队列的链式存储

程序员文章站 2022-06-05 14:46:32
...

环形队列是首位相连的,所以队尾元素就会指向队首元素。
环形队列初始时,队尾指针rear.next等于null
大概图如下:
java实现环形队列的链式存储

实现代码如下:

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