Java实现环形队列

我不是女神ヾ 2022-09-30 07:04 217阅读 0赞

> 这里我定义的环形队列为：列表中最后一个元素是指向列表中的第一个元素，而且里面提供一个next方法，可以不断获取下一个元素，在环形队列中也就是不断的转圈，实现方式如下：

队列中提供的方法：

public boolean add(E e)：加入队列
    public E next()：加入返回当前指针元素并把指针指向下一个元素
    public E prev()：返回当前元素，并把指针指向上一个元素
    remove(E e)：删除队列中某一个元素

完整的实现代码如下：

public class CircularQueue<E> { 
        private int size;
    
        //指针
        private Node<E> node;
    
        private Node<E> first;
        private Node<E> last;
    
        private final int MODE_NEXT = 0;
        private final int MODE_PREV = 1;
        private int lastMode = MODE_NEXT; //最后一次操作，0为next，1为prev
    
    
    
        public CircularQueue() {
    
        }
    
        /** * 加入队列 * @param e */
        public boolean add(E e){
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, first);
            last = newNode;
    
            if (node == null) node = newNode; //指针
            if (l == null) {
                first = newNode;
                first.prev = first;
            }
            else {
                l.next = newNode;
                first.prev = l.next;
            }
    
            size++;
            return true;
        }
    
        /** * 返回当前指针元素并把指针指向下一个元素 * @return */
            public E next() {
            if (node == null) {
                return null;
            }
            E e = node.item;
            node = node.next;
    
            lastMode = MODE_NEXT;
            return e;
        }
    
        /** * 返回当前元素，并把指针指向上一个元素 * @return */
        public E prev() {
            if (node == null) {
                return  null;
            }
            E e = node.item;
            node = node.prev;
    
            lastMode = MODE_PREV;
            return e;
        }
    
        /** * 删除队列中某一个元素 * @param e * @return */
        public boolean remove(E e) {
            if (e == null) {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (x.item == null) {
                        unlink(x);
                        return true;
                    }
                }
            } else {
                for (Node<E> x = first; x != null; x = x.next) {
                    if (e.equals(x.item)) {
                        unlink(x);
                        return true;
                    }
                }
            }
    
            size--;
            return true;
        }
    
        public E peek(){
            return node.item;
        }
    
        /** * 删除节点 */
        E unlink(Node<E> x) {
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == x || next == x) {
                this.first = null;
                this.last = null;
                this.node = null;
            }
    
            next.prev = prev;
            prev.next = next;
    
            if ((element==null&&this.node.item==null) || (element.equals(this.node.item))) {
                this.node = lastMode==MODE_NEXT ? this.node.next : this.node.prev;
            }
    
            x.item = null;
            x = null;
            size--;
            return element;
        }
    
        public int size() {
            return size;
        }
    
    
        /** * 节点类 * @param <E> */
        private static class Node<E> { 
            E item;
            Node<E> next;
            Node<E> prev;
    
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
        }
    
    }

> 如果在高并发的情况下需要实现线程同步的环形队列，只需要继承上面的类，为需要同步的方法加锁即可：

import java.util.concurrent.locks.ReentrantLock;
    
    /** * Created by giant039 on 2017/3/17. */
    public class CircularBlockingQueue<E> extends CircularQueue<E> { 
        /** 对添加，删除，指针移动操作加锁 */
        protected final ReentrantLock putLock = new ReentrantLock();
    
        private QueueListener listener;
    
        public CircularBlockingQueue() {
            super();
        }
    
        public CircularBlockingQueue(QueueListener listener) {
            super();
            this.listener = listener;
        }
    
        public void setListener(QueueListener listener) {
            this.listener = listener;
        }
    
        @Override
        public boolean add(E e) {
            final ReentrantLock putLock = this.putLock;
            try {
                putLock.lockInterruptibly();
                super.add(e);
    
                if (listener != null) listener.afterAdd(e);
    
                return true;
            } catch (InterruptedException exp) {
                exp.printStackTrace();
                return false;
            } finally {
                putLock.unlock();
            }
    
        }
    
        @Override
        public E next() {
            final ReentrantLock putLock = this.putLock;
            try {
                putLock.lockInterruptibly();
                return super.next();
            } catch (InterruptedException e) {
                e.printStackTrace();
                return null;
            } finally {
                putLock.unlock();
            }
    
        }
    
        @Override
        public E prev() {
            final ReentrantLock putLock = this.putLock;
            try {
                putLock.lockInterruptibly();
                return super.prev();
            } catch (InterruptedException e) {
                e.printStackTrace();
                return null;
            } finally {
                putLock.unlock();
            }
        }
    
        @Override
        public boolean remove(E e) {
            final ReentrantLock putLock = this.putLock;
            try {
                putLock.lockInterruptibly();
    
                if (listener != null) listener.afterAdd(e);
    
                return super.remove(e);
            } catch (InterruptedException exp) {
                exp.printStackTrace();
                return false;
            } finally {
                putLock.unlock();
            }
        }
    
    
        /** * 监听器监听插入，删除，等操作之后需要实现的功能 */
        interface QueueListener<E> {
            void afterAdd(E e);
            void afterRemove(E e);
        }
    
    }