算法（Algorithms）第4版 练习 1.3.29

题目

使用环形链表实现队列（FIFO），环形链表也是链表，只是没有任何一个节点的链接是空的，且只有链表非空则 last.next 的值为 fist。只能使用一个 Node 类型的实例变量（last）。

答案

/**
 * 练习题 1.3.29
 *
 * @author tingshuo 2022/10/30 11:06
 */
public interface Queue<E> extends Iterable<E> {
    /**
     * 添加一个元素
     */
    void dequeue(E e);

    /**
     * 删除最早添加的元素
     */
    E dequeue();

    /**
     * 队列是否为空
     */
    boolean isEmpty();

    /**
     * 队列中的元素
     */
    int size();
}

package com.company;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 使用环形链表实现队列（FIFO）
 *
 * @author tingshuo 2022/10/30 11:10
 */
public class QueueOfCircular<E> implements Queue<E> {

    private Node<E> last;
    private int size;

    @Override
    public void dequeue(E e) {

        Node<E> node = new Node<>(e, null);

        if (last == null) {
            last = node;
            last.next = last;
        } else {
            node.next = last.next;
            last.next = node;
            last = node;
        }

        size++;
    }

    @Override
    public E dequeue() {

        if (isEmpty()) {
            throw new UnsupportedOperationException("queue is empty.");
        }

        E e = last.next.item;
        if (size == 1) {
            last = null;
        } else {
            last.next = last.next.next;
        }
        size--;

        return e;
    }

    @Override
    public boolean isEmpty() {
        return last.next == null;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Iterator<E> iterator() {
        return new QueueOfCircularIterator(last, size());
    }

    /**
     * 节点定义
     */
    private static class Node<E> {
        E item;
        Node<E> next;

        Node(E element, Node<E> next) {
            this.item = element;
            this.next = next;
        }
    }

    /**
     * Iterator
     */
    private class QueueOfCircularIterator implements Iterator<E> {

        private Node<E> current;
        private int size;

        public QueueOfCircularIterator(Node<E> last, int size) {
            if (last == null) {
                this.current = null;
            } else {
                this.current = last.next;
            }

            this.size = size;
        }

        @Override
        public boolean hasNext() {
            return size > 0;
        }

        @Override
        public E next() {

            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            E e = current.item;
            current = current.next;
            size--;
            return e;
        }
    }
}